Geschrieben von blubbiblubb am 10.05.2016 um 15:35:
Kruskal-Algorithmus Zusammenhangskomponenten
Meine Frage:
Hallo zusammen,
ich muss folgende Aufgabe bearbeiten: In dieser Aufgabe wollen wir die Zusammenhangskomponenten eines ungerichteten Graphen mit einem modifizierten Kruskal-Algorithmus bestimmen. Zur Erinnerung: Ein kantengewichteter ungerichteter Graph G = (V, E, c) heißt zusammenhängend, falls für alle v, w Element von V ein ungerichteter Weg von v nach w in G existiert. Eine Zusammenhangskomponente ist ein maximal zusammenhängender Teilgraph. Damit zerfallen unzusammenhängende Graphen in ihre Zusammenhangskomponenten. Wie muss man den Algorithmus von Kruskal anpassen, damit dieser die Zusammenhangskomponenten von G berechnet? Geben Sie Pseudocode an und erklären Sie das Funktionsprinzip.
Hinweis: Sie k¨onnen die Zusammenhangskomponenten als Liste/Menge von Knoten re-
pr¨asentieren.
Meine Ideen:
Den Kruskal-Algorithmus selbst verstehe ich in der Praxis ziemlich gut. Meine einzige Idee ist, dass sich ein Baum in 2 Teilbäume, also zwei Zusammenhangskomponenten aufteilt, wenn sich irgendwo ein Kreis bildet (wobei das doch gar nicht erlaubt ist?!).
Ich hoffe mir kann jemand helfen. Danke schon mal
