Kruskal的最小生成树算法|贪婪算法2

2021年4月10日11:46:08 发表评论 869 次浏览

本文概述

什么是最小生成树?

给定一个连通无向图,该图的生成树是一个子图,该子图是一棵连接所有顶点的树。一个图可以有许多不同的生成树。加权连通无向图的最小生成树(MST)或最小权生成树是权值小于或等于其他每棵生成树的权值的一棵生成树。一棵生成树的权值是它的每条边的权值之和。

一个最小生成树有多少条边?

最小生成树具有(V – 1)个边, 其中V是给定图中的顶点数。

最小生成树有哪些应用?

请参阅本文了解MST的应用。

以下是使用Kruskal算法查找MST的步骤

1.按重量的递减顺序对所有边进行排序。
2.选择最小的边。检查它是否与形成的生成树形成一个循环。如果未形成循环, 则包括该边。否则, 将其丢弃。
3.重复步骤2, 直到生成树中有(V-1)个边。

步骤2使用并集查找算法检测周期。因此,我们建议阅读以下文章作为先决条件。

联合查找算法|S1(图形中的检测周期)

联合查找算法|S2(按等级和路径压缩合并)

该算法是贪婪算法。贪婪的选择是选择迄今为止不会造成MST循环的最小重量边。让我们以一个示例来理解它:考虑以下输入图。

Kruskal的最小生成树算法|贪婪算法21

该图包含9个顶点和14个边。因此, 形成的最小生成树将具有(9 – 1)= 8个边。

After sorting:

Weight   Src    Dest
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
11        1      7
14        3      5

现在从边排序列表中一一挑选所有边

1.挑边7-6:没有形成循环,包括它。

Kruskal的最小生成树算法|贪婪算法22

2.挑边8-2:没有形成循环,包括它。

Kruskal的最小生成树算法|贪婪算法23

3.挑边6-5:没有形成循环,包括它。

Kruskal的最小生成树算法|贪婪算法24

4.挑边0-1:没有形成循环,包括它。

Kruskal的最小生成树算法|贪婪算法25

5.挑边2-5:没有形成循环,包括它。

Kruskal的最小生成树算法|贪婪算法26

6.选择边8-6:因为包含这条边会导致循环,丢弃它。

7.挑边2-3:没有形成循环,包括它。

Kruskal的最小生成树算法|贪婪算法27

8.选择边7-8:因为包含这条边会导致循环,丢弃它。

9.选择边0-7:没有周期形成, 包括它。

Kruskal的最小生成树算法|贪婪算法28

10.挑边1-2:由于包含此边沿会导致循环, 因此将其丢弃。

11.选边3-4:没有周期形成, 包括它。

Kruskal的最小生成树算法|贪婪算法29

由于包含的边数等于(V – 1), 因此算法在此处停止。

以下是上述想法的实现:

C++

//C++ program for Kruskal's algorithm
// to find Minimum Spanning Tree of a
// given connected, undirected and weighted
// graph
#include <bits/stdc++.h>
using namespace std;
 
//a structure to represent a
//weighted edge in graph
class Edge {
public :
     int src, dest, weight;
};
 
//a structure to represent a connected, //undirected and weighted graph
class Graph {
public :
     
     //V-> Number of vertices, E-> Number of edges
     int V, E;
 
     //graph is represented as an array of edges.
     //Since the graph is undirected, the edge
     //from src to dest is also edge from dest
     //to src. Both are counted as 1 edge here.
     Edge* edge;
};
 
//Creates a graph with V vertices and E edges
Graph* createGraph( int V, int E)
{
     Graph* graph = new Graph;
     graph->V = V;
     graph->E = E;
 
     graph->edge = new Edge[E];
 
     return graph;
}
 
//A structure to represent a subset for union-find
class subset {
public :
     int parent;
     int rank;
};
 
