Algorithmus aufspannender baum bei Graphen

Archiv Algorithmik II
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

Algorithmus aufspannender baum bei Graphen
Sers, kann es sein das der Algorithmus im Script nicht stimmt.
Jedenfalls komme ich nicht auf ne Lösung wenn ich mit dem rekursiven
Alg. die Zyklen entfernen will. Hat jemand nen funktionierenden, oder
kanns mir jemand erklären.

Mfg Majeeks

3

klaro
ok…
der algo im skript ist brauchbar (zur abwechslung) allerdings (und das is nicht neu) unuebersichtlich formuliert.

in meiner implementierung ist adj die adjanzen matrix des ausgangsgraphen und spanTree die adjanzenz Matrix des Spanning Trees. visited ist ein bool’sches array und der parameter k der knoten von dem der spanning tree aufgespannt wird.

private void sTree(int k) {
	visited[k] = true;
	for(int i = 0; i < vertices.length; i++) {
		if(spanTree[k][i] != 0) {
			if(!visited[i]) {
				visited[i] = true;
				sTree(i);
			} else
				spanTree[k][i] = 0;
		}
	}
}

ich denke er is richtig und passt auch

mfg

die hackfresse nr1