알고리즘 공부<9> - 너비우선탐색

오늘은 그래프 탐색에 대해 공부해보자

1. Graph-Searching Algorithms

그래프 탐색은 시스템적으로 그래프의 간선들이 꼭지점들을 찾아가는 것이다.

그래프의 구조를 사용하는데 

• 너비 우선 탐색
• 깊이 우선 탐색

이 2가지가 있다. 먼저 너비 우선 탐색에 대해 알아보자

2. Breadth-First Search

탐색할 그래프 G는 방향 무방향 둘다 상관 없으며 출발점 꼭지점은 꼭지점 집합에 속한다.

d[v]는  s  - > v 로 가는 가장 짧은 경로를 의미한다.

d[v] = 무한대  는   아직 s가 v로 도달하지 못한 것을 의미한다.

ㅠ[v] = u 는 s가 v로 가는 가장 짧은 경로중 마지막 간선을 의미한다. 즉 u는 v의 이전 노드이다.

BFS를 그림으로서 한번 보기전에 간단한 색깔에 대해서 정의하고 가자

그림과 함께보면 어느정도 이해가 갈것이다. 이를 탐색하는 과정은 큐 와 비슷한다 찾으려는 노드들을 큐에 넣어놓고 이후에 하나씩 앞에서부터 찾기 떄문이다

먼저 1행부터 8행 까지는 각각의 노드 와 시작 노드를 초기화 해주는 부분으로 노드의 개수를 V라 할때 노드의 개수만큼 초기화 하므로 빅오 O(V)이다.

이후 9행에서 출발점s는 큐에 들어가게 된다.

10행에서 큐가 공집합이 아닐때까지 돌게되므로 모든 노드의 대하여 큐에 넣어다 뺴는것을 반복하므로 노드의 개수인 V번 수행하게 된다.

이후 11에서 큐에 있는 노드들을 뺀다. 

12 행에서는 각 노드와 인접해 있는 노드에 대해서 수행되므로 모든 노드에 대해서 자신과 인접한 노드의 개수만큼 수행하므로 간선의 개수만큼 수행됨을 알 수 있다.

13행 인접한 노드가 하얀색 즉 발견되지 않은 노드인경우 이하 내용이 수행된다.

gray색으로 바꾸고 현재 노드 u와  u의 인접 노드는 하나 차이나므로 거리를 1 증가시킨값을 넣어주고 인접노드의 이전 노드로 u를 넣어주면 된다.

이후 이 인접노드v를 큐에 넣어주면된다. 이 과정을 간선의 개수만큼 수행하게되며 찾고자 하는 노드 u의 색이 전부 검정색이 될때 끝나게 된다.

이 while구문에 대한 빅오를 구하면 각 노드별 인접 노드의 개수가 다르므로 곱하기가 아닌 모든 간선개수를 더한 값이다. 즉 간선의 집합을 E라 할때 O(E)가 된다

따라서 전 과정의 빅오는 O(V+E)가 된다.

이와 같이 인접 리스트만큼 옆으로 찾아가므로 너비우선탐색이라고 하는것이다.

그리고 이 그래프를 펼쳐보면 사이클이 없는 그래프이므로 트리구조를 이룬다는것을 알 수 있다.