MST - Minimale Spannbäume

Geschrieben von Joël Mathys.

Minimale Spannbäume

Die minimalen Spannbäume gehören zur Kategorie der Graphenprobleme. Ein minimaler Spannbaum, ist ein Baum, dessen Summe der Kantengewichte minimal ist. Doch was ist ein Baum? Als Baum bezeichnet man in der Graphentheorie einen Graphen mit \(N\) Knoten, welcher durch genau \(N-1\) Kanten so miteinander verbunden ist, dass zwischen zwei Knoten genau einen Weg gibt.

Der blaue Graph ist ein Baum. Der grüne Graph ist kein Baum, da er mehr als :math:`N-1` Kanten hat und deswegen auch einen Zyklus (Länge 4) enthält. Der weisse Graph ist ebenfalls kein Baum, da er nicht die richtige Anzahl Kanten hat und in mehrere Subgraphen aufgeteilt ist, d.h. es gibt nicht zwichen jeden zwei Punkten einen Weg.

Für einen Graphen gibt es oft mehrere verschiedene Arten wie ein Spannbaum gewählt werden kann. Uns interessiert allerdings vorallem, wie man die Summe der Kantengewichte des Baumes minimieren, respektive maximieren kann. Dieses Problem ist unter dem Namen “minimal spannender Baum” oder kurz “MST” (minimal spanning tree) bekannt. Für das MST Problem gibt es zwei bekannte Lösungsideen, die Algorithmen von Kruskal und Prim. Es kann auch sein, dass es mehrere minimale Spannbäume gibt.

Lösungsansatz Kruskal

Wir betrachten in unserem Graphen die Kante mit dem kleinsten Gewicht. Diese Kante ist sicher Teil eines gültigen Spannbaumes, sofern sie keinen Zyklus formt (die Baum-Bedingung verletzt). Stellen wir uns vor, wir haben unseren minimalen Spannbaum gefunden und wir teilen den Spannbaum in zwei Komponenten (blau, grün) auf, wobei die kleinste Kante genau zwischen den Beiden Komponenten ist. Um den gesamten Spannbaum zu konstruieren, müssen wir jetzt genau eine Kante einfügen, welche die beiden Komponenten wieder verbinden. Dazu kommen alle Kanten in Frage, welche den Startknoten im blauen und den Endknoten im grünen Bereich haben (gestrichelte Kanten). Weil wir den minimalen Spannbaum möchten, ist dies genau die kleinste Kante (alle anderen Kanten haben ein grösseres Kantengewicht), welche wir am Anfang betrachtet haben (gefüllte Kante).

Immer wenn wir eine Kante auswählen und hinzufügen, können wir uns dies auch als Verschmelzung der beiden Knoten vorstellen, welche wiederum einen Knoten bilden. Bei diesem Prozess erniedrigen wir die Anzahl Knoten immer um genau eins. Wir erhalten somit einen neuen Graphen und können das gleiche Verfahren erneut anwenden, bis nur noch ein einziger Knoten übrig bleibt. Die Abfolge der ausgewählten Kanten, welche zur “Verschmelzung” geführt haben bilden einen MST.

Die kleinste Kante (blau) befindet sich zwischen 1 und 7, deswegen ist sie Teil unseres MST. Wir können uns dies auch als “Verschmelzung” der Knoten vorstellen.

In Wirklichkeit “verschmelzen” wir die Knoten nicht, sondern unterteilen sie in verschiedene Subgraphen. Wir können dann mithilfe von Union Find effizient entscheiden, ob sich zwei Knoten im selben Subgraphen befinden (bereits “verschmelzt” worden sind) und zwei Subgraphen miteinander verbinden.

Vorgehen

  • Sortiere alle Kanten aufsteigend nach ihrem Kantengewicht
  • Nimm die kleinste Kante, bis keine Kanten mehr vorhanden sind
    • Falls die beiden Endpunkte der Kante nicht im gleichen Subgraphen liegen:
    • Kante dem minimalen Spannbaum hinzufügen
    • Subgraphen miteinander verbinden.

Als erstes sortieren wir alle Kanten nach ihrem Kantengewicht. In den SOI Aufgaben ist der Graph oft in verschiedenen “Formaten” gegeben, es kann also gut sein, dass du den Graphen in eine andere From bringen must. Für den Algorithmus von Kruskal brauchen wir alle Kanten in einem Vektor. Dabei lohnt es sich folgende Struktur zu verwenden:

// gewicht, von, zu
vector<pair<int,pair<int,int> > > edges;

Denn nun können wir die eingebaute Sortierfunktion con C++ brauchen um alle Kanten nach ihrem Gewicht zu sortieren. Dabei ist die Kante mit dem kleinsten Gewicht (kann auch negativ sein) zuvorderst im Vektor.

sort(edges.begin(), edges.end());

Um zu entscheiden ob zwei Knoten im selben Subgraphen sind (bereits “verschmelzt” wurden), brauchen wir Union Find. Dazu gibt es ein separates Skript. Nun betrachten wir alle Kanten für die Konstruktion unseres MST’s.

for(int i=0; i<(int)edges.size();i++){
        int from = edges[i].second.first;
        int to = edges[i].second.second;
        int w = edges[i].first;
        ...
    }

Wenn zwei Kanten im selben Subgraphen sind, können wir sie überspringen.

if(find(to) == find(from)){
    continue;
}

Ansonsten ist die Kante teil des minimalen Spannbaumes. Wir fügen ihr Kantengewicht dem Gesamtgewicht hinzu und verbinden die beiden Subgraphen.

unite(to, from);
weight += w;

Möchten wir statt eines minimalen Spannbaumes einen Spannbaum mit maximalen Kantengewicht finden, können wir einfach alle Kanten negieren (mit \(-1\) multiplizieren) und den gleichen Algorithus verwenden.

Implementierung

vector<int> parent;
// finde den parent von x
int find(int x){
    if(x == parent[x]){
        return x;
    }
    return parent[x] = find(parent[x]);
}
// verbinde subgraph a mit b
void unite(int a, int b){
    a = find(a);
    b = find(b);
    if(rand()%2){
        parent[a] = b;
    }else{
        parent[b] = a;
    }
}
// finde den MST nach kruskal
int kruskal(vector<vector<pair<int,int> > > &graph){
    // Kanten speichern
    vector<pair<int,pair<int,int> > > edges;
    // Gesamtgewicht des Spannbaumens
    int weight = 0;

    // Alle Kanten aus dem Graphen (Adjazenzliste) auslesen
    // parent - Vektor initalisieren
    for(int i=0;i<(int)graph.size();i++){
        parent.push_back(i);
        for(int j=0;j<(int)graph[i].size();j++){
            int from = i;
            int to = graph[i][j].first;
            int w = graph[i][j].second;
            if(from > to){continue;}
            edges.push_back({w, {from, to}});
        }
    }
    // Alle Kanten nach Kantengewicht sortieren
    sort(edges.begin(), edges.end());

    // Alle Kanten für den MST betrachten
    for(int i=0; i<(int)edges.size();i++){
        int from = edges[i].second.first;
        int to = edges[i].second.second;
        int w = edges[i].first;

        // to und from sind bereits im selbem Subgraphen, d.h. verbunden
        if(find(to) == find(from)){
            continue;
        }
        // Kante ist Teil des Spannbaumes
        unite(to, from);
        weight += w;
    }
    return weight;
}

Laufzeit- und Speicheranalyse

  • Alle Kanten des Graphen speichern \(O(m)\)
  • Union Find Struktur für jeden Knoten \(O(n)\)
  • Gesamtspeicher \(O(n+m)\)
  • Alle Kanten sortieren \(O(m \cdot log(m))\)
  • Einmal durch alle Kanten und entscheiden ob Teil des MST \(O(m*acrama)\) ~ \(O(m)\)
  • Gesmatlaufzeit \(O(m \cdot log(m))\)

Lösungsansatz Prim

Im Gegensatz zum Ansatz von Kruskal, betrachten wir nicht direkt den gesamten Graphen. Vielmehr versuchen wir den minimalen Spannbaum Schritt für Schritt von einem Startknoten aus zu konstruieren. Dabei beginnen wir bei einem beliebigen Startknoten \(S\) (weisser Knoten). Wir nehmen an, dass wir für alle anderen Knoten ausser \(S\) bereits einen minimalen Spannbaum konstruiert haben (blau).

Links die ursprüngliche Ausgangslage mit dem Startknoten S, die rote Kante ist die kleinste von S ausgehendste Kante. In der Mitte werden zwei Knoten miteinander vereint, beachte, dass es durchaus vorkommen kann, dass mehrere Kanten zum gleichen Knoten zeigen im Verlaufe des Prozesses. Rechts die Lage nach der Vereinigung dder Knoten. Beachte, dass unser neuer Knoten zwar zwei Kanten verloren , aber auch zwei neue (grüne) Kanten gewonnen hat.

Dies bedeutet, dass wir \(S\) mit diesem Spannbaum verbinden müssen. Da alle anderen Knoten ausser \(S\) bereits im Spannbaum enthalten sind, bilden wir mit jeder Kante, welche vom Knoten \(S\) ausghet einen Spannbaum (gestrichelte Linien). Da wir die Kantengewichte minimieren möchten, wählen wir die kleinste Kante, welche von \(S\) ausgeht (durchgezogene Linie). Die Wahl unserer Kante wird nicht durch den “gedachten” MST beeinflusst. Dies beduetet, dass wir für unseren Knoten in jedem Fall die kleinste Kante auswählen. Wir können uns vorstellen, dass wir diese beiden Knoten, welche die Kante verbinden, vereinen / zusammenschmelzen und sie nun wieder einen einzelnen Knoten darstellen. Nun haben wir wieder die gleiche Ausgangslage mit einem Knoten weniger. Dieses Vorgehen wiederholen wir, bis wir nur noch einen einzigen Knoten haben. Die ausgewählten Kanten bilden dann unseren MST.

Implementierung

Die Implementiertung unseres MST-Prim Algorithmus ist dem Dijkstra Algorithmus sehr ähnlich, nur fügen wir den neuen Kanten den bereits zurück gelegten Weg nicht hinzu. Denn wir möchten die Kanten alle zu unserem Vereinigungsknoten hinzufügen und nicht vom aktuellen Ort aus weitersuchen.

In unserem Beispiel wird der Graph durch eine Adjazenzliste repräsentiert. Wir definieren zugleich einige wichtige Datenstrukturen und Variablen. \(n\) entspricht der Anzahl Knoten in unserem Graphen. Für jeden Knoten speichern wir in \(visited\) , ob er bereits Teil unseres MST ist (ob wir ihn bereits vereint haben). Am Anfang sind noch keine Knoten Teil unseres MST, deswegen initialisieren wir \(visited\) mit false. Um effizient die kleinste Kante herauszufinden, speichern wir alle Kanten des “Vereinigungsknoten” in einer Priority Queue. Das oberste Element entspricht dabei der kleinsten Kante. Um unsere Suche beginnen zu könnnen fügen wir den Knoten 0 zu unserem Spannbaum hinzu (Startknoten \(S\)). Die Summe aller Kanten des minimalen Spannbaumes behalten wir in unserer \(weight\) Variable.

int prim(vector<vector<pair<int,int> > > &graph){
    int n = (int)graph.size();
    int weight = 0;

    vector<bool> visited(n,false);
    priority_queue<pair<int,int> > pq;
    pq.push({0,0});

    /* MST Suche*/

    return weight;
}

Solange wir jetzt noch Kanten in unserer Priority Queue haben, welche wir nicht betrachtet haben, konstruieren wir unseren Spannbaum weiter.

while(pq.size() != 0){
    /*Weitere Kanten betrachten*/
}

Für jede Kante, lesen wir erst die Informationen aus der Priority Queue. Anschliessend entscheiden wir, ob die Kante zu einem Knoten führt, welchen wir bereits besucht haben / bereits Teil des MST ist. Wenn \(visited[pos]\) wahr ist, ist dieser Knoten bereits Teil unseres MST und wir gehen zur nächsten Kante. Ist \(visited[pos]\) falsch, fügen wir den Knoten in unseren MST ein / speichern den Knoten als besucht ab und addieren das Kantengewicht zu unserem Gesamtgewicht des minimalen Spannbaumes.

int pos = pq.top().second
int dist = -pq.top().first;
pq.pop();

if(visited[pos] == true){
    continue;
}
visited[pos] = true;
weight += dist;

Falls wir einen neuen Knoten zu unserem minimalen Spannbaum hinzugefügt haben, müssen wir alle Kanten des neuen Knotens zu unserer Priority Queue hinzufügen. Wenn eine Kante bereits zu einem besuchten Knoten zeigt, müssen wir sie nicht erneut zu unserer Priority Queue hinzufügen.

for(int i=0;i<(int)graph[pos].size();i++){
    int next = graph[pos][i].first;
    int edge = graph[pos][i].second;
    if(visited[next] == true){
        continue;
    }
    pq.push({-edge, next});
}

Im Gegensatz zum Dijkstra Algorithmus funktioniert Prim auch mit negativen Kanten. Prim kann zudem ähnlich wie Kruskal modifiziert werden um einen maximalen Spannbaum zu suchen indem alle Kanten negiert werden (mit \(-1\) multiplizieren). #### Laufzeit- und Speicheranalyse * Für alle Knoten speichern, ob sie besucht worden sind \(O(n)\) * Alle Kanten in die Priority Queue einfügen \(O(m)\) * Gesmatspeicherverbauch \(O(n+m)\) * Jede Kante in der Priority Queue einmal betrachten \(O(m)\) * Alle Elemente in der Priority Queue sortiert halten \(O(m*log(m))\) * Entscheidung, ob bereits Teil des MST \(O(1)\) * Gesamtlaufzeit \(O(m*log(m))\)

Code Beispiel C++

int prim(vector<vector<pair<int,int> > > &graph){
    int n = (int)graph.size();
    vector<bool> visited(n, false);
    priority_queue<pair<int,int> > pq;
    pq.push({0,0});
    int weight = 0;

    while(pq.size() != 0){
        int pos = pq.top().second;
        int dist = -pq.top().first;
        pq.pop();

        if(visited[pos] == true){
            continue;
        }
        visited[pos] = true;
        weight += dist;

        for(int i=0;i<(int)graph[pos].size();i++){
            int next = graph[pos][i].first;
            int edge = graph[pos][i].second;
            if(visited[next] == true){
                continue;
            }
            pq.push({-edge, next});
        }
    }
    return weight;
}