[그래프 탐색] DFS와 BFS

1. 그래프란?

 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 

(좌) 무방향 그래프 (우) 유향 그래프

 상호 관계가 대칭적이지 않은 경우 방향을 가진 간선으로 나타낼 수 있다. 이때 이러한 그래프를 방향을 가진 그래프 혹은 Direct Graph 유향 그래프라고 한다.

 

 반면 간선의 방향이 없는 그래프를 무방향 그래프 혹은 Undirected Graph 무향 그래프라고 한다.

---

2. 그래프의 표현

 그래프의 표현 방법에는 행렬을 이용하는 방식과 리스트를 이용하는 방식이 있다.

 

2.1 인접 행렬

 그래프 G = (V, E)에서 정점의 총 수를 n이라고 가정하자. 행렬의 크기는 n x n 행렬이 된다. 정점 i와 정점 j 사이에 간선이 존재하면 행렬의 (i, j)원소와 (j, i) 원소의 값을 1로 할당한다. 연결된 두 정점은 인접하다고 표현한다.

 

무향 그래프

	1	2	3	4	5	6
1	0	1	1	1	0	1
2	1	0	1	0	0	0
3	1	1	0	0	1	0
4	1	0	0	0	0	1
5	0	0	1	0	0	1
6	1	0	0	1	1	0

 위 무향 그래프를 기준으로 행렬을 채워 나간다.

 

 무방향 그래프의 경우 i와 j값이 같은 좌표를 기준으로 대칭을 이루는 것을 알 수 있다. 추가적으로 만약 간선에 가중치를 가진다면, 1 대신 가중치 값으로 행렬을 채울 수 있다.

 

 행렬 표현법은 이해하기 쉽고 간선의 존재 여부를 즉각적으로 알 수 있다. 또한 배열로 구현하기 때문에 원소의 값만 보면 쉽게 알 수 있다. 

 

 하지만 큰 단점이 존재한다. 행렬의 준비 과정에서 행렬의 모든 원소를 채우는 데만 n의 제곱에 비례하는 공간이 필요하고, n의 제곱에 비례하는 시간이 걸린다. 

2.2 인접 리스트

 인접 리스트 표현법은 각 정점에 인접한 정점들을 리스트로 표현하는 방법이다. 각 정점마다 리스트를 하나씩 만든다. 각 정점에 인접한 정점들을 연결 리스트로 연결한다. 행렬과 다르게 존재하지 않는 간선은 메모리 공간을 차지하지 않는다. 

 

인접 리스트 표현법

 장점으로는 인접 리스트는 공간이 간선의 수에 비례하는 양만큼 필요하기 때문에 인접 행렬보다 공간의 낭비가 적다.

 

 단점으로는 거의 모든 정점 쌍에 간선이 존재한다면 인접 리스트를 구현하기 위한 오버헤드만 증가할 뿐이다. 또한 간선의 존재를 확인하기 위해서는 리스트를 차례차례 훑어야 하기 때문에 인접 행렬보다 많은 시간이 걸리게 된다. 그렇기 때문에 간선의 밀도가 높은 경우 적합하지 않는 표현 방법이다.

2.3 인접 배열과 인접 해시 테이블 

 인접 행렬과 인접 리스트는 상황에 따라 장단점을 가지고 있다. 그렇기 때문에 각 정점에 연결된 정점들을 연결 리스트로 저장하는 대신 배열로 저장하여 연결 리스트의 포인터 관리의 번거로움을 줄인다. 또한 두 정점의 인접 여부를 체크하는 시간도 대폭 줄일 수 있다. 

 

인접 배열 표현

---

3. BFS Breadth-First Search

 너비 우선 탐색은 먼저 루트의 자식을 차례로 방문한다. 다음으로 루트의 자식의 자식, 즉 루트에서 두 개의 간선을 거쳐서 도달할 수 있는 정점을 방문한다. 그 다음 세 개의 간선을 거쳐 도달하는 정점들 순으로 루트에서 거리순으로 방문을 한다. 너비를 우선적으로 탐색하기 때문에 너비 우선 탐색이다.

---

4. DFS Depth-First Search

 깊이 우선 탐색은 루트의 자식 정점을 하나 방문한 다음 아래로 내려갈 수 있는 곳 까지 내려간다. 더 이상 내려갈 수 없으면 위로 되돌아 오다가 내려갈 곳이 있으면 즉각 내려간다. 아래로 갈 수 있는데 까지 갔다가 되돌아 오기 때문에 깊이를 우선적으로 탐색한다.

 

References.

문병로 지음 쉽게 배우는 알고리즘 개정판