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

1. 개념

'너비 우선 탐색' 깊게보다 넓게 탐색. 시작 노드에서 인접한 노드를 먼저 탐색하는 방법

--> 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때

 

 

2. 방법

큐(Queue, FIFO)를 사용해서 구현하면 된다.

1) 우선 방문해야할 정점을 넣을 queue 선언, 방문 정점(v)으로 초기화

2) 현재 방문한 곳은 노드 방문 처리

3) queue 안에 데이터 있는 동안 반복

-1) queue에서 pop해서 방문 정점(v)에 넣고 출력

-2) 반복문 실행해서 방문 정점과 인접한 정점 찾아서 queue에 append

--> 방문하지 않았고, 현재 방문 정점인 v와 인접해있으면 queue에 넣어주고, 방문처리 해준다.

 

3. 예제

 

 

4. dfs와의 비교

n에 대한 반복문을 실행하면서 방문하지 않았고, 현재 방문 정점과 인접해있으면

해당 정점에 대한 재귀함수를 수행하는 게 dfs,

해당 정점을 queue에 넣어주는 게 bfs