너비 우선 탐색
-
그래프의 너비 우선 탐색알고리즘 이론/알고리즘 구현 2019. 9. 3. 02:31
너비 우선 탐색(BFS)는 시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘이다. 너비 우선 탐색은 깊이 우선 탐색과는 달리 발견과 방문이 같지 않다. 1. 아직 발견되지 않은 상태 ( 큐에 넣기 전) 2. 발견되었지만 아직 방문되지 않은 상태 ( 큐에서 대기 중) 3. 방문된 상태 ( 큐에서 꺼낸다 ) 너비 우선 탐색이 시작점인 0 을 방문하면 정점 1 3 4 8이 목록에 추가 된다. 이들은 모두 0에서 간선 하나로 연결되기에 어느 정점을 먼저 꺼내도 상관 없다. 이 중 1을 꺼내 방문했다고 하면 2가 목록에 추가 된다. 이때 2는 자신보다 먼저 목록에 추가된 남은 정점 3 4 8이 방문되기 전까지는 결코 방문되어서는 안된다. 이를 구현하는 방법은 목록에 먼저 넣은 정점을 항상 먼저 꺼내야 하..