[파이썬 | 자료구조] 9. 그래프(Graph)

9. 그래프(Graph)

9.1 그래프의 개념

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

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

9.2 그래프의 종류

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

9.3 그래프의 구현

1. 인접 행렬 기반 그래프

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

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

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

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

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

BFS

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

즉 아래 그림에서 A에서 BFS를 시작한다고 하면, B, E, I를 우선적으로 탐색하고, 그 후 B, E, I에 연결된 Node를 탐색한다.

즉 방문하는 순서는 ['A', 'B', 'E', 'I', 'C', 'F', 'H', 'J', 'D', 'G'] 순이 된다.

queue를 이용해서 구현할 수 있다.

DFS

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

즉 아래 그림에서 A에서 BFS를 시작한다고 하면, B를 우선적으로 탐색하고, 그 후 B에 연결된 Node를 탐색한다.

즉 방문하는 순서는 ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J'] 순이 된다.

stack을 이용해서 구현할 수 있고, 함수의 재귀호출을 이용해서 구현할 수도 있다.