Analyse der Breitensuche

Wie lange dauert die Breitensuche in einem Graphen mit der Knotenmenge $V$V und der Kantenmenge $E$E? Die Antwort lautet $O(V + E)$O, left parenthesis, V, plus, E, right parenthesis.

Wir betrachten $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis. Dabei nehmen wir an, dass $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar, was auf die meisten Graphen zutrifft, besonders für diejenigen, auf die wir eine Breitensuche anwenden. Dann folgt $|V| + |E| \leq |E| + |E| = 2 \cdot |E|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, E, vertical bar, plus, vertical bar, E, vertical bar, equals, 2, dot, vertical bar, E, vertical bar. Da wir Konstanten in der Asymptotischen Notation vernachlässigen dürfen, erkennen wir, dass wenn $|E| \geq |V|$vertical bar, E, vertical bar, is greater than or equal to, vertical bar, V, vertical bar ist, $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis zu $O(E)$O, left parenthesis, E, right parenthesis wird. Wenn stattdessen jedoch $|E| < |V|$vertical bar, E, vertical bar, is less than, vertical bar, V, vertical bar, dann ist $|V| + |E| \leq |V| + |V| = 2 \cdot |V|$vertical bar, V, vertical bar, plus, vertical bar, E, vertical bar, is less than or equal to, vertical bar, V, vertical bar, plus, vertical bar, V, vertical bar, equals, 2, dot, vertical bar, V, vertical bar, und damit wird $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis zu $O(V)$O, left parenthesis, V, right parenthesis. Wir vereinigen beide Fälle: $O(V+E)$O, left parenthesis, V, plus, E, right parenthesis bedeutet damit $O(\max(V,E))$O, left parenthesis, \max, left parenthesis, V, comma, E, right parenthesis, right parenthesis. Allgemein: Wenn wir die Parameter $x$x und $y$y verwenden, dann bedeutet $O(x+y)$O, left parenthesis, x, plus, y, right parenthesis $O(\max(x,y))$O, left parenthesis, \max, left parenthesis, x, comma, y, right parenthesis, right parenthesis.

(Beachte übrigens, dass ein Graph verbunden ist, wenn es einen Pfad von jedem Knoten zu allen anderen Knoten gibt. Die minimale Anzahl von Kanten, die ein verbundener Graph haben kann ist $| V | -1$vertical bar, V, vertical bar, minus, 1. Ein Graph, in dem $| E | = | V | -1$vertical bar, E, vertical bar, equals, vertical bar, V, vertical bar, minus, 1 ist, wird als ein Freier Baum bezeichnet.)

Wie kommt es, dass die Breitensuche in $O (V+E)$O, left parenthesis, V, plus, E, right parenthesis läuft? Es dauert $O (V)$O, left parenthesis, V, right parenthesis, um den Abstand und Vorgänger für jeden Knoten zu initialisieren (genau genommen $\Theta (V)$\Theta, left parenthesis, V, right parenthesis). Jeder Knoten wird höchstens einmal besucht, denn nur beim ersten Besuch ist sein Abstand null, und so wird jeder Knoten höchstens einmal in die Queue eingeschrieben. Jede Kante wird höchstens zweimal untersucht: je einmal für jeden der Knoten, mit dem sie verbunden ist. Also dauert die Breitensuche $O (V + E)$O, left parenthesis, V, plus, E, right parenthesis, um alle Knoten zu besuchen.

Dieses Tutorial ist in Zusammenarbeit zwischen den Professoren Thomas Cormen und Devin Bock von Dartmouth Computer Sience und dem Khan Academy Computing Curiculum-Team entstanden und wurde von der KA Deutsch Community übersetzt. Das Tutorial ist unter der Lizenz CC-BY-NC-SA lizenziert.