Breadth-first search (BPF) Maybe understood (python)

Reference article

BFS (breadth-first search) that anyone can write in Python

This article comes up at the top when you search for BFS in python. However, there are some parts that are difficult for me to understand, and I think there were some mistakes in the explanation. So I decided to write an article about what I understood.

Rewritten

I recorded it in a situation where I fully understood the BPF.

from collections import deque

n, m = map(int, input().split())

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

for i in range(m):
 a, b = map(int, input().split())
 graph[a].append(b)
 graph[b].append(a)

#print(graph)　⇦①

dist = [-1] * (n+1)
dist[0] = 0
dist[1] = 0

#print(dist)　←②

d = deque()
d.append(1)

#print(d)⇦③

while d:
 #print(d)⇦④
 v = d.popleft() #"Return" one element from the end, "Erase that element from d"=1⇦⑤
 #print(v)
 for i in graph[v]: #Salty is graph[1]=[2]So v=1,i=It is 2. ⇦ ⑥
   #print(i)⇦⑦
   #print(graph[i])←
   if dist[i] != -1:
     #print(i)⇦⑧
     continue
   else:　#！！！
     #print(i)⇦⑨
     #print(v) #Salty v=1,i=2　　⇦⑩
     dist[i] = dist[v] + 1 #Is it else?#◯!!!
     
     d.append(i) #i=Start searching with 2#◯!!!

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

barrier

The hardest part is that the [else] part of the part described by # !!! is not described in the bibliography. I think it's else. .. .. There may be a way to write without this, but it was difficult to understand with the eyes of if else. From ①, ② graph [[], [2], [1, 3, 4], [2, 4], [3, 2]] dist [0, 0, -1, -1, -1]

I thought that popleft () in ⑤ would be "erased from d", but it is "deleted from d and put in v".

⑥ Since v = 1 in ⑤, graph [1] = [2] is assigned to i. That is, i = 2.

If ~ else, if you describe the array in i and graph as ⇨ when if is executed and ← when else is executed 2 ← [1, 3, 4] 1 ⇨ [2] 3　← [2, 4] 4　← [3, 2] 2　⇨ [1, 3, 4] 4　⇨ [3, 2] 3　⇨ [2, 4] 2　⇨ [1, 3, 4]

◯ !!! But if it's salty dist [2] = dist [1] +1 In other words, the distance is recorded because it is only one distance from [1]. d.append (i) advances the search for the next v.

Where the reference seems to be wrong

The 4th line is defined as -1 except for dist [0] and dist [1] in the initialization of dist (# 5), so if "dist [i] == 1 then not visited (this while) I haven't looked into vertex i yet in the statement) ". Conversely, if dist [i]! = 1, It means that you have already visited.

this is, If dist [i] == -1, it means "not visited yet (not yet examined for vertex i in this while statement)". Conversely, if dist [i]! = -1, it means that you have already visited. It seems to be. .. .. ..