幅優先探索とは？

• 経路探索を行いたいときなどに使う
• スタート地点から近い順に探索していく（=幅優先）

試したコード

python
from collections import deque

n = 4
nodes =[[1, 2], [2, 3], [3, 4], [4, 2]]

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

for i in range(len(nodes)):
    a, b = nodes[i]
    graph[a].append(b)
    graph[b].append(a)

# graph[i] = [X, X...]
#i地点はX, X, ...とつながっているというリスト

# スタートは地点１
dist = [-1] * (n+1) # dist: dist[i]はスタート地点（地点1）から地点iまでの距離
dist[0] = 0
dist[1] = 0 # dist[1]は地点1から地点1までなので距離0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if dist[i] != -1:
            continue
        dist[i] = dist[v] + 1
        d.append(i)

ans = dist[1:]
print(*ans, sep="\n")

References

Pythonで誰でも書けるBFS(幅優先探索)｜ぱん

こんばんは、ぱんと申します。 お久しぶりです！私が前回ABC参戦記を書いたのはABC154の時なので、今回は私が灰→茶coderになってから初の競プロ記事ということになります。めでたい(？) さて

めっちゃわかりやすかったです！