DFS Entdeckung und Endzeiten

Question

Angenommen, wir DFS auf diesem Diagramm durchführen, indem Sie die folgenden Regeln gehorchen:

• Start von Vertex 1.

• An jeder Ecke, Prozess seine Out-Nachbarn in aufsteigender Reihenfolge Ich würde.

• Jedes Mal, wenn wir neu starten müssen, tut es aus dem weißen Scheitel mit dem kleinsten id

den resultierenden DFS Wald zeigen. Außerdem geben Sie für jeden Eckpunkt die Erkennungszeit und die Endzeit an. # Auch/= entdeckt und #/# = fertig

dfs Baum wie folgt:

   6 
       | 
1--2--7--3--4--5--8 

die Frage mich fragen, die sich ergebende Wald zu zeigen, aber ich bin produzieren nur einen Baum , was habe ich falsch gemacht?

Answer 1

Sie haben nichts verpasst. Ein Wald ist eine Menge von Graphen und erlaubt daher sogar, 0 Graphen zu enthalten. So ist der Graph-Forst in Ihrem Ergebnis absolut gültig. Einige Dozenten neigen dazu, ihre eigene Definition zu verwenden, also würde ich empfehlen, das mit Ihrem Skript zu überprüfen. Wie für die DFS-Traversal ist es perfekt gültig und ziemlich einfach zu zeigen, dass es einen Pfad von 1 bis Knoten im Baum