Kruskal-Algorithmus Zusammenhangskomponenten |
| 10.05.2016, 15:35 | Auf diesen Beitrag antworten » |
| blubbiblubb | 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 
|
|
|
|
| 10.05.2016, 22:33 | Auf diesen Beitrag antworten » |
| eulerscheZahl | Kreise brauchst du da nicht. Es kann ja auch sein, dass der Graph bei n Knoten keine (n-1) Kanten hat. Mein Vorschlag: grenze die Suche bei den Kanten ein (vergleiche Algorithmus von Prim). Dann kriegst du auf jeden Fall einen zusammenhängenden Teilgraphen. Wenn noch Knoten übrig sind, wiederhole die Suche auf dem Restgraphen. |
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
|
| Die Neuesten » |
