[알고리즘이론] 파이썬으로 BFS 구현

BFS(Breadth-First Search)는 큐(Queue)를 이용하여 구현할 수 있습니다. 큐는 선입선출(FIFO) 구조이므로, BFS에서는 현재 노드와 인접한 노드 중 방문하지 않은 노드가 있으면 해당 노드를 큐에 삽입하고 방문 처리합니다. 그리고 큐에서 꺼낸 노드를 다시 시작점으로 하여 인접한 노드 중 방문하지 않은 노드가 있으면 큐에 삽입하고 방문 처리합니다. 이 과정을 큐가 빌 때까지 반복하면 됩니다.

 

아래는 큐를 사용하여 BFS를 구현한 예제 코드입니다.

 

# 큐를 사용한 BFS 구현 예제
from collections import deque

def bfs(start, adj_list):
    visited = [False] * len(adj_list)  # 각 노드의 방문 여부를 저장할 리스트
    queue = deque([start])  # 시작 노드를 큐에 삽입

    while queue:
        v = queue.popleft()  # 큐에서 노드를 꺼내어
        if not visited[v]:  # 방문하지 않은 노드라면
            visited[v] = True  # 해당 노드를 방문 처리하고 출력
            print(v, end=' ')

            # 해당 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 삽입
            for i in adj_list[v]:
                if not visited[i]:
                    queue.append(i)

# 예제 그래프
adj_list = {
    1: [2, 3, 4],
    2: [1, 4, 5],
    3: [1, 6, 7],
    4: [1, 2, 5],
    5: [2, 4, 8],
    6: [3, 7],
    7: [3, 6],
    8: [5]
}

bfs(1, adj_list)  # 1번 노드에서 BFS 탐색 시작

 

위 코드에서 bfs() 함수는 시작 노드의 인덱스와 인접 리스트 adj_list를 입력으로 받습니다.

visited 리스트는 각 노드의 방문 여부를 저장합니다. 큐는 deque() 함수를 사용하여 queue 리스트를 생성하며, 최초로 시작 노드를 큐에 삽입합니다.

 

그리고 while문에서는 큐가 빌 때까지 노드를 꺼내어 방문하지 않은 노드면 방문 처리하고 출력한 후, 해당 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 삽입합니다.

 

최초로 bfs() 함수를 호출할 때는 시작 노드의 인덱스와 인접 리스트를 입력으로 넣어주면 됩니다.