BFS (Breitenprioritätssuche), die jeder in Python schreiben kann
Dieser Artikel wird oben angezeigt, wenn Sie in Python nach BFS suchen. Es gibt jedoch einige Teile, die für mich schwer zu verstehen sind, und ich denke, es gab einige Fehler in der Erklärung. Also habe ich beschlossen, einen Artikel über das zu schreiben, was ich verstanden habe.
Ich habe es in einer Situation aufgenommen, in der ich BPF vollständig verstanden habe.
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() #"Ein Element vom Ende zurückgeben", "Dieses Element aus d löschen"=1⇦⑤
#print(v)
for i in graph[v]: #Salzig ist Grafik[1]=[2]Also v=1,i=Es ist 2. ⇦ ⑥
#print(i)⇦⑦
#print(graph[i])←
if dist[i] != -1:
#print(i)⇦⑧
continue
else: #！！！
#print(i)⇦⑨
#print(v) #Salzig v=1,i=2 ⇦⑩
dist[i] = dist[v] + 1 #Ist es sonst#◯!!!
d.append(i) #i=Beginnen Sie mit 2 zu suchen#◯!!!
ans = dist[1:]
#print(*ans, sep="\n")
Der schwierigste Teil ist, dass der [sonst] Teil des durch # !!! beschriebenen Teils nicht in der Referenz beschrieben wird. Ich denke es ist anders. .. .. Es mag einen Weg geben, ohne diesen zu schreiben, aber es war mit den Augen von wenn sonst schwer zu verstehen. Von ①, ② graph [[], [2], [1, 3, 4], [2, 4], [3, 2]] dist [0, 0, -1, -1, -1]
Ich dachte, dass popleft () in ⑤ "aus d löschen" würde, aber es ist "aus d löschen und in v setzen".
⑥ Da v = 1 in ⑤ ist, wird Graph [1] = [2] i zugewiesen. Das heißt, i = 2.
Es ist, wenn ~ else, aber wenn Sie das Array in i und graph als ⇨ beschreiben, wenn if ausgeführt wird, und ←, wenn else ausgeführt wird 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]
◯ !!! Aber wenn es salzig ist dist [2] = dist [1] + 1 Mit anderen Worten, die Entfernung wird aufgezeichnet, da sie nur eine Entfernung von [1] beträgt. d.append (i) treibt die Suche nach dem nächsten v voran.
Die 4. Zeile ist mit Ausnahme von dist [0] und dist [1] bei der Initialisierung von dist (# 5) als -1 definiert. Wenn also "dist [i] == 1" nicht besucht wird (diesmal) Ich habe noch nicht in den Scheitelpunkt geschaut, den ich im Satz habe) ". Umgekehrt bedeutet dist [i]! = 1, dass Sie bereits besucht haben.
das ist, Wenn dist [i] == -1 ist, bedeutet dies "noch nicht besucht (ich habe den Scheitelpunkt i in dieser while-Anweisung noch nicht untersucht)". Umgekehrt bedeutet dist [i]! = -1, dass Sie bereits besucht haben. Es scheint so als. .. .. ..
Recommended Posts