//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[yroot].rank)
         subsets[xroot].parent = yroot;
     else if (subsets[xroot].rank> subsets[yroot].rank)
         subsets[yroot].parent = xroot;
 
     //If ranks are same, then make one as root and
     //increment its rank by one
     else {
         subsets[yroot].parent = xroot;
         subsets[xroot].rank++;
     }
}
 
//Compare two edges according to their weights.
//Used in qsort() for sorting an array of edges
int myComp( const void * a, const void * b)
{
     Edge* a1 = (Edge*)a;
     Edge* b1 = (Edge*)b;
     return a1->weight> b1->weight;
}
 
//The main function to construct MST using Kruskal's
//algorithm
void KruskalMST(Graph* graph)
{
     int V = graph->V;
     Edge result[V]; //Tnis will store the resultant MST
     int e = 0; //An index variable, used for result[]
     int i = 0; //An index variable, used for sorted edges
 
     //Step 1: Sort all the edges in non-decreasing
     //order of their weight. If we are not allowed to
     //change the given graph, we can create a copy of
     //array of edges
     qsort (graph->edge, graph->E, sizeof (graph->edge[0]), myComp);
 
     //Allocate memory for creating V ssubsets
     subset* subsets = new subset[(V * sizeof (subset))];
 
     //Create V subsets with single elements
     for ( int v = 0; v <V; ++v)
     {
         subsets[v].parent = v;
         subsets[v].rank = 0;
     }
 
     //Number of edges to be taken is equal to V-1
     while (e <V - 1 && i <graph->E)
     {
         //Step 2: Pick the smallest edge. And increment
         //the index for next iteration
         Edge next_edge = graph->edge[i++];
 
         int x = find(subsets, next_edge.src);
         int y = find(subsets, next_edge.dest);
 
         //If including this edge does't cause cycle, //include it in result and increment the index
         //of result for next edge
         if (x != y) {
             result[e++] = next_edge;
             Union(subsets, x, y);
         }
         //Else discard the next_edge
     }
 
     //print the contents of result[] to display the
     //built MST
     cout <<"Following are the edges in the constructed "
             "MST\n" ;
     int minimumCost = 0;
     for (i = 0; i <e; ++i)
     {
         cout <<result[i].src <<" -- " <<result[i].dest
              <<" == " <<result[i].weight <<endl;
         minimumCost = minimumCost + result[i].weight;
     }
     //return;
     cout <<"Minimum Cost Spanning Tree: " <<minimumCost
          <<endl;
}
 
//Driver code
int main()
{
     /* Let us create following weighted graph
             10
         0--------1
         | \ |
     6| 5\ |15
         | \ |
         2--------3
             4 */
     int V = 4; //Number of vertices in graph
     int E = 5; //Number of edges in graph
     Graph* graph = createGraph(V, E);
 
     //add edge 0-1
     graph->edge[0].src = 0;
     graph->edge[0].dest = 1;
     graph->edge[0].weight = 10;
 
     //add edge 0-2
     graph->edge[1].src = 0;
     graph->edge[1].dest = 2;
     graph->edge[1].weight = 6;
 
     //add edge 0-3
     graph->edge[2].src = 0;
     graph->edge[2].dest = 3;
     graph->edge[2].weight = 5;
 
     //add edge 1-3
     graph->edge[3].src = 1;
     graph->edge[3].dest = 3;
     graph->edge[3].weight = 15;
 
     //add edge 2-3
     graph->edge[4].src = 2;
     graph->edge[4].dest = 3;
     graph->edge[4].weight = 4;
 
   
     //Function call
     KruskalMST(graph);
 
     return 0;
}
 
//This code is contributed by rathbhupendra

C

//C program for Kruskal's algorithm to find Minimum
//Spanning Tree of a given connected, undirected and
//weighted graph
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
//a structure to represent a weighted edge in graph
struct Edge {
     int src, dest, weight;
};
 
//a structure to represent a connected, undirected
//and weighted graph
struct Graph {
     //V-> Number of vertices, E-> Number of edges
     int V, E;
 
     //graph is represented as an array of edges.
     //Since the graph is undirected, the edge
     //from src to dest is also edge from dest
     //to src. Both are counted as 1 edge here.
     struct Edge* edge;
};
 
//Creates a graph with V vertices and E edges
struct Graph* createGraph( int V, int E)
{
     struct Graph* graph = new Graph;
     graph->V = V;
     graph->E = E;
 
     graph->edge = new Edge[E];
 
     return graph;
}
 
//A structure to represent a subset for union-find
struct subset {
     int parent;
     int rank;
};
 
//A utility function to find set of an element i
//(uses path compression technique)
int find( struct 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( struct 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[yroot].rank)
         subsets[xroot].parent = yroot;
     else if (subsets[xroot].rank> subsets[yroot].rank)
         subsets[yroot].parent = xroot;
 
     //If ranks are same, then make one as root and
     //increment its rank by one
     else
     {
         subsets[yroot].parent = xroot;
         subsets[xroot].rank++;
     }
}
 
//Compare two edges according to their weights.
//Used in qsort() for sorting an array of edges
int myComp( const void * a, const void * b)
{
     struct Edge* a1 = ( struct Edge*)a;
     struct Edge* b1 = ( struct Edge*)b;
     return a1->weight> b1->weight;
}
 
//The main function to construct MST using Kruskal's
//algorithm
void KruskalMST( struct Graph* graph)
{
     int V = graph->V;
     struct Edge
         result[V]; //Tnis will store the resultant MST
     int e = 0; //An index variable, used for result[]
     int i = 0; //An index variable, used for sorted edges
 
     //Step 1:  Sort all the edges in non-decreasing
     //order of their weight. If we are not allowed to
     //change the given graph, we can create a copy of
     //array of edges
     qsort (graph->edge, graph->E, sizeof (graph->edge[0]), myComp);
 
     //Allocate memory for creating V ssubsets
     struct subset* subsets
         = ( struct subset*) malloc (V * sizeof ( struct subset));
 
     //Create V subsets with single elements
     for ( int v = 0; v <V; ++v) {
         subsets[v].parent = v;
         subsets[v].rank = 0;
     }
 
     //Number of edges to be taken is equal to V-1
     while (e <V - 1 && i <graph->E) {
         //Step 2: Pick the smallest edge. And increment
         //the index for next iteration
         struct Edge next_edge = graph->edge[i++];
 
         int x = find(subsets, next_edge.src);
         int y = find(subsets, next_edge.dest);
 
         //If including this edge does't cause cycle, //include it in result and increment the index
         //of result for next edge
         if (x != y) {
             result[e++] = next_edge;
             Union(subsets, x, y);
         }
         //Else discard the next_edge
     }
 
     //print the contents of result[] to display the
     //built MST
     printf (
         "Following are the edges in the constructed MST\n" );
     int minimumCost = 0;
     for (i = 0; i <e; ++i)
     {
         printf ( "%d -- %d == %d\n" , result[i].src, result[i].dest, result[i].weight);
         minimumCost += result[i].weight;
     }
     printf ( "Minimum Cost Spanning tree : %d" , minimumCost);
     return ;
}
 
//Driver program to test above functions
int main()
{
     /* Let us create following weighted graph
              10
         0--------1
         |  \     |
        6|   5\   |15
         |      \ |
         2--------3
             4       */
     int V = 4; //Number of vertices in graph
     int E = 5; //Number of edges in graph
     struct Graph* graph = createGraph(V, E);
 
     //add edge 0-1
     graph->edge[0].src = 0;
     graph->edge[0].dest = 1;
     graph->edge[0].weight = 10;
 
     //add edge 0-2
     graph->edge[1].src = 0;
     graph->edge[1].dest = 2;
     graph->edge[1].weight = 6;
 
     //add edge 0-3
     graph->edge[2].src = 0;
     graph->edge[2].dest = 3;
     graph->edge[2].weight = 5;
 
     //add edge 1-3
     graph->edge[3].src = 1;
     graph->edge[3].dest = 3;
     graph->edge[3].weight = 15;
 
     //add edge 2-3
     graph->edge[4].src = 2;
     graph->edge[4].dest = 3;
     graph->edge[4].weight = 4;
 
     KruskalMST(graph);
 
     return 0;
}

