3. Decompositions of Graphs (3) DFS, BFS

21 Jan 2020

Sanjoy Dasgupta가 저술한 책인 Algorithms과 이기창님의 블로그를 참고하였다.

1-1. 깊이우선탐색(DFS. Depth First Search)

하나의 시작 정점에서 출발해 더이상 나아갈 엣지가 없을 때 까지 깊이 탐색하는 그래프 순회 기법

마치 미로에서 나와있는 길을 쭉~가다가 막히면 다시 길이 나있는 곳으로 돌아와서 탐색하는 것과 같다.

1-2. 깊이우선탐색(DFS) 방법

깊이우선탐색을 할 때는 start time과 finish time을 사용한다. 노드 안의 숫자를 보면 ‘/’를 기준으로 숫자가 나뉘어있는데, 앞이 start time, 뒤가 finish time이다. 먼저 (a)에서 $u$라는 시작노드에서 DFS를 시작한다. 따라서 $u$의 start time이 1이므로 ‘ 1/ ‘을 써준다. 이후 $u$에서 임의의 노드로 향하는 엣지 중 하나를 아무거나 선택한다. 여기서는 $v$로 향하는 엣지를 선택했으며, $v$는 2번째 시작노드가 되므로 ‘ 2 / ‘를 써준다. 이렇게 쭉 가다보면 (d)와 같이 $u$에서 $v$와 $y$를 거쳐 $x$까지 간 것을 알 수 있다.

이제 더이상 나아갈 곳이 없으므로 다시 왔던 길로 되돌아가며 다른 곳으로 나아갈 준비를 한다. $x$에서 다시 $y$로 가고, 이때, $x$는 더이상 방문할 일이 없으므로 ‘4 / 5’이고 $y$또한 더이상 방문할 일이 없으므로 ‘3 / 6’이다. 이렇게 다시 다른 곳으로 나아갈 수 있는 노드까지 간다.

그런데 $u$까지 되돌아가도 다른 노드로 나아갈 수 있는 엣지가 없어서 DFS가 불가능하다. 그러면 여기서 DFS를 끝낸다. 이후 방문하지 않은 노드 중 다시 시작노드를 정해서 DFS를 시작한다. 그 과정은 (m) ~ (p)와 같다.

DFS의 최종 결과는 아래와 같다. start time이 짧은 것이 큰 것의 부모노드이다.

방향그래프(Directed graph)의 DFS 결과를 통해서 그래프의 edge의 성격을 구분할 수 있다.

Tree edge(트리 간선)

DFS의 spanning tree를 이루는 간선
Forward edge(순방향 간선)

트리 간선이 아닌 간선 중, 부모에서 자식으로 향하는 간선. ex) $u \rightarrow x$
Back edge(역방향 간선)

트리 간선이 아닌 간선 중, 자식에서 부모로 향하는 간선. 방향그래프에서 back edge가 존재한다면 이 그래프는 사이클을 가진다. ex) $x \rightarrow v$, 　$z \rightarrow z$
Cross edge(교차 간선)

부모자식 관계가 아닌 정점들간의 간선. ex) $w \rightarrow y$

참고로 무방향그래프(Undirected graph)의 경우 Tree edge와 Back edge만 존재한다.

1-3. 깊이우선탐색(DFS)의 시간복잡도

모든 노드와 엣지를 한번씩은 탐색하므로 $O(\left\vert V \right\vert + \left\vert E \right\vert)$이다.

2-1. 너비우선탐색(BFS. Breath First Search)

시작노드(가장 먼저 생성된 정점)를 방문한 후, 시작 노드에 인접한 모든 노드를 우선 방문하는 그래프 순회기법. 더 이상 방문할 노드가 없으면 그 다음 가까운 인접 노드를 우선 방문함.

2-2. 너비우선탐색(BFS) 방법

너비우선탐색은 큐를 사용한다.

가장 먼저 시작된 정점인 1을 시작노드로 하여 1을 큐에 넣는다(enqueue).
그 다음, dequeue를 해 1을 빼낸 뒤 1의 인접노드(3, 6)을 차례대로 돌며 거리와 부모 정보를 업데이트 한 뒤 다시 큐에 넣는다. 이후, 이번에는 3을 dequeue해 빼낸 뒤 3의 인접노드 (1, 2, 4, 5)를 차례대로 돌며 다시 거리와 부모 정보를 업데이트 하고 큐에 넣는다. 이때, 1은 이미 방문한 노드이므로 이 처리에서 제외한다.

이처럼 노드를 큐에 넣은 뒤, 빼내면서 인접노드를 큐에 넣는 과정을 쭉 반복한다.