MST - Minimale Spannbäume

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;
}

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))$

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;
}