Spanning Tree VS. Spanning Forest

Question

Was ist der Unterschied zwischen einer Spanning Tree und einem Spanning Forest in Grafiken, konzeptionell.

Auch ist es möglich, einen Spanning Wald durch DFS oder BFS Querungen zu konstruieren? Warum? Wie?

Ich verstehe den Spanning Tree, aber ich konnte keine klaren Erklärungen über Spanning-Wälder finden. Sogar Wikipedia (https://en.wikipedia.org/wiki/Spanning_tree) gibt keine klare Definition darüber. Mein Buch (Datenstrukturen & Algorithmen, Wiley - sechste Ausgabe) hat auch keine Definition für Spanning Forests.

Ich frage mich, ob es möglich ist, eine Spanning-Gesamtstruktur durch DFS/BFS-Traversals zu erstellen, wenn wir ein Diagramm mit beispielsweise drei verbundenen Komponenten darin haben?

Answer 1

Wenn es nur eine verbundene Komponente in Ihrem gibt, die spanning tree = spanning forest.

Aber wenn es mehrere connected components in Ihrem Diagramm gibt. Zum Beispiel in folgenden Bild haben wir connected components.

Also für jeden component, werden wir eine spanning tree haben, und alle spanning treesspanning forest

bilden werde ich war frage mich, ob es einen Graphen mit zum Beispiel drei verbundenen Komponenten gibt, ist es möglich, eine Spanning Forest vonzu konstruierenDFS/BFS-Traversalen?

Ja, es ist möglich. Wenn es nur 1 gibt, wird Ihr BFS oder DFS den Besuch aller Vertices beenden und Sie werden eine spanning tree (which in this case is equal to spanning forest) haben.

Aber wenn Sie mehr als 1 haben, wie in dem Bild, das einzige, was Sie tun müssen, ist eine andere BFS oder DFS von einem unvisited Vertex zu starten. Ihr Algorithmus wird beendet, wenn kein nicht besuchte Vertex übrig ist und jeder BFS oder DFS Traversal einen spanning tree ergibt.