그래프 탐색

Graph Search 그래프 탐색

Depth First Search (깊이 우선 탐색)

• Root 에서 시작해서 다음 branch 로 넘어가기 전에 해당 branch 를 끝까지 탐색
• 현재 정점에서 한 방향으로 가면서 검사하며, 막힌 정점은 포기하고 마지막에 따라온 간선으로 되돌아 간다.
• BFS 보다 간단하지만 느리다.
• 깊이 우선 탐색은 스택(stack), 혹은 재귀를 사용해서 탐색한다.

  어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 안그럼 infinite loop 에 빠질 위험이 있다.

Breadth First Search (너비 우선 탐색)

• 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법
• 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다.
• 두 노드 사이의 최단 경로, 혹은 임의의 경로를 찾을 떄 사용한다.
• 너비 우선 탐색은 큐(Queue)를 사용해서 탐색한다.