Da es sich um ein verkettetes Diagramm handelt, wird das Minimum durch das BFS-Prinzip garantiert.
Referenz BFS (Width Priority Search) Super Einführung! ~ Verwenden Sie die Warteschlange lebhaft ~
Beispielcode
from collections import deque
#Anzahl der Eckpunkte und Seiten
N, M = map(int, input().split())
#Seite
AB = [map(int, input().split()) for _ in range(M)]
#Angrenzende Listeneinstellung für ungerichtetes Diagramm
link = [[] for _ in range(N + 1)]
for a, b in AB:
link[a].append(b)
link[b].append(a)
#BFS-Datenrahmen
dist = [-1] * (N + 1) #Kein Zeichensatz
que = deque([1]) #Besuchen Sie die Warteschlange ab Eckpunkt 1
#BFS-Start(Suchen Sie, bis die Warteschlange leer ist)
while que:
v = que.popleft() #Erster Peak aus der Warteschlange(Aktueller Standort)v bekommen
for i in link[v]:
#Setzen Sie ein Zeichen an der aktuellen Position am nicht festgelegten Scheitelpunkt i und fügen Sie es der Besuchswarteschlange hinzu
if dist[i] == -1:
dist[i] = v
que.append(i)
#Ergebnisausgabe (Signatur an jedem Scheitelpunkt installiert)
print('Yes')
print('\n'.join(str(v) for v in dist[2:]))
Recommended Posts