소개

python을 사용한 폭 우선 탐색의 구현에 대해 설명합니다. (내가 언제나 실장하는 녀석을 올릴 뿐입니다.)
폭 우선 탐색에서는 자주 거리에 관한 문제가 나오므로, 이번은 어느 1 정점으로부터 각 정점까지의 거리를 돌려주는 함수를 실장합니다.

폭 우선 탐색

폭 우선 탐색에 관한 일반적인 지식은 조사하면 많이 나올 것이라고 생각하므로, 자세한 것은 생략합니다만 간단히 설명합니다.
　 　
파란색 화살표처럼 가까운 곳에서 순서대로 정점을 쫓아갑니다. 이번에 다루는 거리의 경우에는, 하나 앞의 정점까지의 거리에 1을 더하면 됩니다. (이미지에서는 1에서 흔들고 있습니다만, 거리라면 0에서 흔들면 됩니다.)
이 정점의 탐색의 순서는, 큐로 관리합니다. 큐는 선입선출 데이터 구조입니다. 이번 예에서 말하면, 우선은 스타트의 0이 들어갑니다. ([0]) 그런 다음 내용물을 앞에서 꺼내 인접한 정점을 검사합니다. (이번에는 1, 2) 처음 방문한 경우 큐에 추가합니다. ([1, 2])
이것을 반복해 가면 파란색 화살표 순서로 정점을 조사할 수 있습니다.
([2, 3, 4]→[3, 4, 5, 6]→[4, 5, 6, 7]...)
큐가 비워지면 탐색 종료입니다. 고마워요.

구현

입력

정점수 n과 변의 수 m이 주어지고, 그 후 인접하는 정점을 m행에 건너 주어집니다.

11 9
0 1
0 2
1 3
1 4
2 5
2 6
3 7
5 8
8 9

코드

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()] # nは頂点の数、mは辺の数
g = [[] for _ in range(n)] # 隣接リスト

for _ in range(m):
    a, b = [int(x) for x in input().split()]
    g[a].append(b)
    g[b].append(a)

from collections import deque

def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

# 0からの各頂点の距離
d = bfs(0)
print(d)

출력

왼쪽부터 정점의 번호순으로 정점 0과의 거리를 가지는 리스트를 출력합니다. 자신과의 거리는 0으로, 도착할 수 없는 정점은 None이 됩니다.

[0, 1, 1, 2, 2, 2, 2, 3, 3, 4, None]

결론

뭔가 실수가 있으면 가르쳐주세요! 조언 등도 주시면 기쁩니다!