Topologische Sortierung

Geschrieben von Luc Haller und Raphael Fischer.

Dieser Artikel setzt voraus, dass du schon weisst was ein Graph ist und wie Tiefensuche (DFS) funktioniert. Du solltest also zuerst die entsprechenden Artikel lesen.

Problembeschreibung

Das Ziel von Toposort ist, eine bestimmte Reihenfolge der Knoten eines gerichteten Graphen zu finden. Konkreter haben wir einen gerichteten Graphen und wollen die Knoten in eine Reihenfolge bringen, so dass alle Kanten von links nach rechts zeigen. Zum Beispiel haben wir eine Liste von Abhängigkeiten von verschiedenen Aufgaben, wobei einige erst erledigt werden können, nachdem andere fertig sind. Das Ziel ist, eine Reihenfolge der Aufgaben zu finden, so dass jede erledigt werden kann. Somit müssen alle ihre Abhängigkeiten schon erledigt sein, wenn eine Aufgabe drankommt. Toposort findet eine solche Reihenfolge.

Die Abhängigkeiten werden als Graph dargestellt, wobei die Aufgaben die Knoten sind und die Abhängigkeiten die Kanten. Eine Kante von Knoten A nach Knoten B stellt dar, dass A nach B kommen muss.

Beispiel

Schauen wir uns ein konkretes Beispiel an: Wir haben fünf Aufgaben: A, B, C, D, E. Wir haben die Bedingungen, dass B nach A erledigt werden muss, E nach D und E nach A.

Die Darstellung als Graph sieht dann so aus:

%3 B B A A B->A E E E->A D D E->D C C

Es gibt mehrere Möglichkeiten, die Bedingungen einzuhalten, z. B. die Reihenfolge (A, B, D, E, C).

Lösungsidee

Die erste Beobachtung ist, dass der Abhängigkeitsgraph keine Zyklen enthalten darf, damit eine topologische Sortierung existieren kann (wenn A nach B erledigt werden muss, aber auch B nach A, ist es unmöglich, eine Sortierung zu finden). Wie wir weiter unten zeigen werden, existiert für azyklische Graphen immer eine topologische Sortierung.

Die Grundidee des Algorithmus ist, dass eine Aufgabe ausgeführt werden kann, sobald alle Abhängigkeiten weg sind. In der Graph-Darstellung heisst das, dass wir Knoten löschen, die erledigt sind, und einen Knoten in die Liste einsortieren/erledigen können, sobald er keine ausgehenden Kanten mehr hat.

Um diese Idee effizient umzusetzen, führen wir eine modifizierte DFS durch. Wir starten DFS an einem beliebigen Knoten, d. h. wir folgen Kanten zu unbesuchten Knoten solange es geht und merken uns den Pfad, den wir genommen haben. Falls wir eine Kante zu einem schon weiter oben im Pfad besuchten Knoten antreffen, hat der Graph einen Zyklus, also existiert keine Lösung. Sonst sind wir am Ende bei einem Knoten ohne ausgehende Kante, also einem Knoten, den wir jetzt in die Ausgabeliste schreiben können. Von hier aus geht die DFS zurück zum vorherigen Knoten im Pfad etc. Dabei schreiben wir Knoten immer dann in die Ausgabeliste, wenn sie aus dem aktuellen DFS-Pfad entfernt werden (d. h. wenn wir sie auf dem Rückweg wieder verlassen). Falls am Ende der DFS noch nicht alle Knoten besucht worden sind, wiederholen wir das ganze von einem noch unbesuchten Knoten, wobei wir alle schon bearbeiteten Knoten ignorieren, falls wir eine Kante finden, die uns dorthin führt.

Aus der obigen Erklärung folgt, dass wir einen Knoten erst dann in die Ausgabeliste schreiben, wenn alle seine ausgehenden Nachbarn schon erledigt wurden, also ist die Ausgabe eine korrekte topologische Sortierung. Wir sehen auch, dass der Algorithmus immer eine topologische Sortierung findet, falls kein Zyklus existiert. Also existiert für jeden gerichteten azyklischen Graphen eine.

Die Laufzeit ist die von DFS plus was wir für das Einfügen in die topologische Sortierung brauchen, also \(O(n+m) + O(n) = O(n+m)\), wobei \(n\) die Anzahl Knoten und \(m\) die Anzahl Kanten ist. Der Speicherverbrauch ist auch der von DFS plus \(O(n)\), also immer noch \(O(n)\).

Durchführen am Beispiel

Wir können den Algorithmus von Hand am Beispiel von oben ausprobieren. Eine mögliche Ausführung von Toposort ist wie folgt: - Wir beginnen bei A. A hat keine ausgehenden Kanten, also geben wir A aus. - Wir beginnen erneut bei B. Wir ignorieren die Kante zu A, da wir A schon bearbeitet haben. Sonst hat B hat keine ausgehenden Kanten, also geben wir B aus. - Wir beginnen erneut bei E. Wir ignorieren wieder die Kante zu A, da A schon bearbeitet ist. Wir merken uns E als aktuellen Pfad und gehen zu D. - D hat keine ausgehenden Kanten, also geben wir D aus, und gehen zurück zu E. - E hat keine ausgehende Kante zu einem unbearbeiteten Knoten mehr, also geben wir E aus. - Wir beginnen erneut bei C. C hat keine ausgehenden Kanten, also geben wir C aus.

Insgesamt ist die Ausgabe also A B D E C.

Implementation

#include <iostream>
#include <vector>
using namespace std;

// Führe eine Tiefensuche durch, beginnend bei Knoten v, und füge dabei die Knoten in Toposort-Reihenfolge in out ein.
// Gibt true zurück, falls ein Zyklus gefunden wurde, sonst false.
bool dfs(const vector<vector<int>>& g, vector<bool>& visited, vector<bool>& currentsearch, vector<int>& sorted, int v) {
    visited[v] = true; // haben den Knoten bearbeitet
    currentsearch[v] = true; // Knoten ist jetzt im aktuellen Suchpfad
    for(int next: g[v]) {
        if(currentsearch[next]) // Zyklus gefunden
            return true;
        if(visited[next]) // ignoriere schon bearbeitete Knoten
            continue;
        if(dfs(g, visited, currentsearch, sorted, next)) // führe DFS rekursiv von w aus aus
            return true;
    }
    sorted.push_back(v);
    currentsearch[v] = false; // Knoten ist nicht mehr im aktuellen Suchpfad.
    return false;
}

// Gibt eine topologische Sortierung der Knoten vom Graphen g zurück, oder einen leeren vector falls keine existiert.
vector<int> toposort(const vector<vector<int>>& g) {
    int n = g.size();
    vector<bool> visited(n, 0);
    vector<int> sorted;
    vector<bool> currentsearch(n, 0); // gibt an, ob ein Knoten im aktuellen Suchpfad ist
    for(int i=0; i<n; ++i) {
        if(visited[i])
            continue;
        if(dfs(g, visited, currentsearch, sorted, i))
            return vector<int>(); // DFS hat einen Zyklus im Graphen gefunden, also existiert keine topologische Sortierung.
    }
    return sorted;
}

int main() {
    // Wir lesen den Graphen im üblichen Format ein und speichern ihn als Adjazenzliste.
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i=0; i<m; ++i) {
        int v, w;
        cin >> v >> w;
        g[v].push_back(w);
    }
    // Nun können wir unsere Toposort-Funktion aufrufen.
    vector<int> ts = toposort(g);
    // Wir geben das Resultat aus.
    if(n != 0 && ts.size() == 0)
        cout << "Es existiert keine topologische Sortierung.\n";
    else {
        cout << "Eine mögliche topologische Sortierung der Knoten: ";
        for(int v: ts)
            cout << v << " ";
        cout << "\n";
    }
}

Vielleicht fragst du dich, wieso wir den Graphen als const vector<vector<int>>& g in die Funktion toposort übergeben, und nicht einfach als vector<vector<int>> g. Das & bedeutet, dass der Graph nicht kopiert wird für den Funktionsaufruf, sondern das originale Objekt verwendet wird. Das const bedeutet, dass wir ihn nicht verändern in der Funktion. Der Unterschied ist also einfach, dass wir Laufzeit und Speicher sparen, weil keine unnötige Kopie gemacht wird.

Erkennen von Zyklen

Wie oben erwähnt erkennt dieser Algorithmus zusätzlich, ob es überhaupt eine topologische Sortierung gibt. Dies macht er, indem er prüft, ob der Graph einen Zyklus enthält. Im Gegensatz zu ungerichteten Graphen, genügt es hier allerdings nicht, zu testen, ob nur zuvor unbesuchte Knoten gefunden werden. Hier muss getestet werden, ob ein neu gefundener Knoten auf dem Pfad (den die DFS genommen hat) vom Startknoten zum aktuellen Knoten liegt. Dies wird mithilfe des Vektors currentsearch gemacht: Jeder Eintrag currentsearch[v] ist true falls der Knoten v in diesem Pfad ist.

Beispiel: Die Tiefensuche hat bei a gestartet und ist schon über alle bunten Kanten gegangen. Die blauen Knoten (also d) sind nur in visited markiert, die roten Knoten (a, b, c, e) auch in currentsearch. Beachte, dass es bei d keinen Zyklus hat, obwohl wir in einem (blauen) Schritt eine zweite Kante zu diesem schon besuchten Knoten gefunden haben. Bei der orangen Kante wird gerade ein Zyklus detektiert, da b im aktuellen Pfad ist:

%3 a a b b a->b e e a->e c c b->c d d b->d c->d c->e e->b

Alternativer Algorithmus

Es gibt noch einen alternativen Algorithmus zur Bestimmung der topologischen Sortierung:

  1. Man suche eine Senke und gebe ihr die nächst kleinste Nummer.
  2. Alle Knoten, die mit der gefundenen Senke verbunden sind, werden später eine grössere Nummer erhalten.
  3. Entferne die gefundene Senke und alle Kanten, die zu ihr hin zeigen. Der entstandene Graph ist wieder ein DAG.
  4. Gehe zu 1.

Dieser Algorithmus kann mit BFS implementiert werden. Wenn man ihn richtig implementiert, hat er ebenfalls Laufzeit \(O(n + m)\). Die Implementierung mittels Tiefensuche ist aber meist einfacher.