自分用なので、かなり雑です。
また、以下のコードはこちらから、引用させていただいたものです。
頂点n個、辺の数m本を標準入力で受け取り、その後、m（辺の数）回2つの頂点を受け取り、それを二つの辺における辺とする。そして、頂点1からの最短距離を出力する。
例えば、例えば頂点4個で辺4本、つながっている頂点が(1, 2)、(2, 3)、(3, 4)、(4, 2)なら
入力
4 4
1 2
2 3
3 4
4 2
出力
0
1
2
2
と言う感じ。
from collections import deque #1
n, m = map(int, input().split()) #2
graph = [[] for _ in range(n+1)] #3
for i in range(m): #4
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
dist = [-1] * (n+1) #5
dist[0] = 0
dist[1] = 0
d = deque() #6
d.append(1)
while d: #7
v = d.popleft()
for i in graph[v]:
if dist[i] != -1:
continue
dist[i] = dist[v] + 1
d.append(i)
ans = dist[1:] #8
print(*ans, sep="\n")
学んだことと分からなかったことだけを抜粋してメモ。
dequeとは、スタックとキューを合わせた感じのやつでメモリ効率が良く、O(1)で実行されるらしい。
＃３と＃４は
graph = [[] for _ in range(n+1)] #3
for i in range(m): #4
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
隣接リストとか言うやつで、隣接行列と一緒にグラフをプログラミングで表す時に使うらしい。因みに、上記の例でgraphを出力してみるとこんな感じ。
[[], [2], [1, 3, 4], [2, 4], [3, 2]]
これで、インデックス番号と中の要素をそれぞれ対応させて、無向グラフ（または、双方向グラフ）が表現されてる。
例えば、インデックス[2] の要素、1, 3, 4は頂点2と繋がってることを表す。
dist = [-1] * (n+1) #5
dist[0] = 0
dist[1] = 0
distは shortest distance の略で、初期値を -1 として、すでに頂点1からの距離が計算されたかの判別の為に用いているらしい。こう言うところ、しっかり見習いたい。
今回は頂点１からの距離なので、dist[0]はさよなら。またdist[1]も『頂点１』
からなので距離０として固定されている。
＃７の挙動は例えば上の例でいくと、
while d: #7
v = d.popleft()
for i in graph[v]:
if dist[i] != -1:
continue
dist[i] = dist[v] + 1
d.append(i)
最初、d には＃６より、
d = deque() #6
d.append(1)
１が入っているので、
v = 1
また、graph[[1]には、２のみが入っており、dist[2]は初期値 -1 のままであるので、
dist[2] = dist[1] + 1
が行われ、dist[2] == 1（頂点１からの距離は１）と言うことになる。最後にi である２がdにappendされる。
dist[i] == -1 じゃないのが続けば、d は popleft されるだけとなり、
いずれ d == False（空）となり、while文が終了する。と言う流れ。
今回ようやくにして初歩的ではあるが、アルゴリズムを実装する経験ができ、少しずつやりたいことができるようになっている気がする。
これから、どんな風になっていくのか見当もつかないが、こんなのを扱ってご飯がたべれたら最高の外の何ものでもない。
結論、プログラミングは楽しい。イエイ。