BreadthFirstSearch
-
[Data Structure] 그래프 순회, 탐색(BFS) - 자료 구조CSE/Data Structure 2016. 4. 16. 11:39
그래프 순회(Graph Traversal) 2. 너비 우선 탐색 BFS(Breadth First Search) 시작 정점으로부터 인접한 정점들을 모두 차례로 방문하고 나서방문했던 정점을 시작으로 다시 인접한 정점들을 차례로 방문하여 가까운 정점들을 번저 방문하는 방법 인접한 정점들에 대해 차례로 다시 너비 우선 탐색을 반복해야 하므로 FIFO 구조를 갖는 Queue를 사용합니다. 너비 우선 탐색 과정 초기 상태 visited를 초기화하고 공백 큐 생성 1. 정점 A를 시작으로 너비 우선 탐색 시작 visited[A] = true;A 방문 2. 정점 A에서 방문하지 않은 모든 인접 정점 B, C를 방문하고 큐에 enQueue visited[B & C] = true;B & C 방문enQueue(B & C);..