[알고리즘] BFS에 대해 알아봅시다. - I am yumida

그래프의 각 정점을 방문하는 그래프 탐색에는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)가 있습니다. 

 

오늘은 BFS에 대해서 알아보겠습니다.

 

BFS는 임의의 정점에서 시작해서 인접한 정점을 먼저 탐색하는 방법으로, 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

 

두 정점 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택합니다.

 

BFS의 특징은 어떤 정점을 방문했었는지 여부를 반드시 검사 해야 하며 이를 지키지 않을 경우 무한루프에 빠질 위험이 있습니다. 따라서 방문한 정점들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용합니다.

BFS 알고리즘을 먼저 보여드린 후, Python으로 구현한 코드를 제시하겠습니다.

 

1. BFS 알고리즘 - 순서

 

1. 시작 정점을 방문한 후 방문된 정점을 큐에 삽입합니다.(방문한 정점 체크)
2. 시작 정점의 이웃 정점을 모두 방문할때까지 방문된 정점을 큐에 삽입하는 과정을 반복합니다.
3. 큐에서 꺼낸 정점을 방문합니다.
4. 큐에서 꺼낸 정점과 인접한 정점들을 모두 방문합니다.
5. 이 때, 인접한 정점 중 새로 방문되는 점이 있다면, 큐에 삽입합니다.
6. 만약, 인접한 정점 중 새로 방문되는 점이 없다면, 큐에 삽입하는 과정 없이 [과정 3]으로 돌아갑니다.
7. 큐가 빈 공간이 될 때까지 [과정 3~6] 을 반복합니다.

 

2. BFS 알고리즘 - 예시

 

우선 그래프는 [그림 1]과 같습니다.

왼쪽은 그래프 그림, 오른쪽은 그래프 수식입니다. (수식에서 1: set([3,4])는 1은 3과 4를 가리킴을 의미합니다)

 

[그림 1]

아래는 BFS가 진행되는 과정입니다.

과정은 (1)부터 (6)으로 구성됩니다. 초록색 동그라미는 현재 머무는 정점, 파란색 동그라미는 이미 방문한 정점을 의미합니다.

(1) 먼저, 시작점을 정합니다. 저희는 1로 정했습니다. 시작점 1을 큐와 방문기록에 삽입합니다.

(2) 1을 큐에서 뺍니다. 이후 1에서 인접한 접점 3과 4에 방문합니다. 방문한 점을 큐와 방문기록에 삽입합니다.

(3) 3을 큐에서 뺍니다. 이후 3에서 인접한 접점 1과 5에 방문합니다.

    하지만 1은 이미 방문한 점이기 때문에 넘어가고, 5에 방문합니다. 5를 큐와 방문기록에 삽입합니다.

(4) 4를 큐에서 뺍니다. 이후 4에서 인접한 접점 1에 방문합니다.

      하지만 1은 이미 방문한 점이기 때문에 통과하고 다음 단계인 (5)로 넘어갑니다.

(5) 5를 큐에서 뺍니다. 이후 5에서 인접한 접점 2와 6에 방문합니다. 2와 6을 큐와 방문기록에 삽입합니다.

(6) 방문기록은 최단이동경로와도 같습니다. 완성했습니다.

 

3. BFS 알고리즘 - CODE

 

앞의 예시를 파이썬으로 구현하면 아래와 같습니다.

graph_list = {1: set([3, 4]),
              2: set([3, 4, 5]),
              3: set([1, 5]),
              4: set([1]),
              5: set([2, 6]),
              6: set([3, 5])}
root_node = 1

from collections import deque

def iterative_bfs(graph, start_v):
    discovered=[start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
          if w not in discovered:
            discovered.append(w)
            queue.append(w)
    return discovered
  
print(iterative_bfs(graph_list, root_node))

출처

https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog