/* Vorbereitung mit Aufbau des Heaps, kostet O(n log n) */
for (i=1; i<=n; i++) {
H.insert ( (A[i], A[i].getChildrenCount()) );
}
/* Finden der unabhängigen Elemente - wird im schlimmsten Fall
n-mal durchlaufen, wenn alle Knoten ohne Nachbarn sind */
while (H.isEmpty() == false) {
/* Element mit kleinstem Grad holen (die Wurzel des Heaps)
und dieses Element vom Heap entfernen */
minidx = H[1];
H.remove (1); /* <- kostet O(log n) */
/* Löschen der Nachbarn von Knoten minidx - wird maximal
n-mal durchlaufen, bis keine Knoten mehr da sind... */
foreach (x in A[minidx]) {
/* löschen "Referenzen" auf Knoten x von den Nachbarn von x,
das entspricht den Kanten des Graphen und ist in der Summe
über alle Schleifen maximal m = # Kanten der Fall. */
foreach (y in A[x]) {
A[y].remove (x);
/* setze auch die Priorität um eins herab, da ein Nachbar
weniger auch einen Grad weniger bedeutet - kostet O(log n) */
H.change_priority ( y, priority(y) -1 );
}
/* nachdem die "Referenzen" gelöscht sind auch die Knoten
selbst aus der Adjanzenzliste und dem Heap löschen */
A.remove (x);
H.remove (x); /* <- kostet O(log n) */
}
/* Element minidx aus Adjazenzliste löschen und in Stack
der unabhängigen Knoten einfügen */
A.remove (minidx);
W.add (minidx);
}
Die Operationen auf der Adjazenzliste sind vernachlässigbar, teurer die Löschaktionen auf dem Heap. Im schlimmsten Fall wird hier O(log n) pro gelöschtem Element nötig. Da die while-Schleife im schlimmsten Fall n mal durchlaufen wird, haben wir schon O (n log n).
Wie sieht es mit den foreach-Loops aus? Der Loop, der die Nachbarn des selektierten Knoten minidx abläuft (also der äußere), wird höchstens n mal aufgerufen (mehr Elemente x gibt es schließlich nicht!). Diese Laufzeit O (n log n) addiert sich zur Laufzeit der Hauptschleife.
Die innere foreach-Schleife verdient aber noch Beachtung: Hier werden immerhin alle Kanten des Graphen abgelaufen und eine Heap-Modifizierung vorgenommen (change_priority). Die Summe der Kanten (also alle Kanten im Graphen) sei m. Dann haben wir hier noch O (m log n).
Zusammen gibt das: O ((n+m) log n)
Klicke hier, um zurück zur Hauptseite zu gehen.