Java

//Java program for Kruskal's algorithm to
//find Minimum Spanning Tree of a given
//connected, undirected and  weighted graph
import java.util.*;
import java.lang.*;
import java.io.*;
 
class Graph {
     //A class to represent a graph edge
     class Edge implements Comparable<Edge>
     {
         int src, dest, weight;
 
         //Comparator function used for
         //sorting edgesbased on their weight
         public int compareTo(Edge compareEdge)
         {
             return this .weight - compareEdge.weight;
         }
     };
 
     //A class to represent a subset for
     //union-find
     class subset
     {
         int parent, rank;
     };
 
     int V, E; //V-> no. of vertices & E->no.of edges
     Edge edge[]; //collection of all edges
 
     //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 <e; ++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[yroot].rank)
             subsets[xroot].parent = yroot;
         else if (subsets[xroot].rank
                 > subsets[yroot].rank)
             subsets[yroot].parent = xroot;
 
         //If ranks are same, then make one as
         //root and increment its rank by one
         else {
             subsets[yroot].parent = xroot;
             subsets[xroot].rank++;
         }
     }
 
     //The main function to construct MST using Kruskal's
     //algorithm
     void KruskalMST()
     {
         //Tnis will store the resultant MST
         Edge result[] = new Edge[V];
       
         //An index variable, used for result[]
         int e = 0 ;
       
         //An index variable, used for sorted edges
         int i = 0 ;
         for (i = 0 ; i <V; ++i)
             result[i] = new Edge();
 
         //Step 1:  Sort all the edges in non-decreasing
         //order of their weight.  If we are not allowed to
         //change the given graph, we can create a copy of
         //array of edges
         Arrays.sort(edge);
 
         //Allocate memory for creating V ssubsets
         subset subsets[] = new subset[V];
         for (i = 0 ; i <V; ++i)
             subsets[i] = new subset();
 
         //Create V subsets with single elements
         for ( int v = 0 ; v <V; ++v)
         {
             subsets[v].parent = v;
             subsets[v].rank = 0 ;
         }
 
         i = 0 ; //Index used to pick next edge
 
         //Number of edges to be taken is equal to V-1
         while (e <V - 1 )
         {
             //Step 2: Pick the smallest edge. And increment
             //the index for next iteration
             Edge next_edge = new Edge();
             next_edge = edge[i++];
 
             int x = find(subsets, next_edge.src);
             int y = find(subsets, next_edge.dest);
 
             //If including this edge does't cause cycle, //include it in result and increment the index
             //of result for next edge
             if (x != y) {
                 result[e++] = next_edge;
                 Union(subsets, x, y);
             }
             //Else discard the next_edge
         }
 
         //print the contents of result[] to display
         //the built MST
         System.out.println( "Following are the edges in "
                            + "the constructed MST" );
         int minimumCost = 0 ;
         for (i = 0 ; i <e; ++i)
         {
             System.out.println(result[i].src + " -- "
                                + result[i].dest
                                + " == " + result[i].weight);
             minimumCost += result[i].weight;
         }
         System.out.println( "Minimum Cost Spanning Tree "
                            + minimumCost);
     }
 
     //Driver Code
     public static void main(String[] args)
     {
 
         /* Let us create following weighted graph
                  10
             0--------1
             |  \     |
            6|   5\   |15
             |      \ |
             2--------3
                 4       */
         int V = 4 ; //Number of vertices in graph
         int E = 5 ; //Number of edges in graph
         Graph graph = new Graph(V, E);
 
         //add edge 0-1
         graph.edge[ 0 ].src = 0 ;
         graph.edge[ 0 ].dest = 1 ;
         graph.edge[ 0 ].weight = 10 ;
 
         //add edge 0-2
         graph.edge[ 1 ].src = 0 ;
         graph.edge[ 1 ].dest = 2 ;
         graph.edge[ 1 ].weight = 6 ;
 
         //add edge 0-3
         graph.edge[ 2 ].src = 0 ;
         graph.edge[ 2 ].dest = 3 ;
         graph.edge[ 2 ].weight = 5 ;
 
         //add edge 1-3
         graph.edge[ 3 ].src = 1 ;
         graph.edge[ 3 ].dest = 3 ;
         graph.edge[ 3 ].weight = 15 ;
 
         //add edge 2-3
         graph.edge[ 4 ].src = 2 ;
         graph.edge[ 4 ].dest = 3 ;
         graph.edge[ 4 ].weight = 4 ;
 
         //Function call
         graph.KruskalMST();
     }
}
//This code is contributed by Aakash Hasija

