Мінімальне остовне дерево (MST) або охоплююче дерево з мінімальною вагою для зваженого зв’язного неорієнтованого графа — це охоплююче дерево з вагою, меншою або рівною вазі будь-якого іншого охоплюючого дерева. Щоб дізнатися більше про Minimum Spanning Tree, див Ця стаття .
Вступ до алгоритму Крускала:
Ось і обговоримо Алгоритм Крускала щоб знайти MST даного зваженого графа.
В алгоритмі Крускала відсортуйте всі ребра даного графа в порядку зростання. Потім він продовжує додавати нові ребра та вузли в MST, якщо щойно додане ребро не утворює цикл. Спочатку він вибирає мінімально зважену грань, а нарешті – максимальну. Таким чином, ми можемо сказати, що він робить локально оптимальний вибір на кожному кроці, щоб знайти оптимальне рішення. Отже, це a Нижче наведено кроки для пошуку MST за допомогою алгоритму Крускала:
- Відсортуйте всі ребра в порядку не зменшення їх ваги.
- Виберіть найменший край. Перевірте, чи він утворює цикл із сформованим до цього часу остовним деревом. Якщо цикл не утворився, включите це ребро. Інакше відкиньте його.
- Повторюйте крок №2, доки в охоплюючому дереві не буде ребер (V-1).
Крок 2 використовує Алгоритм Union-Find для виявлення циклів.
Тому ми рекомендуємо прочитати наступну публікацію як попередню умову.
- Алгоритм об'єднання-знаходження | Набір 1 (виявлення циклу на графіку)
- Алгоритм об'єднання-знаходження | Набір 2 (об’єднання за рангом і стисненням шляху)
Алгоритм Крускала для пошуку охоплюючого дерева з мінімальною вартістю використовує жадібний підхід. Жадібний вибір полягає в тому, щоб вибрати найменшу вагову грань, яка не викликає циклу в створеному на даний момент MST. Зрозуміємо це на прикладі:
Ілюстрація:
Нижче наведено ілюстрацію вищезазначеного підходу:
Вхідний графік:
Граф містить 9 вершин і 14 ребер. Отже, мінімальне сформоване остовне дерево матиме (9 – 1) = 8 ребер.
Після сортування:
вага Джерело Пункт призначення 1 7 6 2 8 2 2 6 5 4 0 1 4 2 5 6 8 6 7 2 3 7 7 8 8 0 7 8 1 2 9 3 4 10 5 4 одинадцять 1 7 14 3 5 Тепер виберіть усі ребра одне за одним із відсортованого списку ребер
Крок 1: Підберіть ребро 7-6. Цикл не формується, включайте його.
оператор if else javaДодайте край 7-6 у MST
Крок 2: Підберіть ребро 8-2. Цикл не формується, включайте його.
Додайте край 8-2 у MST
крок 3: Ребро підберіть 6-5. Цикл не формується, включайте його.
Додайте край 6-5 у MST
крок 4: Підібрати перевагу 0-1. Цикл не формується, включайте його.
Додайте край 0-1 у MST
крок 5: Виберіть ребро 2-5. Цикл не формується, включайте його.
Додайте край 2-5 у MST
Крок 6: Підберіть ребро 8-6. Оскільки включення цього краю призводить до циклу, відкиньте його. Виберіть ребро 2-3: Цикл не формується, включайте його.
Додайте край 2-3 в MST
Крок 7: Підберіть ребро 7-8. Оскільки включення цього краю призводить до циклу, відкиньте його. Виберіть ребро 0-7. Цикл не формується, включайте його.
Додайте край 0-7 у MST
css для обтікання текстомКрок 8: Виберіть край 1-2. Оскільки включення цього краю призводить до циклу, відкиньте його. Виберіть ребро 3-4. Цикл не формується, включайте його.
Додайте край 3-4 у MST
Примітка: Оскільки кількість ребер, включених до MST, дорівнює (V – 1), алгоритм зупиняється на цьому
Нижче наведено реалізацію вищезазначеного підходу:
C++
// C++ program for the above approach> > #include> using> namespace> std;> > // DSU data structure> // path compression + rank by union> class> DSU {> >int>* parent;> >int>* rank;> > public>:> >DSU(>int> n)> >{> >parent =>new> int>[n];> >rank =>new> int>[n];> > >for> (>int> i = 0; i parent[i] = -1; rank[i] = 1; } } // Find function int find(int i) { if (parent[i] == -1) return i; return parent[i] = find(parent[i]); } // Union function void unite(int x, int y) { int s1 = find(x); int s2 = find(y); if (s1 != s2) { if (rank[s1] parent[s1] = s2; } else if (rank[s1]>rank[s2]) { parent[s2] = s1; } else { parent[s2] = s1; rank[s1] += 1; } } } }; class Graph { vectorint>> edgelist; int V; public: Graph(int V) { this->V = V; } // Функція для додавання краю в графі void addEdge(int x, int y, int w) { edgelist.push_back({ w, x, y }); } void kruskals_mst() { // Сортувати всі краї sort(edgelist.begin(), edgelist.end()); // Ініціалізація DSU DSU s(V); int ans = 0; cout<< 'Following are the edges in the ' 'constructed MST' << endl; for (auto edge : edgelist) { int w = edge[0]; int x = edge[1]; int y = edge[2]; // Take this edge in MST if it does // not forms a cycle if (s.find(x) != s.find(y)) { s.unite(x, y); ans += w; cout << x << ' -- ' << y << ' == ' << w << endl; } } cout << 'Minimum Cost Spanning Tree: ' << ans; } }; // Driver code int main() { Graph g(4); g.addEdge(0, 1, 10); g.addEdge(1, 3, 15); g.addEdge(2, 3, 4); g.addEdge(2, 0, 6); g.addEdge(0, 3, 5); // Function call g.kruskals_mst(); return 0; }> |
>
>
C
// C code to implement Kruskal's algorithm> > #include> #include> > // Comparator function to use in sorting> int> comparator(>const> void>* p1,>const> void>* p2)> {> >const> int>(*x)[3] = p1;> >const> int>(*y)[3] = p2;> > >return> (*x)[2] - (*y)[2];> }> > // Initialization of parent[] and rank[] arrays> void> makeSet(>int> parent[],>int> rank[],>int> n)> {> >for> (>int> i = 0; i parent[i] = i; rank[i] = 0; } } // Function to find the parent of a node int findParent(int parent[], int component) { if (parent[component] == component) return component; return parent[component] = findParent(parent, parent[component]); } // Function to unite two sets void unionSet(int u, int v, int parent[], int rank[], int n) { // Finding the parents u = findParent(parent, u); v = findParent(parent, v); if (rank[u] parent[u] = v; } else if (rank[u]>rank[v]) { parent[v] = u; } else { parent[v] = u; // Оскільки ранг зростає, якщо // ранги двох наборів однакові rank[u]++; } } // Функція для пошуку MST void kruskalAlgo(int n, int edge[n][3]) { // Спочатку ми сортуємо масив країв у порядку зростання // щоб мати доступ до мінімальних відстаней/вартості qsort(edge , n, sizeof(edge[0]), компаратор); int parent[n]; int rank[n]; // Функція для ініціалізації parent[] і rank[] makeSet(parent, rank, n); // Щоб зберегти мінімальну вартість int minCost = 0; printf( 'Далі наведені ребра в побудованому MST
'); for (int i = 0; i int v1 = findParent(parent, edge[i][0]); int v2 = findParent(parent, edge[i][1]); int wt = edge[i][2] ; // Якщо батьки різні, це означає, що // об'єднати їх if (v1 != v2) { unionSet(v1, v2, parent, n); minCost += wt; '%d -- %d == %d
', edge[i][0], edge[i][1], wt } } printf('Minimum Cost Spanning Tree: %d); n', minCost); // Код драйвера int main() { int edge[5][3] = { { 0, 1, 10 }, { 0, 2, 6 }, { 0, 3, 5 } , { 1, 3, 15 }, { 2, 3, 4 } ; kruskalAlgo(5, edge); return 0;> |
>
>
Java
// Java program for Kruskal's algorithm> > import> java.util.ArrayList;> import> java.util.Comparator;> import> java.util.List;> > public> class> KruskalsMST {> > >// Defines edge structure> >static> class> Edge {> >int> src, dest, weight;> > >public> Edge(>int> src,>int> dest,>int> weight)> >{> >this>.src = src;> >this>.dest = dest;> >this>.weight = weight;> >}> >}> > >// Defines subset element structure> >static> class> Subset {> >int> parent, rank;> > >public> Subset(>int> parent,>int> rank)> >{> >this>.parent = parent;> >this>.rank = rank;> >}> >}> > >// Starting point of program execution> >public> static> void> main(String[] args)> >{> >int> V =>4>;> >List graphEdges =>new> ArrayList(> >List.of(>new> Edge(>0>,>1>,>10>),>new> Edge(>0>,>2>,>6>),> >new> Edge(>0>,>3>,>5>),>new> Edge(>1>,>3>,>15>),> >new> Edge(>2>,>3>,>4>)));> > >// Sort the edges in non-decreasing order> >// (increasing with repetition allowed)> >graphEdges.sort(>new> Comparator() {> >@Override> public> int> compare(Edge o1, Edge o2)> >{> >return> o1.weight - o2.weight;> >}> >});> > >kruskals(V, graphEdges);> >}> > >// Function to find the MST> >private> static> void> kruskals(>int> V, List edges)> >{> >int> j =>0>;> >int> noOfEdges =>0>;> > >// Allocate memory for creating V subsets> >Subset subsets[] =>new> Subset[V];> > >// Allocate memory for results> >Edge results[] =>new> Edge[V];> > >// Create V subsets with single elements> >for> (>int> i =>0>; i subsets[i] = new Subset(i, 0); } // Number of edges to be taken is equal to V-1 while (noOfEdges 1) { // Pick the smallest edge. And increment // the index for next iteration Edge nextEdge = edges.get(j); int x = findRoot(subsets, nextEdge.src); int y = findRoot(subsets, nextEdge.dest); // If including this edge doesn't cause cycle, // include it in result and increment the index // of result for next edge if (x != y) { results[noOfEdges] = nextEdge; union(subsets, x, y); noOfEdges++; } j++; } // Print the contents of result[] to display the // built MST System.out.println( 'Following are the edges of the constructed MST:'); int minCost = 0; for (int i = 0; i System.out.println(results[i].src + ' -- ' + results[i].dest + ' == ' + results[i].weight); minCost += results[i].weight; } System.out.println('Total cost of MST: ' + minCost); } // Function to unite two disjoint sets private static void union(Subset[] subsets, int x, int y) { int rootX = findRoot(subsets, x); int rootY = findRoot(subsets, y); if (subsets[rootY].rank subsets[rootY].parent = rootX; } else if (subsets[rootX].rank subsets[rootX].parent = rootY; } else { subsets[rootY].parent = rootX; subsets[rootX].rank++; } } // Function to find parent of a set private static int findRoot(Subset[] subsets, int i) { if (subsets[i].parent == i) return subsets[i].parent; subsets[i].parent = findRoot(subsets, subsets[i].parent); return subsets[i].parent; } } // This code is contributed by Salvino D'sa> |
також модель
>
>
Python3
strsep c
# Python program for Kruskal's algorithm to find> # Minimum Spanning Tree of a given connected,> # undirected and weighted graph> > > # Class to represent a graph> class> Graph:> > >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> []> > ># Function to add an edge to graph> >def> addEdge(>self>, u, v, w):> >self>.graph.append([u, v, w])> > ># A utility function to find set of an element i> ># (truly uses path compression technique)> >def> find(>self>, parent, i):> >if> parent[i] !>=> i:> > ># Reassignment of node's parent> ># to root node as> ># path compression requires> >parent[i]>=> self>.find(parent, parent[i])> >return> parent[i]> > ># A function that does union of two sets of x and y> ># (uses union by rank)> >def> union(>self>, parent, rank, x, y):> > ># Attach smaller rank tree under root of> ># high rank tree (Union by Rank)> >if> rank[x] parent[x] = y elif rank[x]>rank[y]: parent[y] = x # Якщо ранги однакові, тоді зробіть один коренем # і збільште його ранг на один: parent[y] = x rank[x] += 1 # Основна функція для створення MST # з використанням алгоритму Крускала def KruskalMST(self): # Це збереже результуючий результат MST = [] # Змінна індексу, що використовується для відсортованих країв i = 0 # Змінна індексу, що використовується для результату [] e = 0 # Сортувати всі ребра в # порядку не спадання їх # ваги self.graph = sorted(self.graph, key=lambda item: item[2]) parent = [] rank = [] # Створити V підмножин з одиничними елементами для вузла в діапазоні (self.V): parent.append(node) rank.append(0) # Кількість ребер, які потрібно взяти, менша, ніж для V-1, поки e |
>
>
C#
// C# Code for the above approach> > using> System;> > class> Graph {> > >// A class to represent a graph edge> >class> Edge : IComparable {> >public> int> src, dest, weight;> > >// Comparator function used for sorting edges> >// based on their weight> >public> int> CompareTo(Edge compareEdge)> >{> >return> this>.weight - compareEdge.weight;> >}> >}> > >// A class to represent> >// a subset for union-find> >public> class> subset {> >public> int> parent, rank;> >};> > >// V->немає. вершин & E->кількість ребер> >int> V, E;> > >// Collection of all edges> >Edge[] edge;> > >// Creates a graph with V vertices and E edges> >Graph(>int> v,>int> e)> >{> >V = v;> >E = e;> >edge =>new> Edge[E];> >for> (>int> i = 0; i edge[i] = new Edge(); } // A utility function to find set of an element i // (uses path compression technique) int find(subset[] subsets, int i) { // Find root and make root as // parent of i (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } // A function that does union of // two sets of x and y (uses union by rank) void Union(subset[] subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); // Attach smaller rank tree under root of // high rank tree (Union by Rank) if (subsets[xroot].rank subsets[xroot].parent = yroot; else if (subsets[xroot].rank>subsets[yroot].rank) subsets[yroot].parent = xroot; // Якщо ранги однакові, тоді зробіть один кореневим // і збільште його ранг на ще один { subsets[yroot].parent = xroot; підмножини[xroot].rank++; } } // Основна функція для побудови MST // за допомогою алгоритму Kruskal void KruskalMST() { // Це зберігатиме // результуючий MST Edge[] result = new Edge[V]; // Індексна змінна, яка використовується для результату [] int e = 0; // Індексна змінна, яка використовується для відсортованих країв int i = 0; for (i = 0; i result[i] = new Edge(); // Відсортувати всі ребра в неубываючому // порядку їх ваги. Якщо нам не дозволено // змінювати заданий графік, ми можемо створити // копія масиву ребер Array.Sort(edge); // Виділити пам'ять для створення підмножин V subset[] subsets = new subset[V]; ; // Створення V підмножин з одиничними елементами для (int v = 0; v subsets[v].parent = v; subsets[v].rank = 0; } i = 0; // Кількість ребер, які потрібно взяти, дорівнює до V-1 while (e // Виберіть найменше ребро. І збільште // індекс для наступної ітерації Edge next_edge = new Edge(); next_edge = edge[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); // Якщо включення цього краю не викликає циклу, // включає його в результат і збільшує індекс результату для наступного краю if (x != y) { result[e++] = next_edge; Union(subsets, x, y); } } // Друк вмісту result[] для відображення // вбудованої MST Console.WriteLine('Далі є ребра в ' + ' побудований MST'); int minimumCost = 0; for (i = 0; i Console.WriteLine(result[i].src + ' -- ' + result[i].dest + ' == ' + result[i].weight); minimumCost += result[i].weight; } Console.WriteLine('Minimum Cost Spanning Tree: ' + minimumCost(); // Код драйвера public static(String[] args) { int V = 5; Graph graph = new Graph(V, E); // додавання ребра graph.edge[0].src = 0; graph.edge[0].weight = 10; // додати край graph.edge[1].src = 0; graph.edge[1].dest = 2; graph.edge[1].weight = 6 ; // додавання ребер 0-3 graph.edge [2].src = 0; graph.edge [2].weight = 5; // додавання ребер 1-3 graph. edge[3].src = 1; graph.edge[3].dest = 3; graph.edge[3].weight = 15; // додати край 2-3 graph.edge[4].src = 2; .edge[4].dest = 3; graph.edge[4].weight = 4; // Виклик функції graph.KruskalMST(); } // Цей код створено Aakash Hasija> |
>
>
Javascript
> // JavaScript implementation of the krushkal's algorithm.> > function> makeSet(parent,rank,n)> {> >for>(let i=0;i { parent[i]=i; rank[i]=0; } } function findParent(parent,component) { if(parent[component]==component) return component; return parent[component] = findParent(parent,parent[component]); } function unionSet(u, v, parent, rank,n) { //this function unions two set on the basis of rank //as shown below u=findParent(parent,u); v=findParent(parent,v); if(rank[u] { parent[u]=v; } else if(rank[u] { parent[v]=u; } else { parent[v]=u; rank[u]++;//since the rank increases if the ranks of two sets are same } } function kruskalAlgo(n, edge) { //First we sort the edge array in ascending order //so that we can access minimum distances/cost edge.sort((a, b)=>{ return a[2] - b[2]; }) //вбудована функція швидкого сортування постачається разом із stdlib.h //перейдіть на https://www.techcodeview.com Сортування країв займає O(E * logE) часу. Після сортування ми повторюємо всі ребра та застосовуємо алгоритм пошуку-об’єднання. Операції пошуку та об’єднання можуть тривати щонайбільше O(logV). Отже, загальна складність становить O(E * logE + E * logV) часу. Значення E може бути не більше O(V2), тому O(logV) і O(logE) однакові. Таким чином, загальна часова складність становить O(E * logE) або O(E*logV). Допоміжний простір: O(V + E), де V — кількість вершин, а E — кількість ребер у графі. Цю статтю зібрано Аашішем Барнвалом і перевірено командою techcodeview.com.> |