열혈 자료구조 - 14.3 그래프의 탐색(1)

그래프에서 탐색

- 어떻게 정점을 한번씩 조회할 수 있을까

- 종류 : 깊이 우선 탐색, 너비 우선 탐색

 

깊이 우선 탐색(Depth First Search)

- 연결된 정점 중 하나를 선택해서 탐색하는 방법

- 먼저 시작 정점에서부터 정점을 하나씩 선택하여 탐색을 시작

- E의 경우 연결되어 있는 D와 C는 이미 탐색을 마쳤으므로 다시 역으로 돌아가면서 탐색할 곳을 찾음

- C와 연결된 F는 탐색하지 않았으므로 F를 탐색

- F도 다시 역으로 탐색할 대상을 찾고 시작 부분까지 되돌아 가고 더이상 탐색할 정점이 없다면 탐색이 종료

 

너비 우선 탐색(Breadth First Search)

- 연결된 정점을 모두 탐색하면서 진행하는 방법

- 탐색한 정점 순서대로 주변을 탐색함