python

# Python program for Kruskal's algorithm to find
# Minimum Spanning Tree of a given connected, # undirected and weighted graph
 
from collections import defaultdict
 
# Class to represent a graph
 
 
class Graph:
 
     def __init__( self , vertices):
         self .V = vertices  # No. of vertices
         self .graph = []  # default dictionary
         # to store 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
     # (uses path compression technique)
     def find( self , parent, i):
         if parent[i] = = i:
             return i
         return self .find(parent, 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):
         xroot = self .find(parent, x)
         yroot = self .find(parent, y)
 
         # Attach smaller rank tree under root of
         # high rank tree (Union by Rank)
         if rank[xroot] <rank[yroot]:
             parent[xroot] = yroot
         elif rank[xroot]> rank[yroot]:
             parent[yroot] = xroot
 
         # If ranks are same, then make one as root
         # and increment its rank by one
         else :
             parent[yroot] = xroot
             rank[xroot] + = 1
 
     # The main function to construct MST using Kruskal's
         # algorithm
     def KruskalMST( self ):
 
         result = []  # This will store the resultant MST
         
         # An index variable, used for sorted edges
         i = 0
         
         # An index variable, used for result[]
         e = 0
 
         # Step 1:  Sort all the edges in
         # non-decreasing order of their
         # weight.  If we are not allowed to change the
         # given graph, we can create a copy of graph
         self .graph = sorted ( self .graph, key = lambda item: item[ 2 ])
 
         parent = []
         rank = []
 
         # Create V subsets with single elements
         for node in range ( self .V):
             parent.append(node)
             rank.append( 0 )
 
         # Number of edges to be taken is equal to V-1
         while e <self .V - 1 :
 
             # Step 2: Pick the smallest edge and increment
             # the index for next iteration
             u, v, w = self .graph[i]
             i = i + 1
             x = self .find(parent, u)
             y = self .find(parent, v)
 
             # If including this edge does't
             #  cause cycle, include it in result
             #  and increment the indexof result
             # for next edge
             if x ! = y:
                 e = e + 1
                 result.append([u, v, w])
                 self .union(parent, rank, x, y)
             # Else discard the edge
 
         minimumCost = 0
         print "Edges in the constructed MST"
         for u, v, weight in result:
             minimumCost + = weight
             print ( "%d -- %d == %d" % (u, v, weight))
         print ( "Minimum Spanning Tree" , minimumCost)
 
# Driver code
g = Graph( 4 )
g.addEdge( 0 , 1 , 10 )
g.addEdge( 0 , 2 , 6 )
g.addEdge( 0 , 3 , 5 )
g.addEdge( 1 , 3 , 15 )
g.addEdge( 2 , 3 , 4 )
 
# Function call
g.KruskalMST()
 
# This code is contributed by Neelam Yadav

C#

//C# Code for above approach
using System;
 
class Graph {
 
     //A class to represent a graph edge
     class Edge : IComparable<Edge> {
         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;
     };
 
     int V, E; //V-> no. of vertices & E->no.of edges
     Edge[] edge; //collection of all edges
 
     //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 <e; ++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[yroot].rank)
             subsets[xroot].parent = yroot;
         else if (subsets[xroot].rank> subsets[yroot].rank)
             subsets[yroot].parent = xroot;
 
