[알고리즘] 너비 우선 탐색(Breadth First Search : BFS) 이란?

 

너비 우선 탐색, BFS 란?

• BFS는 그래프 탐색 방법 중 하나로 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
• 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.
• BFS는 큐(Queue) 자료구조를 이용해 구현한다. 큐 자료구조에 대해 알고싶다면 다음 포스팅 참고

[자료구조] 큐(Queue)의 개념, 이해 | c언어 큐 연결리스트로 구현, 소스코드

 

BFS의 과정

BFS 는 다음과 같은 과정을 거치게 된다.

 

1. 시작정점을 방문하고 큐에 넣는다.
2. 큐에서 가장 앞의 노드를 빼고 해당 노드의 인접 정점을 방문하지 않았다면 모두 방문하고 큐에 넣는다.
3. 큐가 빌 때까지 2를 반복 한다. 

가장 먼저 시작 정점을 방문하게 되고, 큐에 시작정점을 넣는다.

큐의 가장 앞의 노드를 빼고(A노드) 해당 노드의 인접 노드를 조사한다.

 

B노드는 방문하지 않았으므로 방문하고 큐에 넣는다.

C노드는 방문하지 않았으므로 방문하고 큐에 넣는다.

E노드는 방문하지 않았으므로 방문하고 큐에 넣는다.

 

큐의 가장 앞의 노드를 빼고(B노드) 해당 노드의 인접 노드를 조사한다.

 

A노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

C노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

 

큐의 가장 앞의 노드를 빼고(C노드) 해당 노드의 인접 노드를 조사한다.

 

B노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

A노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

D노드는 방문하지 않았으므로 방문하고 큐에 넣는다.

 

큐의 가장 앞의 노드를 빼고(E노드) 해당 노드의 인접 노드를 조사한다.

 

A노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

D노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

C노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

 

 

큐의 가장 앞의 노드를 빼고(D노드) 해당 노드의 인접 노드를 조사한다.

 

C노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

E노드는 이미 방문했으므로 방문하지 않고 큐에 넣지 않는다.

 

큐가 비었으므로 BFS를 종료한다.

 

---

BFS 의 장점

• 노드의 수가 적고 깊이가 얕은 경우 빠르게 탐색할 수 있다.
• 단순 검색 속도가 DFS 보다 빠르다.
• 너비를 우선 탐색하므로 답이 되는 경로가 여러개여도 최단경로를 보장한다. 

 

BFS의 단점

• 큐에 다음에 탐색할 정점들을 저장해야 하므로 이에 따른 저장공간이 많이 필요하다.
• 노드의 수가 많아지면 탐색할 노드 또한 많아져 시간이 오래 걸린다.

 

깊이 우선 탐색(DFS)가 궁금하다면 다음 포스팅을 참고하자.

[알고리즘] 깊이 우선 탐색, DFS(Depth First Search)알고리즘이란?| C언어 DFS 구현

 

 

---