[강의노트] 그래프 순회 -2 (BFS)

그래푸 순회 - 2(BFS)

지난 포스트에서는 DFS에 다루어보았고, 이번에 배울것은 BFS 너비우선탐색이다.

마찬가지로 그래프 순회 기법이다.

 

 

BFS - 너비우선탐색

너비우선탐색에서 가장 핵심적인 단어를 꼽자면 level 이라고 생각한다. 이 얘기는 뒤에 몇번 더 언급하겠다.

 

BFS는 트리의 level 별로 순회를 한다. 즉 트리에서 루트노드를 기준으로 자식노드로 계속 내려가는 것을 깊이우선탐색이라고 한다면, 기준노드에서 형제노드를 우선적으로 탐색하는 것이 너비우선탐색이다.

DFS와는 탐색의 방향성 측면에서 어떻게 보면 반대의 개념이라고도 생각할 수 있다.

 

BFS를 확장해서 해결 가능한 문제를 살펴보자.

두개의 주어진 정점 사이의 최소 간선을 사용하는 경로를 찾을 수 있다고 한다. 그래프 내 싸이클을 탐색하는 문제는 

BFS와 DFS를 모두 활용할 수 있지만, BFS는 최소 간선을 사용하는 경로를 탐색하는데에 유리하다는 점 기억하자.

 

깊이우선탐색은 선위순회와 유사너비우선탐색은 레벨순회와 유사

 

 

BFS 수도코드

재귀알고리즘이었던 DFS와 다르게 BFS 는 비재귀알고리즘이다.

수도코드를 살펴보자.

먼저 BFS 알고리즘에서는 그래프의 정점과 간선을 초기화하고, 각 정점에 대해 방문하지않은 정점이라면 BFS1 알고리즘을 호출한다. 

BFS1 알고리즘의 핵심은 level 이다. 리스트를 생성해서, 인접 간선들을 레벨별로 리스트에 삽입한다.

 

상세한 내용은 수행 예시를 통해 알아보자.

후향간선 대신 교차간선이라는 이름이 등장했다.

예시에서는 정점A가 기준이 되는데 이해하기 쉽게 강의에서는 정점A를 세종대역으로 예시를 들어주셨다.

세종대역에 대한 부착간선 B,C,D는 한 정거장만 이동하면 갈 수 있는 역을 의미한다. B,C,D는 level 1에 해당하는 리스트1에 삽입한다.

 

L1에 B,C,D가 삽입된 후에, 정점B에서 C는 이미 방문한 역이다. 따라서 교차간선으로 표시한다. 다음 인접간선인 E는 리스트2에 삽입한다.

그 후 정점C에서 D는 이미 방문한 역이다. 따라서 교차간선으로 표시한다. E는 이미 방문한 역이다. 따라서 교차간선으로 표시한다. F는 방문하지않은 역이기때문에, 간선을 tree로 설정하고, 정점F를 방문표시로 설정한다.

 

위에서 설명한 과정이다. 딱히 어렵다고 느껴지지않고 level 별로 리스트에 분류한다는 것을 잘 기억하면 될 것 같다

 

정리하면 BFS는 루트노드(또는 임의의 다른 노드)에서 시작해서 인접 노드를 먼저 탐색하는 방법.

두 노드 사이의 최단 경로를 찾을 때 사용된다. BFS를 구현할 때는 선입선출 원칙인 Queue를 이용해서 탐색한다.

 

 

아래의 입력예시를 통해 결과를 살펴보면 

front 변수는 그래프에서 현재 노드를 의미하고

rear 변수는 현재 노드가 방문한 가장 최근 노드를 의미한다는 것을 알 수 있다.

BFS vs DFS 의 미로 순회

BFS는 용감하다. 갈림길에서도 일단 끝까지 들어가고 본다.

DFS는 겁이 많다. 가까운 길 부터 모두 확인하면서 순회한다.

 

 

BFS의 속성

BFS1(G,V)는 Gv의 모든 정점과 간선을 방문한다. 즉 연결되어잇는 덩어리 그래프의 모든 정점과 간선을  방문

 

 

BFS 분석

정점이 리스트에 삽입(addLast)되는 과정은 정점의 개수 n * O(1) 이므로 O(n), 즉 영향을 안줌

 

**

인접행렬로 구현하면 시간복잡도가 어떻게 될까?

 

 

BFS 분석

비트리 간선

알고리즘에서 간선의 상태를 표시할때, tree 외에 후향간선(back)과 교차간선(cross)가 등장했었는데 각각의 개념에 대해서 한번 더 상세히 다루어보자.

• DFS의 후향간선의 경우 모든 간선은 그 부모 노드를 가리킨다.
• BFS의 경우 형제와, 조카를 가리킨다. 여기서 조카는 형제의 자식을 말한다.