[자료구조] 너비 우선 탐색(bfs) 원리 , 알고리즘

DFS는 시작 정점에서 가까운 정점보다 더 먼 정점을 먼저 방문할 수도 있는 반면에, BFS는 시작 정점에서 가까운 정점이 먼 정점보다 먼저 방문되도록 하는 방식을 뜻한다.

 

너비 우선 탐색(BFS)에서는 시작 정점을 방문하고, v에 인접한 모든 정점들을 방문한다. 그리고 새롭게 방문한 정점들에 인접하면서 아직 방문하지 못한 정점들을 방문한다. 이를 위해 큐(queue)를 사용한다.

 

BFS는 다음과 같은 절차로 진행된다.

 

[example]

      A
    /    \
  B      C
  /   \    /
 D   E     F
  \     |    /
       G

 

 

1) 너비 우선 탐색을 위한 초기 상태를 셋팅한다. 배열의 visited를 false로 설정하고(기본값) 공백 큐를 생성한다.

2) 정점 A를 시작으로 너비 우선 탐색을 시작한다.

3) 정점 A에서 방문하지 않은 모든 인접 정점 B,C를 방문하고 큐에 enqueue한다.

4) 정점 A에 대한 인접 정점들을 처리했으므로, 다음 정점을 찾기 위해 큐를 dequeue하여 B를 받는다.

5) B에서 방문하지 않은 모든 인접 정점 D,E를 방문하고 큐에 enqueue한다.

6) C를 받는다. (큐에서 dequeue를 통하여)

7) C의 인접 정점이 없으므로 큐를 dequeue하여 D를 받는다.

8) D에서 방문하지 않은 인접 정점 G를 방문하고 큐에 enqueue한다.

9) E를 받는다.

10) G를 받는다 (다음 정점 선택)

11) G에서 방문하지 않은 인접 정점 F를 방문하고 큐에 enqueue한다.

12) 정점 G에 대한 인접 정점들을 처리했으므로, 너비 우선 탐색을 계속할 다음 정점을 찾기 위해 큐를 dequeue하여 F를 받는다.

 

[파이썬으로 작성한 코드] 

 

from collections import deque

# 그래프의 인접 리스트 표현
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': ['G'],
    'E': ['G'],
    'F': ['G'],
    'G': []
}

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()

        if vertex not in visited:
            visited.add(vertex)
            print("Visit:", vertex)

            # 인접한 정점을 큐에 추가
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)

# BFS 시작
start_vertex = 'A'
bfs(graph, start_vertex)