Recherche de priorité de largeur (BPF) Peut-être compris (python)

Article de référence

BFS (recherche de priorité de largeur) que n'importe qui peut écrire en Python

Cet article apparaît en haut lorsque vous recherchez BFS en python. Cependant, certaines parties sont difficiles à comprendre pour moi, et je pense qu'il y a eu des erreurs dans l'explication. J'ai donc décidé d'écrire un article sur ce que j'avais compris.

Réécrit

Je l'ai enregistré dans une situation où je comprenais parfaitement 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() #"Renvoie" un élément de la fin, "Efface cet élément de d"=1⇦⑤
 #print(v)
 for i in graph[v]: #Salty est graphique[1]=[2]Donc v=1,i=C'est 2. ⇦ ⑥
   #print(i)⇦⑦
   #print(graph[i])←
   if dist[i] != -1:
     #print(i)⇦⑧
     continue
   else:　#！！！
     #print(i)⇦⑨
     #print(v) #Salé v=1,i=2　　⇦⑩
     dist[i] = dist[v] + 1 #Est-ce autre chose?#◯!!!
     
     d.append(i) #i=Commencez la recherche avec 2#◯!!!

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

barrière

Le plus dur est que la partie [else] de la partie décrite par # !!! n'est pas décrite dans la référence. Je pense que c'est autre chose. .. .. Il y a peut-être un moyen d'écrire sans cela, mais c'était difficile à comprendre avec les yeux de sinon. De ①, ② graph [[], [2], [1, 3, 4], [2, 4], [3, 2]] dist [0, 0, -1, -1, -1]

Je pensais que popleft () dans ⑤ "supprimerait de d", mais c'est "supprimer de d et mettre en v".

⑥ Puisque v = 1 dans ⑤, le graphe [1] = [2] est affecté à i. Autrement dit, i = 2.

C'est si ~ else, mais si vous décrivez le tableau dans i et le graphe comme ⇨ quand if est exécuté et ← quand else est exécuté 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]

◯ !!! Mais si c'est salé dist [2] = dist [1] + 1 En d'autres termes, la distance est enregistrée car elle n'est qu'à une distance de [1]. d.append (i) fait avancer la recherche du prochain v.

Où la référence semble être fausse

La 4ème ligne est définie comme -1 sauf pour dist [0] et dist [1] lors de l'initialisation de dist (# 5), donc si "dist [i] == 1 alors non visité (this while) Je n'ai pas encore examiné le sommet i dans la phrase) ". Inversement, si dist [i]! = 1, cela signifie que vous avez déjà visité.

c'est, Si dist [i] == -1, cela signifie "pas encore visité (je n'ai pas encore examiné le sommet i dans cette déclaration while)". Inversement, si dist [i]! = -1, cela signifie que vous avez déjà visité. Il semble que. .. .. ..