Find if Path Exists in Graph
Ein ungerichteter Graph hat n Knoten, nummeriert von 0 bis n-1. Jeder Eintrag [u, v] in edges verbindet die Knoten u und v, und du kannst eine Kante in beide Richtungen durchlaufen. Gib true zurück, wenn du entlang der Kanten von source nach destination gelangen kannst, andernfalls false. Ein Knoten kann sich immer selbst erreichen.
Funktion
- ninteger
- die Anzahl der Knoten
- edgesinteger-2d-array
- die Kanten, jeweils ein Paar [u, v] verbundener Knoten
- sourceinteger
- der Knoten, von dem aus du startest
- destinationinteger
- den Knoten, den du erreichen möchtest
- Gibt zurückboolean
- ob ein Pfad Quelle und Ziel verbindet
Einschränkungen
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [u, v]wobei0 ≤ u, v ≤ n-1undu ≠ v- Keine Kante kommt zweimal vor, auch nicht in umgekehrter Richtung.
0 ≤ source, destination ≤ n-1
Beispiele
- Eingabe
- n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
- Ausgabe
- true
- Erklärung
- Der Pfad
0 → 1 → 2 → 3verwendet drei Kanten, also ist Knoten 3 erreichbar. Die Knoten 4 und 5 bilden einen separaten Bereich, den der Pfad nie benötigt.
- Eingabe
- n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
- Ausgabe
- false
- Erklärung
- Von Knoten 2 aus erreichst du 0 und dann 1, und sonst nichts. Knoten 4 ist nur mit Knoten 3 verbunden, und keine Kante verbindet
{0, 1, 2}mit{3, 4}, also lautet die Antwortfalse.
+16 versteckte Tests beim Einreichen
Weiterführende Frage
Angenommen, die Kanten sind Einbahnstraßen: [u, v] lässt dich nur von u nach v gehen. Welche der drei Ansätze funktionieren weiterhin, und was musst du daran ändern?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Vergiss für einen Moment das Ziel. Welche Knoten kannst du überhaupt von
sourceaus erreichen?Erweitere die Menge der erreichten Knoten ausgehend von
sourceKante für Kante und höre auf, wenn sie nicht mehr wächst. Eine Suche in einer Nachbarschaftsliste erledigt das in einem Durchlauf, solange du keinen Knoten zweimal besuchst.Führe entweder eine BFS von
sourcemit einemseen-Array aus oder fasse die beiden Endpunkte jeder Kante mit Union-Find zu einer Gruppe zusammen und prüfe, obsourceunddestinationam Ende dieselbe Wurzel haben.
Lösung
Die Frage ist, ob source und destination im selben zusammenhängenden Teil des Graphen liegen. Die langsame Methode durchsucht die Kantenliste so lange erneut, bis nichts Neues mehr erreicht wird. Eine Breitensuche über eine Adjazenzliste erkundet jeden Knoten und jede Kante genau einmal, und Union-Find liefert dieselbe Antwort, indem es beim Einlesen der Kanten Gruppen zusammenführt – ganz ohne Nachbarlisten.
Durchlaufe die Kanten, bis sich nichts mehr ändert
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Markiere jeden Knoten, von dem du weißt, dass du ihn erreichen kannst, beginnend mit source. Lies nun die Kantenliste. Eine Kante mit einem markierten und einem nicht markierten Ende bedeutet, dass du auch das nicht markierte Ende erreichen kannst; markiere es also. Wiederhole den gesamten Durchlauf, bis ein Durchlauf nichts Neues markiert oder destination markiert ist.
Das ist korrekt: Ein Knoten auf einem Pfad der Länge k von source wird spätestens im k-ten Durchlauf markiert, und ein Knoten wird nur dann markiert, wenn eine Kante von einem markierten Knoten zu ihm führt. Im ersten Beispiel markiert ein Durchlauf in der Reihenfolge der Liste nacheinander 1, 2 und 3, und du bist fertig.
Der Aufwand hängt von der Reihenfolge der Kanten ab. Ist der Pfad vom entfernten Ende aus rückwärts aufgelistet, markiert jeder Durchlauf nur einen weiteren Knoten. Ein Pfad durch 5001 Knoten benötigt dann 5000 Durchläufe über 5000 Kanten, also 2.5 × 10^7 Kantenprüfungen, während ein einziger Durchlauf über eine Nachbarliste genügen würde.
Algorithmus
- Erstelle
reached, wobei nursourcemarkiert ist. - Gehe alle Kanten
[u, v]durch. Wenn genau ein Ende markiert ist, markiere das andere und halte fest, dass sich etwas geändert hat. - Wiederhole den Durchlauf, solange sich etwas geändert hat und
destinationnoch nicht markiert ist. - Gib zurück, ob
destinationmarkiert ist.
def validPath(n, edges, source, destination):
reached = [False] * n
reached[source] = True
changed = True
while changed and not reached[destination]:
changed = False
for u, v in edges:
# An edge with exactly one reached end pulls the other end in.
if reached[u] != reached[v]:
reached[u] = reached[v] = True
changed = True
return reached[destination]Breitensuche
Idee
Die Suche verschwendet Zeit damit, Kanten erneut zu lesen, deren Enden schon lange feststehen. Liste stattdessen für jeden Knoten die Knoten auf, mit denen er verbunden ist. Jede Kante [u, v] kommt in beide Listen, denn du kannst sie in beide Richtungen durchlaufen. Erkunde dann ausgehend von source die Umgebung: Nimm einen Knoten aus einer Warteschlange und füge jeden Nachbarn hinzu, den du noch nicht gesehen hast.
Markiere einen Knoten als gesehen, wenn du ihn hinzufügst, nicht erst, wenn du ihn herausnimmst. So gelangt kein Knoten zweimal in die Warteschlange, und die Suche endet auch dann, wenn der Graph Zyklen enthält, wie 0 → 1 → 2 → 0. Wenn destination aus der Warteschlange genommen wird, existiert ein Pfad. Ist die Warteschlange zuerst leer, hast du alle Knoten gesehen, die source erreichen kann, und destination war nicht darunter.
Jeder Knoten wird höchstens einmal in die Warteschlange eingefügt, und jede Kante wird zweimal betrachtet, einmal von jedem Ende aus. Daher beträgt die Laufzeit O(n + m) für m Kanten. Die Nachbarlisten benötigen O(n + m) Speicherplatz. Eine Warteschlange statt Rekursion verhindert, dass ein Pfad mit 5000 Knoten den Aufrufstapel überlaufen lässt.
Algorithmus
- Erstelle eine Adjazenzliste: Füge für jede Kante
[u, v]vzur Liste vonuunduzur Liste vonvhinzu. - Markiere
sourceals besucht und füge es in eine Warteschlange ein. - Nimm einen Knoten vom Anfang der Warteschlange. Wenn er
destinationist, gibtruezurück. - Markiere jeden noch nicht besuchten Nachbarn und füge ihn in die Warteschlange ein.
- Wenn die Warteschlange leer ist, gib
falsezurück.
from collections import deque
def validPath(n, edges, source, destination):
# Each edge goes both ways, so list it under both of its ends.
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
seen = [False] * n
seen[source] = True
queue = deque([source])
while queue:
node = queue.popleft()
if node == destination:
return True
for nxt in graph[node]:
if not seen[nxt]:
# Mark on push, so no node enters the queue twice.
seen[nxt] = True
queue.append(nxt)
return FalseUnion-Find
Idee
Du benötigst den Pfad nicht, sondern musst nur wissen, ob einer existiert. Betrachte den Graphen also als Gruppen miteinander verbundener Knoten. Zu Beginn bildet jeder Knoten eine eigene Gruppe. Eine Kante [u, v] bedeutet, dass u und v zusammengehören, also führe ihre Gruppen zusammen. Nach dem Verarbeiten aller Kanten sind source und destination genau dann verbunden, wenn sie zur selben Gruppe gehören.
Speichere jede Gruppe als Baum mit parent-Verknüpfungen; die Wurzel bezeichnet die Gruppe. find(x) geht bis zur Wurzel hinauf. Zum Zusammenführen hängst du eine Wurzel unter die andere. Im zweiten Beispiel bilden [0, 1] und [0, 2] die Gruppe {0, 1, 2}, und [3, 4] bildet {3, 4}; find(2) und find(4) geben unterschiedliche Wurzeln zurück, daher lautet die Antwort false.
Zwei Vorgehensweisen halten die Bäume flach. Hänge die kleinere Gruppe unter die größere und halbiere den Pfad während find, indem du jeden Knoten auf seinen Großelternknoten verweist. Zusammen sorgen sie dafür, dass jede Operation α(n) kostet, die inverse Ackermann-Funktion, die für jede Eingabe, die du jemals sehen wirst, unter 5 bleibt. Die Kanten werden einmal eingelesen und gespeichert werden nur parent und size: Speicherbedarf O(n) und keine Nachbarlisten, die erstellt werden müssen.
Algorithmus
- Setze für jeden Knoten
parent[x] = xundsize[x] = 1. - Bestimme für jede Kante
[u, v]die Wurzelnaundbbeider Endpunkte. - Wenn sie verschieden sind, hänge die Wurzel der kleineren Gruppe unter die andere und addiere die Größen.
- Gib zurück, ob
find(source)gleichfind(destination)ist.
def validPath(n, edges, source, destination):
parent = list(range(n)) # every node starts as its own group
size = [1] * n
def find(x):
# Walk up to the group's root, halving the path on the way.
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
for u, v in edges:
a, b = find(u), find(v)
if a != b:
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
return find(source) == find(destination)
Stolperfallen und Grenzfälle
Der Graph ist klein, aber einige Details entscheiden darüber, ob die Suche abgeschlossen wird und das richtige Ergebnis liefert.
- Jede Kante nur in einer Richtung hinzufügen. Der Graph ist ungerichtet, daher muss
[1, 0]es dir auch ermöglichen, von 0 nach 1 zu gehen. Eine einseitige Adjazenzliste übersieht Pfade, die eine Kante rückwärts nutzen. - Knoten erst als besucht markieren, wenn du sie aus der Warteschlange nimmst, statt wenn du sie hineinlegst. Ein Knoten wird dann für jeden Nachbarn, der vor ihm verarbeitet wird, einmal in die Warteschlange eingefügt, sodass die Warteschlange bis zu
2mEinträge statt höchstensnenthalten kann. - Vergessen, dass
sourcegleichdestinationsein kann. Die Antwort isttrue, auch wenn dieser Knoten überhaupt keine Kanten hat. - Rekursive Tiefensuche auf einem langen Pfad verwenden. Ein Pfad durch 5000 Knoten besteht aus 5000 verschachtelten Aufrufen und überschreitet damit Pythons Standardlimit von 1000. Verwende eine Warteschlange oder einen expliziten Stack.
- Bei Union-Find
parent[source]mitparent[destination]vergleichen. Nur die Wurzeln bezeichnen eine Gruppe; vergleiche immerfind(source)mitfind(destination). - Den Indexversatz in Lua und R vergessen, deren Arrays bei 1 beginnen: Knoten
xbefindet sich am Indexx+1.
Häufige Fragen4
Sollte ich BFS, DFS oder Union-Find verwenden, um zu prüfen, ob ein Pfad existiert?
Alle drei sind linear oder liegen nahe daran. BFS und DFS können anhalten, sobald sie das Ziel erreichen, und sie können den Pfad selbst zurückgeben. Union-Find benötigt keine Adjazenzliste, liest jede Kante einmal ein und glänzt, wenn für denselben Graphen viele Fragen zur Zusammenhangskomponente gestellt werden, denn nach den Vereinigungen kostet jede Frage zwei find-Aufrufe.
Wie hoch ist die Zeitkomplexität, um festzustellen, ob in einem Graphen ein Pfad existiert?
Mit BFS oder DFS beträgt der Zeit- und Speicheraufwand O(n + m) für n Knoten und m Kanten: Jeder Knoten wird einmal besucht und jede Kante wird von beiden Enden aus geprüft. Union-Find mit Union nach Größe und Pfadhalbierung benötigt O(n + m·α(n)) Zeit und O(n) Speicher, wobei α so langsam wächst, dass sie in der Praxis eine kleine Konstante ist.
Warum benötigt BFS ein Besuchsarray?
Ohne diese Maßnahme würde ein Zyklus wie 0 → 1 → 2 → 0 die Suche endlos im Kreis laufen lassen, und selbst ohne Zyklen würde ein Knoten mit mehreren Nachbarn für jeden Nachbarn einmal in die Warteschlange gestellt. Wenn jeder Knoten genau in dem Moment markiert wird, in dem er in die Warteschlange gestellt wird, ist sichergestellt, dass er nur einmal verarbeitet wird. Dadurch wird der Aufwand auf O(n + m) begrenzt.
Was bewirken Pfadkompression und Vereinigung nach Größe bei Union-Find?
Sie halten die Bäume flach, damit find schnell bleibt. Bei der Vereinigung nach Größe wird der kleinere Baum unter den größeren gehängt, sodass sich die Tiefe eines Knotens nur dann erhöht, wenn sich die Größe seiner Gruppe mindestens verdoppelt. Dadurch wird die Tiefe auf log n begrenzt. Die Pfadkompression oder das hier verwendete Pfadhalbieren verkürzt jedes Mal, wenn du den Weg zurücklegst, den Pfad zur Wurzel. Zusammen senken sie den Aufwand jeder Operation auf α(n).
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def validPath(n, edges, source, destination):
# Schreibe hier den CodeFall 1
Fall 2
Eingabe
n = 6 edges = [[0, 1], [1, 2], [2, 3], [4, 5]] source = 0 destination = 3
Erwartet
true