Minimal Spanning Tree mit Greedy

[Malcolm X]

Hallo,

Es geht um das Minimal Spanning Tree (MST) Problem. Ich habe die Aufgabe dieses Problem mit Hilfe des Greedy Algorithmus zu lösen. Nun existiert ja zur Lösung dieses Problems auch noch der Kruskal Algorithmus. Ist der Kruskal Algorithmus eine spezielle Greedy Variante oder verfolgt dieser Algorithmus einen anderen Ansatz.

 

[Malcolm X]

Nun weiss ich wie ich das Problem zu lösen habe:

zunächst sollen die Kanten des Graphen aufsteigend nach Gewicht sortiert werden.

des weiteren soll der Greedy Algorithmus mit dem Teilmengensystem (E,U) zur Lösung verwendet werden. U stellt hier alle zyklenfreien Teilmengen von E dar.

Frage 1
--------

Wie ich festellen kann ob ein gegebener Graph zyklenfrei ist mir klar. Probleme habe ich allerdings damit alle zyklenfreien Teilmengen aus E zu ermitteln. Könnt ihr mir sagen wie das geht?


Frage 2
--------

Mal angneommen ich habe nun alle zyklenfreien Teilmengen aus E ermittelt. Wir geht es denn nun weiter um den mimimalen Spannbaum zu finden. Laut des Greedy Algorithmus müßte das doch folgendermaßen funktionieren:

1.) Alle Elemente in E (also alle Kanten) nach Gewicht sortieren.

2.) zunächst ist die Lösung T leer

3.) Nun werden in einer for-Schleife die sortiereten Kanten durchlaufen

4.) Wenn nun die Kante im aktuellen Schleifendurchlauf vereinigt mit der Lösung T in der Menge der zyklenfreien Teilmengen (von dehnen ich nicht weiss wie ich sie ermitteln soll) von E enthalten ist dann wird die Kante zur Lösung hinzugefügt.

5.) Am Ende sollte der Algorithmus nun den minimalen Spannbaum des Graphen zurückliefern.


Ist das soweit korrekt?

 

[bygones]

zu Frage 1:

einfache tiefensuche mit knotenmarkieren. Triffst du auf einen schon markierten Knoten hast du einen Zykluis