Algorithm Study (DFS, BFS)

이전내용 링크

 

완전탐색

정렬

문자열

배열,리스트

스택,큐

해시

힙

 

 

탐색 기법으로 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있다.

 

12. 깊이우선탐색(DFS)

시작노드(혹은 루트노드) 에서 시작하여 탐색을 진행한다.

하나의 경로를 깊게 탐색한다.

깊이가 무한한 트리의 경우 잘못된 방향으로 탐색을 시작하면 무한루프에 빠질 수 있다(이를 방지하기 위해 깊이 제한을 두기도 한다)

깊이 제한까지 도달할때까지 목표 노드가 발견되지 않으면 부모 노드로 돌아와 재탐색을 진행한다(백트래킹)

 

스택 자료구조를 사용하여 다음 방문할 노드의 정보를 저장한다.

 

장점

• 저장공간의 수요가 비교적 적다
• 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있다.

 

단점

• 해가 없는 경로에 빠질 가능성이 있다.
• 구해진 해(경로)가 최단경로임을 보장하지 않는다.

 

 

13. 너비우선탐색(BFS)

시작노드(혹은 루트노드)에서 시작하여 탐색을 진행한다.

인접한 모든 정점을 우선 방문한다.

 

장점

• 구해진 해(경로)가 최단 경로임을 보장한다.

 

단점

• 경로가 매우 길 경우 탐색 가지수가 급격히 증가하여 많은 저장공간을 필요로 한다.
• 해가 존재하지 않을때 유한그래프의 경우 모든 그래프를 탐색한 후에 실패한다.
• 무한그래프의 경우 해를 찾지도 못하고 끝내지도 못한다.

 

큐 자료구조를 사용하여 다음 방문할 노드의 정보를 저장한다.

 

BFS/DFS 모두 인접행렬, 인접리스트를 사용하여 구현할 수 있다.