Forschungsinstitut für Diskrete Mathematik

Übungen zur Vorlesung "Algorithmische Mathematik I"

Wintersemester 2008/09

Hinweise zur zweiten Programmieraufgabe

Instanzen:

Zum Testen sind hier einige Instanzen mit minimalen Spannbäumen angegeben:

Hier sind außerdem Instanzen, bei denen keine Lösung angegeben ist:

Bitte testen Sie Ihre Programm auch auf diesen Instanzen und geben Sie die Längen der berechneten Bäme zusammen mit Ihrem Programm ab.

Beispielprogramm:

Als Beispiel, wie eine Datenstruktur für einen gerichteten Graphen aussehen kann, und wie eine Eingabedatei, die einen Graphen kodiert, eingelesen werden kann, ist hier ein Beispielprogramm angegeben. Mit dem Compiler g++ kann es wie folgt kompiliert werden: g++ -Wall -W -pedantic *.cpp -o dfs

Das Programm berechnet in einem gerichteten Graphen mittels Tiefensuche alle vom Knoten mit Index 0 aus erreichbaren Knoten. Beachten Sie aber, dass das Eingabeformat für das Beispielprogramm etwas anders aussieht als in der Aufgabenstellung. In dem Beispielprogramm sieht eine Eingabedatei so aus:

Knotenanzahl
Anfang0 Ende0
Anfang1 Ende1
...

Jede Zeile ab der zweiten enthält also nur zwei Indizes (von 0 bis n-1, wenn n die Knotenanzahl ist). Kantengewichte gibt es nicht. Wenn Sie das Beispielprogramm verwenden wollen, müssen Sie also das Einlesen der Eingabe so erweitern, dass auch Gewichte eingelesen werden können. Eine mögliche Eingabe des Beispielprogramms, die einen Graph mit vier Knoten und drei Kanten kodiert, finden Sie hier. Der Aufruf des Programms würde dann so aussehen:
dfs instance_1

Auch die inneren Datenstrukturen müssen Sie anpassen, wenn Sie das Beispielprogramm benutzen wollen. Bisher gibt es noch keine Möglichkeit, Kantengewichte abzuspeichern, und es werden gerichtet Graphen betrachtet.

Weitere Hinweise:

Online-C++-Tutorials finden sie z.B. unter http://www.c-plusplus.de oder http://tutorial.schornboeck.net/inhalt.htm.

Nützliche Informationen zur Programmierung und zum Kompilieren gibt es auch auf den Seiten des CIP-Pools des Instituts für Angewandte Mathematik.