자료구조-그래프 Python(파이썬)

정의

그래프란 정점과 간선들로 이루어진 집합으로 표현되는 자료구조

트리도 일종의 그래프라고 할 수 있다.

종류

• 무방향 그래프 : 간선이 방향을 가지지 않음
• 방향 그래프 : 간선이 방향을 가지고 있음
• 가중치 그래프 : 각 간선에 가중치 정보가 포함됨. 가중치는 거리, 비용 등으로 표현 할 수 있다.

용어

1. 인접 정점: 어떤 정점에서 에지에 의해 직접 연결된 정점

2. 그래프 차수

      2-1) 무방향 그래프: 하나의 정점에 연결된 다른 정점의 수 (=인접 정점의 수)

      2-2) 방향 그래프: 진입 차수와 진출 차수로 구분, 진입 차수는 외부에서 오는 간선의 수 진출 차수는 외부에서 들어오는 간선의 수

                             -> 진입 차수의 합= 진출 차수의 합= 그래프 내 모든 간선의 수

3. 그래프 경로: 특정 정점에서 다른 정점까지의 경로를 의미, 두 정점 사이의 경로 상 정점 나열을 통해 표현

-> 경로의 길이= 경로 구성 간선의 수

    순환: 경로의 시작 정점과 끝 정점이 동일한 경로

    단순 경로: 반복되는 정점, 간선이 없는 경로

특수 그래프

1. 연결 그래프: 무향 그래프 G에 있는 모든 정점 쌍에 대하여 경로가 존재할 경우, 무향 그래프 G는 연결 그래프이다. 경로가 존재한다는 의미는 하나의 정점에서 다른 정점으로 갈 수 있느냐 없느냐를 봐야한다.

 

2. 트리: 무순환 연결 그래프. 이미 방문한 엣지를 무조건 다시 방문하지 않고서는 돌아갈 수가 없다. 또한 간선이 최소로만 연결되어 있다.

 

3. 완전 그래프: 모든 정점이 서로 연결되어 있는 그래프. 무방향은 n(n-1)/2, 방향은 n(n-1)

표현

1. 인접 행렬 기반 그래프

각 정점간의 가중치나 간선의 유무를 행렬로 표현한다.

무방향 그래프의 경우 전치행렬이 되어도 값이 같다.

 

2. 인접 리스트 기반 그래프

인접 행렬이 행렬을 이용한것과는 달리 인접 리스트로 구현한다.

파이썬에서는 그냥 딕셔너리 자료형에 리스트를 넣어 쉽게 인접 리스트처럼 구현하여 사용할 수 있다.

Ex) graph = { 0: [1], 1: [0,2], 2: [] }

 

탐색 방법

BFS

BFS는 너비 우선 탐색으로, 현재 Node(Vertex)에서 연결된 Node로 우선적으로 탐색하는 것을 뜻한다.

https://curiousheaven99.tistory.com/12

BFS-Python(파이썬)

DFS

BFS는 깊이 우선 탐색으로, 현재 Node(Vertex)에서 연결된 Node중에서 하나를 골라 더이상 진행할 수 없을때까지 탐색한다. 그 후 더이상 진행이 불가능하면, 진행이 가능한 Node 까지 되돌아 와서 탐색을 한다.

https://curiousheaven99.tistory.com/11

DFS-Python(파이썬)

 

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS