URL:         /axel/graph_ws0001_blatt2.html
 

Aufgabe 3 - Kruskal - (4 Punkte)

Verwenden Sie den Algorithmus von Kruskal um einen minimalen spannenden Baum zu folgendem Graph zu finden (Beschreiben Sie die einzelnen Schritte genau)

Aufgabe 4 - BFS (4 Punkte + 4 Programmierpunkte)

Verwendet man BFS um z.B. Zusammenhangskomponenten eines Graphen zu finden ist es nötig schnell, d.h. mit O(1) einen noch 'unverbrauchten Knoten' zu bekommen. Entwerfen Sie eine derartige Datenstruktur. Sowohl das Markieren eines Knoten als verbraucht, als auch der Zugriff auf den nächsten unverbrauchten Knoten soll mit O(1) funktionieren. Das Initialisieren soll mit O(n) funktionieren, wobei n die Anzahl der Knoten ist.

Implementieren Sie den BFS Algorithmus, Ergebnis soll eine Routine bfs(int *nachbarschaftsliste, int startknoten, int *durchlaufreihenfolge) sein. Die verwendete Datenstruktur für die Nachbarschaftsliste ist  hier dokumentiert. 

Abgabe mit ausführlichen Kommentar und Namen bis 10.11. unter der email axel.kohnert@uni-bayreuth.de