BFS(Breadth-First Search) 알고리즘

BFS (너비 우선 탐색) 정의 

- 루트 노드 또는 임의의 노드에서 시작해서 인접한 노드를 먼저 탐색하는 방법 

 

동작 과정 

1. 먼저 깊이가 1인 노드들(1번,2번,4번)을 먼저 방문하게 된다 

2. 방문한 노드는 Queue에 넣어서 보관하게된다 

3. 깊이가 1 인 경로를 전부 탐색하면 큐에서 하나씩꺼내서 다음 깊이인  깊이2  노드를 방문한다 

4. 1 ~ 3 과정 반복 

BFS 동작 과정 - https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

 

 

BFS 특징

• 직관적이지 않은 면이 있다.
  • BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
• BFS는 재귀적으로 동작하지 않는다.
• 이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
  • 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
• BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
  • 즉, 선입선출(FIFO) 원칙으로 탐색
  • 일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
• ‘Prim’, ‘Dijkstra’ 알고리즘과 유사
  
  

 

BFS 구현과 활용은 https://devureak.tistory.com/33 링크를 참고