[Algorithm] BFS 와 DFS

BFS 와 DFS

 

용어

 

Discover : Vertex를 처음 방문했을 때 vertex를 discover 했다고 함

Explore : edge를 처음 방문했을 때

Finish : 자신의 노드 뿐만 아니라 연결된 노드들 모두 discovered 되었을 때 그 노드는 Finish 되었다고 함

discover time : discover 한 시간 

finish time : finish한 시간

 

discover 되기 이전의 vertex 색깔 - 흰색

discover 되었지만 연결 되어있는 vertex 중에 discover가 안된 vertex가 있는 경우 - 회색.

discover 되었고 finish 되었을 경우 – 검정색

 

위의 색깔로 discover or finish 되었는지 나타내어 과정을 가시화 한다.

 

BFS

 

탐색 방법

 

◎Queue 사용

◎특정 노드를 탐색하고 그 노드의 주변 노드들을 모두 탐색

◎주변 노드 탐색이 끝났다면 주변 노드의 주변 노드들을 탐색

 

Code

 

코드 설명

 

D[u]는 u까지의 distance. 무한대로 초기화

파이[u]는 u의 조상

Color[s]는 시작할 때 방문 했으므로 Gray로 초기화 .

Distance[s]는 자신과 자신과의 거리이기 때문에 0

 

Queue를 이용하여 주변 vertex들을 순서대로 discover할 수 있다.

discover 된 vertex들은 또 Queue에 들어간다.

주변 vertex들이 다 discover 되면 Queue에 있는 vertex들을 꺼내어 그들의 주변 vertex들을 discover한다.

 

 Example

 

 

문제

 

과정 1 과정 2 과정 3

 

과정 4 과정 5 과정 6

 

과정 7 과정 8 과정 9

 

과정 10 과정 11

 

시간 복잡도

 

 

---

 

DFS

 

탐색 방법

 

◎ Stack을 이용 한다

◎가능한 한 깊이 들어가는 방법

◎ 만약 더 discover 할 수 있는 노드가 없다면 가장 최근에 discovered한 노드를 찾아 나가는 방법이다. (Stack을 이용한 Backtracking)

 

Code

 

코드 설명

 

일단 이 함수에서는 Stack을 사용하지 않고 Recursion을 사용한다.

Recursion으로 함수 자체를 Stack처럼 사용하는 것이라서 이 방법이 가능하다.

 

D[v] : 노드 v 의 discover time

F[v] : 노드 v 의 finish time

시간 복잡도는 세타(V+E)

 

 

Example

 

 

 

 

 

 

 

결과

 

노드 속에 D[v] | F[v] 을 나타냄

 

D[v]가 11인 노드는 연결이 끊겨서 새로운 source vertex로 맨 오른쪽 vertex가 선택 되었다.

 

 

D[u]와 f[u] 에 관한 parenthesis therorem

 

 

1)

이것이 성립하는 경우 vertex u와 v는 parent-descendant 관계가 아니다.

 

 

2)

이 것이 성립하는 경우 vertex v 는 u의 descendant 이다.

 

 

 

3)

u는 v의 descendant이다.

 

 

4)

불가능한 경우이다.

 

 

DFS에서의 edge들

Back edge , forward edge , cross edge는 위의 조건을 만족하면서 tree edge가 아닌 edge이다.

 

 

예시와 함께 보자

 

 

Tree edge

back edge(파란색)

Forward edge( 초록색 )

Cross edge(보라색)