[python] BFS

*알고리즘 이론은 복습 용도로 작성되었습니다. 간략하게 작성되어 있을 수 있으며 해당 알고리즘을 어느정도 알고있다는 전제하에 작성되었습니다.

 

1. BFS란?

그래프를 탐색하는 알고리즘의 한 종류로, leaf 노드에 도달할 때 까지 깊이 우선 탐색을 하는 DFS와 달리 인접한 노드부터 탐색하는 방법입니다. 그래프의 각 깊이 별로 탐색을 하게 되므로, 넓이 우선 탐색이라고 부릅니다.

*시간복잡도는 DFS와 마찬가지로 인접리스트 방식은 모든 노드(n)와 간선(e)을 탐색하므로, O(n+e) 입니다.

 

구체적으로 단계를 설명해보자면 다음 그림과 같습니다.

2. 구현 방법

• queue를 통해 인접한 배열을 담아가며 탐색합니다.
• visited 배열을 통해 방문 여부를 확인합니다.
• 인접한 노드를 우선적으로 탐색하며, 방문하지 않은 노드만 탐색합니다.

백준알고리즘 1260번을 기반으로 구현한 코드입니다.(https://www.acmicpc.net/problem/1260)

import sys
from collections import deque

n,m,v = map(int, sys.stdin.readline().split())

graph = [[] for _ in range(n+1)]

for i in range(m):
    node1, node2 = map(int, sys.stdin.readline().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

for i in range(1,n+1):
    graph[i].sort()

visited_bfs = [False]*(n+1)

def bfs(n):
    q = deque([n])
    visited_bfs[n] = True

    while q:
        node = q.popleft()
        print(node, end=' ')

        for new_node in graph[node]:
            if visited_bfs[new_node]:
                continue
            q.append(new_node)
            visited_bfs[new_node] = True

bfs(v)