         //If ranks are same, then make one as root
         //and increment its rank by one
         else {
             subsets[yroot].parent = xroot;
             subsets[xroot].rank++;
         }
     }
 
     //The main function to construct MST
     //using Kruskal's algorithm
     void KruskalMST()
     {
         //This will store the
         //resultant MST
         Edge[] result = new Edge[V];
         int e = 0; //An index variable, used for result[]
         int i
             = 0; //An index variable, used for sorted edges
         for (i = 0; i <V; ++i)
             result[i] = new Edge();
 
         //Step 1: Sort all the edges in non-decreasing
         //order of their weight. If we are not allowed
         //to change the given graph, we can create
         //a copy of array of edges
         Array.Sort(edge);
 
         //Allocate memory for creating V ssubsets
         subset[] subsets = new subset[V];
         for (i = 0; i <V; ++i)
             subsets[i] = new subset();
 
         //Create V subsets with single elements
         for ( int v = 0; v <V; ++v) {
             subsets[v].parent = v;
             subsets[v].rank = 0;
         }
 
         i = 0; //Index used to pick next edge
 
         //Number of edges to be taken is equal to V-1
         while (e <V - 1)
         {
             //Step 2: Pick the smallest edge. And increment
             //the index for next iteration
             Edge next_edge = new Edge();
             next_edge = edge[i++];
 
             int x = find(subsets, next_edge.src);
             int y = find(subsets, next_edge.dest);
 
             //If including this edge does't cause cycle, //include it in result and increment the index
             //of result for next edge
             if (x != y) {
                 result[e++] = next_edge;
                 Union(subsets, x, y);
             }
             //Else discard the next_edge
         }
 
         //print the contents of result[] to display
         //the built MST
         Console.WriteLine( "Following are the edges in "
                           + "the constructed MST" );
       
         int minimumCost = 0
         for (i = 0; i <e; ++i)
         {
             Console.WriteLine(result[i].src + " -- "
                               + result[i].dest
                               + " == " + result[i].weight);
           minimumCost += result[i].weight;
         }
       
         Console.WriteLine( "Minimum Cost Spanning Tree"
                           + minimumCost);
         Console.ReadLine();
     }
 
     //Driver Code
     public static void Main(String[] args)
     {
 
         /* Let us create following weighted graph
                 10
             0--------1
             | \ |
         6| 5\ |15
             | \ |
             2--------3
                 4 */
         int V = 4; //Number of vertices in graph
         int E = 5; //Number of edges in graph
         Graph graph = new Graph(V, E);
 
         //add edge 0-1
         graph.edge[0].src = 0;
         graph.edge[0].dest = 1;
         graph.edge[0].weight = 10;
 
         //add edge 0-2
         graph.edge[1].src = 0;
         graph.edge[1].dest = 2;
         graph.edge[1].weight = 6;
 
         //add edge 0-3
         graph.edge[2].src = 0;
         graph.edge[2].dest = 3;
         graph.edge[2].weight = 5;
 
         //add edge 1-3
         graph.edge[3].src = 1;
         graph.edge[3].dest = 3;
         graph.edge[3].weight = 15;
 
         //add edge 2-3
         graph.edge[4].src = 2;
         graph.edge[4].dest = 3;
         graph.edge[4].weight = 4;
 
         //Function call
         graph.KruskalMST();
     }
}
 
//This code is contributed by Aakash Hasija

输出如下

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost Spanning Tree: 19

时间复杂度:O(ElogE)或O(ElogV)。边排序需要O(ELogE)时间。排序后, 我们遍历所有边并应用find-union算法。查找和联合操作最多需要O(LogV)时间。因此, 总体复杂度为O(ELogE + ELogV)时间。 E的值最大为O(V2), 因此O(LogV)与O(LogE)相同。因此, 总体时间复杂度为O(ElogE)或O(ElogV)

参考文献:

http://www.ics.uci.edu/~eppstein/161/960206.html

http://en.wikipedia.org/wiki/Minimum_spanning_tree

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: