Kruskals Algorithmus ist ein Minimum-Spanning-Tree-Algorithmus, der einen Graphen als Eingabe nimmt und eine Teilmenge der Kanten dieses Graphen findet, die einen Baum bildet, der jeden Scheitelpunkt enthält und auch die minimale Summe von Gewichten unter allen Bäumen hat, aus denen gebildet werden kann ein Graph.
Wie der Kruskal-Algorithmus funktioniert
Es fällt unter eine Klasse von Algorithmen, die als "gierige" Algorithmen* bezeichnet werden und ein lokales Optimum in der Hoffnung finden, ein globales Optimum zu finden.
Wir beginnen mit den Kanten mit dem geringsten Gewicht und fügen Kanten hinzu, bis wir unser Ziel erreicht haben.
Die Schritte zur Implementierung des Kruskal-Algorithmus sind wie folgt:
- Sortieren Sie alle Kanten von geringem bis hohem Gewicht.
- Nimm die Kante mit dem kleinsten Gewicht und füge sie dem Spannbaum hinzu. Wenn das Hinzufügen einer Kante einen Zyklus erzeugt hat, lehnen Sie diese Kante ab.
- Fügen Sie weitere Kanten hinzu, bis Sie alle Scheitelpunkte erreicht haben.
Beispiel für den Kruskal-Algorithmus
Kruskals Algorithmus. Pseudocode.
Jeder Minimum-Spanning-Tree-Algorithmus dreht sich darum, zu prüfen, ob eine Kante einen Zyklus erzeugt oder nicht.
Der gebräuchlichste Weg, dies herauszufinden, ist der Union FInd-Algorithmus . Der Union-Find-Algorithmus unterteilt die Scheitelpunkte in Cluster und ermöglicht es uns zu prüfen, ob zwei Scheitelpunkte zum selben Cluster gehören oder nicht, und somit zu entscheiden, ob das Hinzufügen einer Kante einen Zyklus erzeugt.
KRUSKAL(G): A = ∅ For each vertex v ∈ G.V: MAKE-SET(v) For each edge (u, v) ∈ G.E ordered by increasing order by weight(u, v): if FIND-SET(u) ≠ FIND-SET(v): A = A ∪ {(u, v)} UNION(u, v) return A
Implementierung des Kruskal-Algorithmus in C++
Es folgt der Code für die Implementierung in C++. Wir verwenden Standard-Vorlagenbibliotheken, um unsere Arbeit einfacher und sauberer zu machen.
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define edge pair<int,int> class Graph { private: vector<pair<int, edge>> G; // graph vector<pair<int, edge>> T; // mst int *parent; int V; // number of vertices/nodes in graph public: Graph(int V); void AddWeightedEdge(int u, int v, int w); int find_set(int i); void union_set(int u, int v); void kruskal(); void print(); }; Graph::Graph(int V) { parent = new int[V]; //i 0 1 2 3 4 5 //parent[i] 0 1 2 3 4 5 for (int i = 0; i < V; i++) parent[i] = i; G.clear(); T.clear(); } void Graph::AddWeightedEdge(int u, int v, int w) { G.push_back(make_pair(w, edge(u, v))); } int Graph::find_set(int i) { // If i is the parent of itself if (i == parent[i]) return i; else // Else if i is not the parent of itself // Then i is not the representative of his set, // so we recursively call Find on its parent return find_set(parent[i]); } void Graph::union_set(int u, int v) { parent[u] = parent[v]; } void Graph::kruskal() { int i, uRep, vRep; sort(G.begin(), G.end()); // increasing weight for (i = 0; i < G.size(); i++) { uRep = find_set(G[i].second.first); vRep = find_set(G[i].second.second); if (uRep != vRep) { T.push_back(G[i]); // add to tree union_set(uRep, vRep); } } } void Graph::print() { cout << "Edge :" << " Weight" << endl; for (int i = 0; i < T.size(); i++) { cout << T[i].second.first << " - " << T[i].second.second << " : " << T[i].first; cout << endl; } } int main() { Graph g(6); g.AddWeightedEdge(0, 1, 4); g.AddWeightedEdge(0, 2, 4); g.AddWeightedEdge(1, 2, 2); g.AddWeightedEdge(1, 0, 4); g.AddWeightedEdge(2, 0, 4); g.AddWeightedEdge(2, 1, 2); g.AddWeightedEdge(2, 3, 3); g.AddWeightedEdge(2, 5, 2); g.AddWeightedEdge(2, 4, 4); g.AddWeightedEdge(3, 2, 3); g.AddWeightedEdge(3, 4, 3); g.AddWeightedEdge(4, 2, 4); g.AddWeightedEdge(4, 3, 3); g.AddWeightedEdge(5, 2, 2); g.AddWeightedEdge(5, 4, 3); g.kruskal(); g.print(); return 0; }
Wenn wir das Programm ausführen, erhalten wir eine Ausgabe wie:
Edge : Weight 1 - 2 : 2 2 - 5 : 2 2 - 3 : 3 3 - 4 : 3 0 - 1 : 4
Kruskals Algorithmus vs. Prima
Der Algorithmus von Prim ist ein weiterer beliebter Minimum-Spanning-Tree-Algorithmus, der eine andere Logik verwendet, um den MST-Graphen zu finden. Anstatt an einer Kante zu beginnen, beginnt der Algorithmus von Prim an einem Scheitelpunkt und fügt die am wenigsten gewichteten Kanten hinzu, die sich nicht im Baum befinden, bis alle Scheitelpunkte abgedeckt sind.
Я так понимаю, это перевод статьи?
Вот такие фразы выглядят стремно: "Любой минимальный алгоритм остовного дерева"
"популярным алгоритмом минимального остовного дерева"
Возможно, должно быть "алгоритмом построения ..."
Первое предложение тоже несогласованное.
Странной кажется идея запихивания графа в класс. Да и все равно можно выстрелить в ногу, вызвав print до вызова kruskal.
Не очевидна связь приведенного кода с описанным алгоритмом. - Что это за массив parent и почему (кстати) он не уничтожается в деструкторе?
Псевдокод не понятный. Что делает функция UNION(u, v) ?
Обе строки 7 и 8 вложены внутрь блока if?
У нормальной реализации алгоритма сложность N*log(N). А у вас для каждого узла графа вызывается функция find_set, которая имеет трудоемкость O(N). И того - O(N^2). Функция find_set при этом вообще особо кривая. Не понятно что она должна вернуть в каком случае.
Ну и еще, вот эта структура выглядит очень плохо:
> G;
vector
Ну потому что edge - это тоже pair и в результате, во всех этих second.first и second.second хрен разберешься. Отрефакторить можно, например, введением нормальной структуры для дуги (вместо пары). При этом, в эту же дугу стоит засунуть длину. Легко ли въехать где тут номер дуги, а где - ее длина?