그래프를 구성하는 모든 꼭짓점(Vertex)들을 체계적으로 방문하여 탐색하는 자료 검색 방법.
일반적으로 깊이 우선 탐색(Depth First Search)과 너비 우선 탐색(Breadth First Search) 두 종류가 많이 사용된다.
(전위 운행법, 중위 운행법, 후위 운행법 등은 이 글에서는 생략한다.)
한 노드를 시작으로 인접한 다른 노드를 탐색하기를 반복하여 끝까지 탐색하면 다시 상위 레벨의 다른 노드에서 탐색을 이어가며 모든 Vertex를 방문한다.
'깊이 우선 탐색'이라는 말 그대로 깊은 곳으로 우선 탐색을 진행하는 방식.
First In Last Out 방식의 Stack과 중복 처리를 방지하기 위해 이미 접근했던 Vertex를 저장하는 방식을 활용한다.
A
를 stack
과 seen
에 각각 저장
stack = [A]
,seen = {A}
A
는 stack
에서 제거 후 A
와 인접하는 vertex들 B, C, D
를 stack
과 seen
에 각각 저장
stack = [D, C, B]
,seen = {A, B, C, D}
stack
에 마지막으로 저장된 B
를 탐색 후 제거하며 B
와 인접하는 A, C, E
중 seen
에 속하지 않은 E
를 stack
과 seen
에 각각 저장
stack = [D, C, E]
,seen = {A, B, C, D, E}
stack
에 마지막으로 저장된 E
를 탐색 후 제거하며 E
와 인접하는 B, G
중 seen
에 속하지 않은 G
를 stack
과 seen
에 각각 저장
stack = [D, C, G]
,seen = {A, B, C, D, E, G}
stack
에 마지막으로 저장된 G
를 탐색 후 제거하고 G
와 인접하는 E
는 이미 seen
에 저장되어 있으므로 따로 처리하지 않음
stack = [D, C]
,seen = {A, B, C, D, E, G}
stack
에 마지막으로 저장되어 있는 C
를 탐색 후 제거하며 C
와 인접하는 A, B, D, F
중 seen
에 속하지 않은 F
를 stack
과 seen
에 각각 저장
stack = [D, F]
,seen = {A, B, C, D, E, F, G}
stack
에 마지막으로 저장된 F
를 탐색 후 제거하고 F
와 인접하는 C, D
는 이미 seen
에 저장되어 있으므로 따로 처리하지 않음
stack = [D]
,seen = {A, B, C, D, E, F, G}
stack
에 마지막으로 저장된 D
를 탐색 후 제거하고 D
와 인접하는 A, C, F
는 이미 seen
에 저장되어 있으므로 따로 처리하지 않음
stack = []
,seen = {A, B, C, D, E, F, G}
stack
에 남은 것이 없으므로 탐색 종료.
A, B, E, G, C, F, D
한 노드를 시작으로 인접한 다른 노드를 탐색하기를 반복하여 같은 레벨의 노드 탐색이 끝나면 하위 레벨의 다른 노드에서 탐색을 이어가며 모든 Vertex를 방문한다.
'너비 우선 탐색'이라는 말 그대로 옆으로 우선 탐색을 진행하는 방식.
First In First Out 방식의 Queue와 중복 처리를 방지하기 위해 이미 접근했던 Vertex를 저장하는 방식을 활용한다.
탐색 시작점 A
를 queue
와 seen
에 각각 저장
queue = [A]
,seen = {A}
A
의 탐색을 마치고 queue
에서 제거 후 인접한 vertex들 B, C, D
를 queue
와 seen
에 각각 저장
queue = [B, C, D]
,seen = {A, B, C, D}
queue
의 맨 처음 값인 B
를 탐색 후 제거하며 인접한 A, C, E
중 seen
에 속하지 않은 E
를 queue
와 seen
에 각각 저장
queue = [C, D, E]
,seen = {A, B, C, D, E}
queue
의 맨 처음 값인 C
를 탐색 후 제거하며 인접한 A, B, D, F
중 seen
에 속하지 않은 F
를 queue
와 seen
에 각각 저장
queue = [D, E, F]
,seen = {A, B, C, D, E, F}
queue
의 맨 처음 값인 D
를 탐색 후 제거하며 인접한 A, C, F
는 이미 seen
에 속해 있으므로 따로 처리하지 않음
queue = [E, F]
,seen = {A, B, C, D, E, F}
queue
의 맨 처음 값인 E
를 탐색 후 제거하며 인접한 B, G
중 seen
에 속하지 않은 G
를 queue
와 seen
에 각각 저장
queue = [F, G]
,seen = {A, B, C, D, E, F, G}
queue
의 맨 처음 값인 F
를 탐색 후 제거하며 인접한 C, D
는 이미 seen
에 속해 있으므로 따로 처리하지 않음
queue = [G]
,seen = {A, B, C, D, E, F, G}
queue
의 맨 처음 값인 G
를 탐색 후 제거하며 인접한 E
는 이미 seen
에 속해 있으므로 따로 처리하지 않음
queue = []
,seen = {A, B, C, D, E, F, G}
queue
에 남은 것이 없으므로 탐색 종료.
A, B, C, D, E, F, G