Wie man einen Durchlauf ausführt 01 Den Graphen bauen. Ein Preset wählen und Bauen drücken — ein Grid mit rows 4 und cols 5 ergibt 20 Knoten und 31 Einheitskanten — oder im Modus Verschieben / Verbinden nacheinander zwei Knoten anklicken, um eine Kante zu zeichnen. 02 BFS oder DFS wählen im Tab Durchlauf und eine Quelle wählen; nach dem Bauen ist die Quelle der erste Preset-Knoten. 03 Die Ergebnistabelle lesen. BFS gibt Besuchsreihenfolge, maximale Ebene, unerreichbare Knoten und Baumkanten aus; DFS gibt Preorder, Postorder und Rückwärtskanten aus; die Zeichenfläche färbt besuchte Knoten und Baumkanten. 04 Durchschreiten. Play, Zurück / Weiter und der Schieberegler laufen durch dieselben Momentaufnahmen, sodass eine Klasse die Queue oder den Stack arbeiten sieht.
Rechenbeispiele Jede Zahl unten wird aus dem Panel gelesen.
Lauf
Anzeige
Grid 4 × 5, BFS von 1-1
Besuchsreihenfolge 1-1 → 1-2 → 2-1 → 1-3 → 2-2 → 3-1 → … → 4-5 ; max. Ebene 7 ; unerreichbar — ; Baumkanten 19
Grid 4 × 5, DFS von 1-1
Preorder 1-1 → 1-2 → 1-3 → 1-4 → 1-5 → 2-5 → … → 4-1 ; Postorder beginnt 4-1 → 4-2 → 4-3 → 4-4 → 4-5 … ; Rückwärtskanten 31
Zyklus C₅, BFS von A
Besuchsreihenfolge A → B → E → C → D ; max. Ebene 2 ; Baumkanten 4
Zyklus C₅, DFS von A
Preorder A → B → C → D → E ; Postorder E → D → C → B → A
Standardgraph, BFS von A
Besuchsreihenfolge A → B → C → D → E → F ; max. Ebene 3 ; Baumkanten 5
Standardgraph, DFS von A
Preorder A → B → C → D → E → F ; Postorder F → E → D → C → B → A ; Rückwärtskanten 9
Auf dem Grid erreicht BFS die ferne Ecke in 7 Sprüngen — der Manhattan-Abstand zwischen 1-1 und 4-5 — und seine 19 Baumkanten bilden einen Spannbaum der 20 Knoten.
Die Falle mit der identischen Reihenfolge Im Standardgraphen drucken die BFS-Besuchsreihenfolge und der DFS-Preorder dieselbe Zeichenfolge, A → B → C → D → E → F , sodass die Reihenfolgezeile allein den Algorithmus nicht identifiziert. Die anderen Zeilen schon: BFS legt F in Ebene 3 , während DFS in F → E → D → C → B → A endet und 9 Rückwärtskanten zählt. In einem ungerichteten Graphen zählt die Rückwärtskanten-Zeile Bögen, nicht Kanten — das Grid meldet 31 , weil seine 31 Kanten von beiden Enden gesehen werden (19 Baumkanten und 12 Vorwärtsbögen machen die andere Hälfte von 62 aus). Lesen Sie die ganze Tabelle, nicht die erste Zeile.
Wobei Durchlauf nützlich ist Zuerst die Erreichbarkeit prüfen BFS listet jeden Knoten, den die Quelle nicht erreicht. Bauen Sie Random G(n,p) mit n 6, p 0.25, seed 20260731: Die Zeichenfläche enthält die Komponenten A, B, D, E, F und das isolierte C , und BFS von A nennt C als unerreichbar — dieselbe Aufteilung, die der Komponenten -Algorithmus als zwei Komponenten meldet, größte 5.
Queue und Stack lehren Führen Sie beide Algorithmen auf C₅ von A aus. BFS fächert zu beiden Nachbarn auf, bevor es tiefer geht (A → B → E → C → D ); DFS legt sich auf eine Richtung fest und kehrt erst am Ende um (A → B → C → D → E mit Postorder E → D → C → B → A ). Der Schrittschieberegler zeigt das Frontgebiet im einen Fall schrumpfen und im anderen wachsen.
Grenzen Sprungdistanzen, keine Gewichte. Beide Durchläufe zählen Kanten; die Gewichte, die Sie im Editor eingeben, ändern hier nichts. Gewichtete Routen gehören zum Kürzeste-Wege -Panel. Eine Quelle nach der anderen. Es gibt kein Multi-Source-BFS: Führen Sie die Quellen nacheinander aus. Das Panel fasst den Graphen auch nicht zusammen (Durchmesser, Taillenweite, Zentralität) und ordnet ihn nicht topologisch — das liegt in Kennzahlen & Zentralität und Ordnung & Konnektivität .
Die Richtung folgt dem Schalter. In einem gerichteten Graphen folgen beide Suchen nur Pfeilen; Knoten, die über eine eingehende Kante erreicht werden, bleiben unerreichbar, bis Sie den Schalter zurückstellen.
Datenschutz Graphbearbeitung und beide Suchen laufen in Ihrem Browser; nichts wird hochgeladen, und der letzte Graph bleibt im lokalen Speicher, bis die Seitendaten gelöscht werden.
Referenzen
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms , 4. Aufl., MIT Press, 2022, mitpress.mit.edu (访问日期:2026-10-07)— BFS und DFS, Queue- und Stack-Disziplin.
Wikipedia, Breadth-first search , en.wikipedia.org (访问日期:2026-10-07)— Ebenen, Distanz und Baumkanten.
Wikipedia, Depth-first search , en.wikipedia.org (访问日期:2026-10-07)— Preorder, Postorder und Rückwärtskanten.
Calculators in this hub
Hand-picked tools, one click away. The mini versions compute live and carry your values into the full calculator.
Sources & review
Updated 2026-10-07