[자료구조] 그래프 (BFS, DFS)

Graph (그래프)

• 현실세계 사물, 개념 간 연결 관계를 수학적 모델로 단순화하여 표현한 것
• V : 정점 (Vertex / Node) / E : 간선 (Edge / Link / Arc)
• 표현 : 그래프 G = (V, E)

그래프 용어

1. 정점, 노드 (Vertex, Node)
2. 간선 (Edge)
   • 무향 간선 (Undirected Edge) : 방향이 존재하지 않는 간선으로 양방향이다.
   • 유향 간선 (Directed Edge) : 방향이 존재하는 간선이다.
3. 인접 (Adjacent) : (정점의 관점에서) 두 정점 사이에 간선이 존재하면 A, B는 인접한다.
4. 부속 (Incident) : (간선의 관점에서) 두 정점 사이에 간선 e가 존재하면 간선 e는 두 정점에 부속한다.
5. 차수 (Degree) : 한 정점에 연결된 간선의 수
   • in-degree : 정점에 들어오는 간선의 수
   • out-degree : 나가는 간선의 수
6. 자기 간선과 다중 간선
   • 자기 간선 (Self-loop) : 자신으로 다시 돌아오는 간선
   • 다중 간선 (Multiple / Parallel edges) : 두 개 이상의 간선이 똑같은 두 정점에 부속
7. 경로 (Path) : 정점과 간선이 교대로 구성된 수열
   • 단순 경로 (Simple Path) : 같은 정점을 두 번 이상 지나지 않는 경로
8. 회로 (Cycle) : A 정점에서 출발했을 때 다시 A 정점으로 돌아오는 경로
   • 단순 회로 (Simple Cycle) : 같은 정점을 두 번 이상 지나지 않는 싸이클
9. 연결됨 (Connected) : 정점 A → B로의 경로, A와 B는 연결되어 있다.

그래프 종류

1. 무향 그래프 (Undirected) : 무방향 간선으로 구성
2. 유향 그래프 (Directed) : 방향 간선으로 구성
3. 가중치 그래프 (Weighted) : 가중치(비용)를 갖는 간선들로 구성
4. 정규 그래프 (Regular) : 모든 정점이 동일한 차수를 가짐
5. 완전 그래프 (Complete) : 모든 정점이 서로 인접
   1. 완전 그래프 → 정규 그래프
6. 연결 그래프 (Connected) : 모든 정점이 연결, 모든 정점끼리 경로가 존재
7. 부분 그래프 : 어떤 그래프의 꼭짓점과 변 가운데 일부로 구성
8. 트리 그래프 : 싸이클을 가지지 않는 연결 그래프
   1. 모든 정점에 대해 경로가 정확히 1개 존재

그래프 표현

그래프의 표현 방식에는 간선 리스트, 인접 행렬, 인접 리스트 3가지 방식이 있다.

정점 개수 : V개, 간선 개수 : E개

간선 리스트 (Edge List)

• 이차원 배열 A에 정보를 저장
• 두 정점 x, y 를 연결하는 간선 k에 대해서 A[k][0] = x, A[k][1] = y
• 가중치 그래프의 경우 A[k][2] 에 가중치 정보를 저장

인접 행렬 (Adjacency Matrix)

• V x V 이차원 배열 A에 정보를 저장
• Vi, Vj를 연결하는 간선이 존재한다면 A[i][j] = 1, 존재하지 않는다면 A[i][j] = 0
• 가중치 그래프의 경우 1 대신 가중치 정보를 저장

메모리 복잡도가 V2 이기 때문에 100 이하의 값일 때 사용하는 것이 좋다.

인접 리스트 (Adjacent List)

• V 개의 Linked List로 그래프 정보 저장
• 가중치 그래프의 경우 (정점 정보, 가중치 정보)를 함께 저장
  • C++ : pair, Java : class

그래프 표현 방식 비교

간선 리스트 인접 행렬 인접 리스트

공간	E	V2	V + E
정점 Va 의 부속 간선	E	V	Va 차수
정점 Va, Vb 의 인접 여부	E	1	min(Va 차수, Vb 차수)
정점 삽입	1	V2	1
간선 삽입	1	1	1

그래프 탐색

DFS (깊이 우선 탐색)

• 더 이상 연결된 간선이 없을 때까지 탐색하고, 이 후 되돌아가 다시 탐색한다.
• 인접 행렬의 시간복잡도는 O(V^2), 인접 리스트의 시간복잡도는 O(V+E) 이다.
• 자기 자신을 호출하는 재귀함수를 이용해 구현한다.

출처: https://commons.wikimedia.org/wiki/File:Depth-First-Search.gif

BFS (너비 우선 탐색)

• 그래프 시작점부터 가까운 점들부터 우선 탐색한다.
• 인접 행렬의 시간복잡도는 O(V^2), 인접 리스트의 시간복잡도는 O(V+E) 이다.
• 먼저 탐색되는 위치를 먼저 꺼내어 인접한 점들을 보기 때문에 큐를 사용한다.

출처: https://commons.wikimedia.org/wiki/File:Breadth-First-Search-Algorithm.gif