[Algorithm] 너비 우선 탐색(BFS)이란?

그래프란?

• 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조를 의미합니다.

그래프 탐색이란?

• 하나의 정점으로부터 시작하여, 차례대로 모든 정점들을 한 번씩 방문하는 것을 의미합니다.

너비 우선 탐색(BFS, Breadth First Search)이란?

• 루트 노드 또는 임의의 노드에서 시작하여, 일정 노드와 인접한 노드들을 우선으로 탐색하는 방법입니다.
• 주로, 어떤 두 노드 사이의 최단 경로를 구할 때 사용되며,
• 주로, 큐(Queue)라는 자료구조를 사용해 구현됩니다.

너비 우선 탐색 예제

• BFS 는, 아래와 같은 간단한 알고리즘에 의해 작동됩니다.

  • 큐에서 하나의 노드를 꺼냅니다.
  • 해당 노드와 연결된 노드들 중, 방문하지 않은 노드들을 큐에 삽입하며, 방문 처리합니다.
  • 반복합니다.

• 아래 그래프를 통해, 간단한 너비 우선 탐색 예제를 다뤄보겠습니다.

  

• 우선, BFS 시작 시, 시작 노드 1 은 큐에 삽입한 뒤, 방문 처리합니다.

  

• 큐에서 1 을 꺼낸 뒤, 1 과 인접한 노드들 중, 방문하지 않은 노드들(2, 3)을 큐에 삽입하고, 방문 처리합니다.

  • 상단의 첫 번째 줄은 꺼낸 노드, 두 번째 줄은 큐를 의미합니다.

    

• 큐에서 2 를 꺼낸 뒤, 2 와 인접한 노드들 중, 방문하지 않은 노드들(4, 5)을 큐에 삽입하고, 방문 처리합니다.

  

• 큐에서 3 을 꺼낸 뒤, 3 과 인접한 노드들 중, 방문하지 않은 노드들(6, 7)을 큐에 삽입하고, 방문 처리합니다.

  

• 모든 노드가 방문 처리 되었다면, 큐에 남은 노드들을 전부 꺼냅니다.

  

• 큐에서 꺼내진 노드 순서는 1, 2, 3, 4, 5, 6, 7 입니다.

• 즉, 1 부터 가까운 노드들부터 탐색이 이루어졌다는 뜻이며, 이를 너비 우선 탐색이라고 합니다.

참고

• https://blog.naver.com/ndb796/221230944971
• https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
• https://velog.io/@sukong/알고리즘-개념-너비우선탐색BFS-lp8zywtn
• https://velog.io/@lucky-korma/DFS-BFS의-설명-차이점
• https://blog.naver.com/ndb796/221230944971
• https://coding-factory.tistory.com/612