Aus Graphen einen Spannbaum erzeugen

[Java-NewBee]

Hallo Leute,

Ich habe Probleme mit einer Aufgabe...

Es ist aus einem ungerichteten Graphen der Spannbaum zu erstellen und anschließend soll eine Breiten- und Tiefensuche durchgeführt werden.

Wie sieht der Spannbaum dieses Graphen aus? Wie kann ich diesen erstellen bzw. ermitteln?

Wäre super, wenn ihr mir weiterhelfen könnt!

MfG

 

[Beni]

Das ist kein "löst mir mal die Hausaufgaben"-Forum! Lies dich gefälligst selbst in die Materie ein. Z.B. auf Wikipedia gibt es einen langen Bericht, und auch google wird 1000 Informationen liefern.

 

[Java-NewBee]

Hier soll mir niemand die "Hausaufgaben" lösen!

Ich dachte da an eine kleine Hilfe oder einen vernünftigen Tip. Es ist ja wohl mögliche eine Antwort zu geben ohne die komplette Lösung abzuliefern, oder?

Ich habe bereit einiges gelesen und auch schon eine Idee, die ihr ja vielleicht mal beurteilen könnt...

Vielen Dank!

MfG

 

[Wildcard]

Das ist zwar ein spannender Baum, aber noch kein minimal spannender Baum (Falls das gefordert ist).
Auf der Wiki Seite steht doch schon ein fertiger Algorithmus. Einfach nur 'nachkochen' :wink:

 

[Java-Newbee]

Danke schonmal!

Es ist zwar in der Aufgabe nichts von einem minimalem Spannbaum gesagt aber ich denke es wird schon nicht schaden wenn er minimal ist. :wink:

Ich habe für den minimalen Spannbaum diesen hier bekommen... Richtig?

Danke.

 

[Wildcard]

Hab ihn zwar jetzt nicht komplett kontrolliert, aber immerhin beim überfliegen keine falsche Kante gefunden.
Sieht doch schon ganz gut aus