자료구조 그래프 Graph Traversing

그래프를 탐험하는 두 가지 방법 

DFS   |   BFS

Depth-first Search    | Breadth-first Search

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

그래프를 탐험하는 것은 Sequential 하지 않기 때문에 알고리즘이 필요하다. 

DFS ( Depth-First Search for Digraph ) 

깊이 우선 탐색이라 불리며 임의의 한 정점을 잡고 재귀적으로 갈 수 있는 모든 정점들을 가 볼 때 까지 가보는 것

용어 정리

visited node : 이미 처리가 끝난 노드로 더이상 이 노드에 대해 처리할 필요가 없다

unvisited  node : 아직 한번도 접근되지 않은 노드로 처리 되어야 한다.

unvisited = 노랑 / visited = 검정

자기자신을 visited 하고 갈 수 있는 녀석을 기점으로 다시 재귀적으로 시작,

더이상 갈수 없으면 RETURN 

정말 단순하게 말하면 이게 끝이다. 

BFS ( Breadth-First Search for Digraph ) 

너비 우선 탐색으로 Queue를 이용한다. 깊이가 1인 정점들에 대해 모두 visit 후 깊이가 2인 정점들에 대해, 3인 정점들에 대해 ... 의 순서로 처리하는 방식

임의의 정점을 시작으로 가까운정점 -> 먼 정점으로 탐색의 범위를 점점 넓히게 된다.

나 자신에 대해 Visit 수행 후, 나로부터 갈 수 있는 녀석들을 모두 Queue에 push,

그리고 POP ( 나 자신이 삭제되게 될것이다. )

더이상 Queue에 아무것도 남지 않으면 탐색 끝

그림으로 이해하자 

Queue에 들어가 있는 것 : 회색

Visit 됨 : 검은색

Unvisited : 흰색 

 

앞서 언급 됬었던 Strongly Connected Component를 

찾기 위한 모험은

http://jason9319.tistory.com/98

이곳에 아주 친절히 잘 나와 있다.