Graph Valid Tree
Du erhältst n Knoten, nummeriert von 0 bis n-1, und eine Liste edges mit ungerichteten Kanten. Jedes Paar [a, b] verbindet Knoten a und Knoten b.
Gib true zurück, wenn die Kanten alle n Knoten zu einem einzigen Baum verbinden: Jeder Knoten kann jeden anderen erreichen, und es gibt keinen Zyklus. Gib andernfalls false zurück.
Funktion
- ninteger
- die Anzahl der Knoten, nummeriert von 0 bis n-1
- edgesinteger-2d-array
- die ungerichteten Kanten, jeweils ein Paar [a, b]
- Gibt zurückboolean
- true, wenn die Kanten alle n Knoten zu einem Baum verbinden, andernfalls false
Einschränkungen
2 ≤ n ≤ 1041 ≤ edges.length ≤ 5000edges[i] = [a, b]mit0 ≤ a, b ≤ n-1unda ≠ b- Keine Kante erscheint zweimal, auch nicht in umgekehrter Richtung.
Beispiele
- Eingabe
- n = 5edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
- Ausgabe
- true
- Erklärung
- Knoten 0 ist mit den Knoten 1, 2 und 3 verbunden, und Knoten 4 hängt an Knoten 1. Vier Kanten verbinden alle fünf Knoten ohne Schleife, also ist dies ein Baum.
- Eingabe
- n = 5edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]]
- Ausgabe
- false
- Erklärung
- Die Kanten
[1, 2],[2, 3]und[1, 3]bilden den Zyklus 1, 2, 3, 1. Fünf Kanten bei fünf Knoten sind eine mehr, als ein Baum haben kann.
- Eingabe
- n = 4edges = [[0, 1], [1, 2], [2, 0]]
- Ausgabe
- false
- Erklärung
- Es gibt 3 Kanten, also
n-1, aber sie bilden den Zyklus 0, 1, 2, 0, und Knoten 3 hat überhaupt keine Kante.
Weiterführende Frage
Wenn der Graph kein Baum ist, wie viele Kanten musst du entfernen und wie viele hinzufügen, damit er zu einem Baum wird? Kannst du beides in einem Durchlauf zählen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Zeichne ein paar kleine Graphen, die keine Bäume sind. Es gibt nur zwei Möglichkeiten, zu scheitern: Welche sind das?
Ein Graph ist fehlerhaft, wenn er einen Zyklus enthält oder ein Knoten abgeschnitten bleibt. Ein Baum mit
nKnoten hat genaun-1Kanten, und bei genaun-1Kanten treten diese beiden Fehler immer gemeinsam auf. Prüfe also die Anzahl und anschließend eines der beiden Kriterien.Lass jeden Knoten allein beginnen. Prüfe für jede Kante, ob ihre beiden Enden bereits zusammengehören. Wenn ja, schließt die Kante einen Zyklus; wenn nicht, füge ihre beiden Gruppen zusammen. Eine Union-Find-Datenstruktur beantwortet diese Frage in nahezu konstanter Zeit.
Lösung
Ein Baum ist zusammenhängend und hat keinen Zyklus. Bei genau n-1 Kanten sind dies ein und dieselbe Bedingung: Ein solcher Graph ist genau dann zusammenhängend, wenn er keinen Zyklus hat. Prüfe also zuerst die Anzahl der Kanten und suche dann entweder einmal nach Zusammenhang oder lass Union-Find eine Kante erkennen, die zwei bereits verbundene Knoten miteinander verbindet.
Suche vor jeder Kante nach einem Pfad
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Füge die Kanten eine nach der anderen hinzu. Suche vor dem Hinzufügen von [u, v] von u aus entlang der bisher hinzugefügten Kanten. Wenn v erreichbar ist, bildet die neue Kante einen zweiten Weg zwischen den beiden Knoten und schließt einen Zyklus, wie es [1, 3] im zweiten Beispiel tut. Wenn keine Kante einen Zyklus schließt, ist der Graph ein Wald, und eine abschließende Suche ab Knoten 0 zeigt, ob er ein einzelner Baum ist.
Bei jeder Prüfung wird der gesamte bisher aufgebaute Graph durchsucht. Bei einem Pfad mit 5001 Knoten, dessen Kanten der Reihe nach eintreffen, besuchen die Suchen 1 + 2 + ... + 5000 Knoten, also etwa 12,5 Millionen.
Algorithmus
- Beginne mit einer leeren Adjazenzliste pro Knoten.
- Suche für jede Kante
[u, v]vonuaus entlang der bisher hinzugefügten Kanten. Wenn dabeiverreicht wird, gibfalsezurück. - Füge die Kante andernfalls zu den Listen beider Endpunkte hinzu.
- Gib am Ende zurück, ob eine Suche vom Knoten 0 aus alle
nKnoten erreicht.
def reachable(graph, start):
# Every node a search from start can reach, using the edges added so far.
seen = [False] * len(graph)
seen[start] = True
stack = [start]
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
stack.append(nxt)
return seen
def validTree(n, edges):
graph = [[] for _ in range(n)]
for u, v in edges:
# A path from u to v already exists, so this edge closes a cycle.
if reachable(graph, u)[v]:
return False
graph[u].append(v)
graph[v].append(u)
# No cycle anywhere. A tree also needs every node reachable from node 0.
return all(reachable(graph, 0))Kanten zählen, dann einmal suchen
Idee
Beginne mit n getrennten Knoten und füge die Kanten eine nach der anderen hinzu. Jede Kante verbindet entweder zwei Gruppen, sodass eine Gruppe weniger übrig bleibt, oder landet innerhalb einer Gruppe und schließt einen Zyklus. Um eine Gruppe zu erhalten, sind n-1 Verbindungen nötig. Daher können weniger als n-1 Kanten den Graphen nicht verbinden, und bei mehr Kanten muss ein Zyklus geschlossen werden: Das zweite Beispiel mit 5 Kanten auf 5 Knoten scheitert schon allein an der Anzahl.
Bei genau n-1 Kanten endet der Graph nur dann als eine einzige Gruppe, wenn jede Kante zwei Gruppen verbunden hat, also nur dann, wenn keine Kante einen Zyklus geschlossen hat. Sobald die Anzahl stimmt, musst du daher nur noch den Zusammenhang prüfen: Eine Suche ab Knoten 0 muss alle n Knoten erreichen. Im dritten Beispiel erreicht sie nur 0, 1 und 2. Bei m = n-1 haben die Listen und die Suche eine Laufzeit von O(n).
Algorithmus
- Wenn
edges.lengthnichtn-1ist, gibfalsezurück. - Erstelle eine Adjazenzliste und speichere jede Kante unter beiden Endpunkten.
- Lege Knoten 0 auf einen Stapel und markiere ihn als besucht.
- Nimm Knoten vom Stapel und lege jeden noch nicht besuchten Nachbarn darauf; markiere und zähle ihn dabei.
- Gib zurück, ob die Anzahl gleich
nist.
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
# With n-1 edges, the graph is a tree exactly when it is connected.
seen = [False] * n
seen[0] = True
stack = [0]
reached = 1
while stack:
node = stack.pop()
for nxt in graph[node]:
if not seen[nxt]:
seen[nxt] = True
reached += 1
stack.append(nxt)
return reached == nKanten zählen und Union-Find
Idee
Union-Find beantwortet die Frage nach einem Zyklus für jede Kante ohne Suche. Jeder Knoten beginnt als eigene Gruppe. Für eine Kante [u, v] ermittelst du die Wurzel jedes Endpunkts. Verschiedene Wurzeln: Die Kante verbindet zwei Teilstücke, also führst du sie zusammen. Dieselbe Wurzel: u und v sind bereits verbunden, und die Kante schließt einen Zyklus. Wenn alle n-1 Kanten Gruppen zusammenführen, enden die n Gruppen als eine einzige: ein Baum.
Zwei Regeln halten die Elternketten kurz. Beim Zusammenführen wird die Wurzel der kleineren Gruppe unter die der größeren gehängt, sodass bei 10^4 Knoten keine Kette länger als 13 Schritte ist. Während einer Suche setzt du jeden durchlaufenen Knoten auf seinen Großelternknoten. Zusammen sorgen sie dafür, dass m Operationen O(m α(n)) kosten, wobei α, die inverse Ackermann-Funktion, hier höchstens 4 beträgt. Der Speicherbedarf ist O(n).
Algorithmus
- Wenn
edges.lengthnichtn-1ist, gibfalsezurück. - Setze
parent[x] = xund eine Gruppengröße von 1 für jeden Knoten. - Folge bei jeder Kante
[u, v]den Eltern vonuundvbis zu ihren Wurzeln und verweise dabei jeden durchlaufenen Knoten auf seinen Großelternknoten. - Gleiche Wurzeln: Gib
falsezurück. - Unterschiedliche Wurzeln: Hänge die Wurzel der kleineren Gruppe an die andere an und addiere ihre Größe.
- Wenn jede Kante zwei Gruppen zusammengeführt hat, gib
truezurück.
def validTree(n, edges):
# A tree on n nodes has exactly n-1 edges.
if len(edges) != n - 1:
return False
parent = list(range(n)) # every node starts as its own group
size = [1] * n
def find(x):
# Walk up to the 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)
# The two ends are already joined: this edge closes a cycle.
if a == b:
return False
# Hang the smaller group under the larger one.
if size[a] < size[b]:
a, b = b, a
parent[b] = a
size[a] += size[b]
# n-1 merges with no cycle turn the n groups into one.
return True
Stolperfallen und Grenzfälle
- Nur auf einen Zyklus zu prüfen. Drei getrennte Kanten auf sechs Knoten haben keinen Zyklus, bilden aber drei Teile.
- Nur die Anzahl der Kanten zu prüfen. Das dritte Beispiel hat
n-1Kanten, aber die Schleife 0, 1, 2 verbraucht die Kante zu Knoten 3, die benötigt wird. - Jede Kante nur unter einem ihrer Endpunkte zu speichern.
[1, 0]verbindet ebenfalls die Knoten 0 und 1, und die Suche ab Knoten 0 findet Knoten 1 nicht. - Einen Tiefensuche-Zyklustest zu verwenden, der den Elternknoten nicht überspringt. Jede Kante führt direkt zurück zu dem Knoten, von dem du gekommen bist, daher wird „besuchten Nachbarn getroffen“ bei jedem Baum ausgelöst.
- Einen langen Pfad rekursiv zu durchlaufen. Eine Linie aus 5001 Knoten geht 5000 Aufrufe tief und überschreitet damit Pythons Standardlimit von 1000; verwende einen expliziten Stack.
Häufige Fragen3
Wie hoch ist die Zeitkomplexität von Graph Valid Tree?
O(n + m) mit einer Tiefensuche, wobei m die Anzahl der Kanten ist, und O(n + m α(n)) mit Union-Find. Beide prüfen zuerst die Anzahl der Kanten, sodass ein Graph mit einer falschen Anzahl zurückgewiesen wird, bevor irgendeine Suche beginnt.
Warum hat ein Baum mit n Knoten n-1 Kanten?
Wachse den Baum von einem Knoten aus und füge die anderen einen nach dem anderen hinzu. Jeder neue Knoten kommt mit genau einer Kante hinzu: Ohne Kante wäre er abgeschnitten, und mit zwei würde er einen Zyklus schließen. Daher benötigen n Knoten n-1 Kanten.
Wie erkennt man einen Zyklus in einem ungerichteten Graphen?
Bei Union-Find schließt eine Kante, deren beide Endpunkte bereits dieselbe Wurzel haben, einen Zyklus. Bei einer Tiefensuche ist ein Zyklus ein besuchter Nachbar außer dem Knoten, von dem du gekommen bist; daher speicherst du für jeden Knoten seinen Vorgänger. Union-Find benötigt weder den Vorgänger noch eine Adjazenzliste.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
def validTree(n, edges):
# Schreibe hier den CodeTest #1
Test #2
Test #3
Argumente
n = 5 edges = [[0, 1], [0, 2], [0, 3], [1, 4]]
Erwartete Ausgabe
true