[이산수학] 그래프의 탐색

 

탐색(Search)

 

1. 맹목적 탐색 (Blind search)

 

1) 깊이 우선 탐색 (Depth First Search : DFS)

시작하는 정점에서 출발해서 인접한 정점 중 아직 반문하지 않은 정점을 계속 찾아 방문하는 방법.

재귀 알고리즘을 이용해 쉽게 구현 가능하며 이 경우 스택(Stack)을 사용한다.

 

그래프 G

 

위와 같이 주어진 그래프 G가 있을 경우 DFS는 아래와 같이 방문하게 된다.

탐색은 A, B, D, H, E, C, F, G 순으로 이루어진다.

 

DFS의 결과

 

이 때, 방문 과정 중 인접한 모든 정점을 이미 탐색한 경우 가장 최근 방문했던 정점으로 돌아가는 것을 Back Tracking 라고 한다.

 

2) 너비 우선 탐색 (Breadth First Search : BFS)

시작점 A를 방문후 A에 인접한 모든 정점을 차례대로 방문 후 더 이상 방문할 정점이 없을 경우 인접한 정점 가운데 가장 처음에 방문한 정점에서 위와 같이 반복하는 과정이며, 레벨 단위로 이루어진다.

DFS와는 달리 큐(queue)를 사용하고 탐색은 A, B, C, D, E, F, G, H 순으로 이루어 진다.

 

BFS의 결과

 

 

2. 경험적 탐색 (Heuristic search)

경험적 탐색이란 실생활에서 예를 들자면 비가 온다는 날씨에 '우산을 가져간다', '가져가지 않는다' 라는 생각을 하는 것이 맹목적인 방법이며, 비의 형태를 경험해보고 '어느정도의 비는 맞아도 되겠다', '우산을 가져간다'라는 최적화 된 방향으로 생각하는 것이다. 간단하게 말하자면 어떤 문제를 탐색할 때 최소, 최대가 아닌 최적의 방법으로 탐색하는 것을 말한다.