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(V + E).
Wir betrachten O(V+E) O(V+E) . Dabei nehmen wir an, dass EV |E| \geq |V| , was auf die meisten Graphen zutrifft, besonders für diejenigen, auf die wir eine Breitensuche anwenden. Dann folgt V+EE+E=2E |V| + |E| \leq |E| + |E| = 2 \cdot |E| . Da wir Konstanten in der Asymptotischen Notation vernachlässigen dürfen, erkennen wir, dass wenn EV |E| \geq |V| ist, O(V+E) O(V+E) zu O(E) O(E) wird. Wenn stattdessen jedoch E<V |E| < |V| , dann ist V+EV+V=2V |V| + |E| \leq |V| + |V| = 2 \cdot |V| , und damit wird O(V+E) O(V+E) zu O(V) O(V) . Wir vereinigen beide Fälle: O(V+E) O(V+E) bedeutet damit O(max(V,E)) O(\max(V,E)) . Allgemein: Wenn wir die Parameter x x und y y verwenden, dann bedeutet O(x+y) O(x+y) O(max(x,y)) O(\max(x,y)) .
(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 V1 | V | -1 . Ein Graph, in dem E=V1 | E | = | V | -1 ist, wird als ein Freier Baum bezeichnet.)
Wie kommt es, dass die Breitensuche in O(V+E) O (V+E) läuft? Es dauert O(V) O (V) , um den Abstand und Vorgänger für jeden Knoten zu initialisieren (genau genommen Θ(V) \Theta (V) ). 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 (V + E) , 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.
Lade