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

깊이우선 탐색(DFS, Depth-First Search)

루트 노드에서 시작해서 연결된 노드의 가지 하나의 최하단 노드까지 탐색 하고, 그다음 노드의 최하단까지 탐색한다. 전체적으로 깊게 탐색 한다고 해서 깊이 우선 탐색이라불린다.

 

특징

• 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
• 전위 순회(Pre-Order)를 보함한 다른 형태의 트리순회는 모두 DFS의 한 종류이다.
• 그래프 탐색의 경우 반드시  어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않을경우 무한루프에 빠질 위험이 있다.

 

너비우선탐색(BFS, Breadth-First Search)

루트 노드에서 시작해 탐색한 노드의 가장 인접한 노드들부터(좌우로) 먼저 탐색 한다음, 그 다음 자식 노드들을 넓게 탐색한다.

 

특징

• 직관적이지 않은 면이 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 그래프 탐색의 경우 반드시  어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않을경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.