BFS

BFS (Breath First Search)

• 그래프 탐색 알고리즘으로, 그래프탐색이란 한 정점에서 시작하여 탐색 조건에 맞는 노드를 찾을때까지 모든 노드를 방문하는 방법입니다.
• 너비 우선 탐색으로 모든 Branch의 같은 깊이의 노드들을 번갈아 가며 탐색을 하게 됩니다.
• FIFO구조인 큐로 구현 가능합니다.

장점
장점 단순검색 속도가 DFS에 비해 빠른편입니다.
깊이에 관계없이 최단 경로를 찾을 수 있습니다.

단점

다음에 탐색할 노드들을 모두 큐에 담아 두기 위해서는 자원이 많이 필요합니다.

 

과정

 

※다음과 같은 그래프의 정점 1에서 모든 노드를 탐색 스택을 이용한 BFS를 하는 과정이고,

한번 방문한 노드는 방문처리가 되어 다시 방문 할 수 없다고 가정합니다.

아래쪽의 큐의 변화와 함께 보시면 이해가 편합니다.

(오른쪽에서 데이터가 들어와서 왼쪽으로 나갑니다)

노드 1을 방문하고 인접한 노드를 조사하여 모두 큐에 추가합니다.

큐

2

5

 

큐의 가장 앞에 있는 노드 2를 방문하고 인접한 노드를 조사하여 모두 큐에 추가합니다.

큐

5

3

큐의 가장 앞에 있는 노드 5를 방문하고 인접한 노드를 조사하여 모두 큐에 추가합니다.

큐

3

6

7