[자료구조] 그래프 탐색

그래프는 정점(vertex)과 간선(edge)으로 구성된 한정된 자료구조이다.

그래프를 탐색한다는 것은, 하나의 정점으로 시작하여 차례대로 모든 정점을 한 번씩 방문하는 것을 말한다.


/* 그래프 탐색 종류 */

깊이 우선 탐색(DFS, Depth-First Search)
: 최대한 깊이 이동한 뒤, 더 이상 이동할 곳이 없을 경우, 옆으로 이동
 
너비 우선 탐색(BFS, Breadth-First Search)
: 최대한 넓게 이동한 뒤, 더 이상 이동할 곳이 없을 경우, 아래로 이동
 
 

ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ

 

깊이 우선 탐색	너비 우선 탐색
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ
ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ	ⓐ 　／　　｜　　＼ ⓑ　―　ⓒ　―　ⓓ 　＼　　＼　　／ 　　ⓔ　―　ⓕ 　　　　　／ 　　　　ⓖ