DepthFirstSearch
-
[Data Structure] 그래프 순회, 탐색(DFS) - 자료 구조CSE/Data Structure 2016. 4. 16. 10:32
그래프 순회(Graph Traversal) 하나의 정점에서 그래프의 모든 정점을 한 번씩 방문하는 것을 그래프 순회라고 합니다. 탐색 방법에는 '깊이 우선 탐색(DFS)' '너비 우선 탐색(BFS)' 1. 깊이 우선 탐색 DFS(Depth First Search) 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 탐색하다 막히면 가장 마지막 갈림길 간선이 있는 정점으로 돌아와서 다른 방향의 간선으로 탐색을 계속하는 탐색 방법 이 탐색 방법에서는 스택(Stack)을 이용하여서 탐색합니다. 깊이 우선 탐색 과정 1. 초기 배열 visited를 False로 초기화하고 공백 스택 생성 2. 정점 A를 시작으로 깊이 우선 탐색 시작 visited[A] = true; 3. 정점 A에 방문하지 않은 정점 B,..