Depth First Search (1) 썸네일형 리스트형 109. Depth First Search 그래프 탐색(Graph Traversal)은 트리의 탐색과는 다르다. 서브트리와 같은 개념이 그래프에는 존재하지 않는데다 노드들 사이의 경로도 여러 개 존재할 수 있으므로 트리의 탐색 방법을 그래프에 그대로 적용하는 것은 무리이다. 그래서 그래프는 트리와 다른 탐색 방식을 사용하며, 대표적인 방식은 두 가지가 있다.깊이 우선 탐색(Depth First Search)은 노드를 탐색하고 그 노드와 인접한 노드을 차례로 탐색하는 과정을 재귀적으로 반복하는 탐색 방법이다. 현재 노드에서 탐색할 수 있는 노드를 최대한 탐색하는 방식이라고 생각하면 간단하다. 인접한 노드가 여러 개 있을 때 그 노드들의 탐색 순서에 대한 규칙은 따로 없으며 문제 상황에 맞게 정하면 된다.아래와 같은 그래프가 존재할 때 노드 $\te.. 이전 1 다음
