[알고리즘] BFS (너비 우선 탐색)

BFS(Breadth First Search, 너비 우선 탐색) 또한 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘입니다. 

현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점들을 발견하면, 그 간선을 통해 방문하지 않은 정점들을 자료구조 큐에 넣습니다. 그리고 큐의 front 정점을 방문하고 pop합니다. 

또 해당 정점에서 인접한 간선을 검사해 방문하지 않은 정점들을 큐에 넣고 방문하는 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없으면 종료합니다. 즉, 과정을 반복하다가 큐에 더 이상 정점이 존재하지 않을 때까지 실행하여 그래프의 모든 정점을 방문하는 알고리즘입니다. 

결과적으로 이어진 것을 보면 최소 간선으로 이동할 수 있는 경로가 됩니다. 

 

(출처: 삼성 코드 그라운드)

 

 

이미지 출처: 삼성 코드 그라운드

 

[시간복잡도] 

O(V+E)

 

[슈도코드]

 

출처: 학교 알고리즘2 수업시간

 

d[]: distance

p[]: parent

V[]: graph (인접 리스트로 구현합니다.)

 

[C코드]