Surfe.be - passive income

Kruskal's Algorithm in Spanning Tree

Minimum Spanning Tree

minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Minimum Spanning Tree

                                  Minimum Spanning Tree

The above image is the example of minimum spanning tree . Let’s see the explanation of minimum spanning tree. See here number of nodes 10 and the number of edges are 21 .We will optimize this following graph so that more than two nodes do not create a circle and at the end, we will get the minimum spanning tree after adding the weight of selected edges. Please note that there is no single circle in the graph above (note the bold line). Just add the weight of the selective edges (bold), we will get our desired results.We can now discuss this spanning tree using the Kruskal's algorithm and will also see how we can find out the exact value from a minimum spanning tree .First we will point out the minimum weighted node such as

kruskal algorithm

                               After optimizing this tree – Now Minimum Spanning Tree

The lowest weight in this graph above is 1 to 3 in the node . That is, the weight of this Edge is one . So we can start our traversing from node 1. From 1 to 4 or 1 to 2, we won't go there but we will go from 1 to 3 . Cause have to follow always the minimum weighted edge. Look at the top graph , they also did it . In this way, every node travels. And see, there is no cycle with one node to another after optimizing. This is the concept of minimum spanning tree .

Kruskal Algorithm

Prim's algorithm or  Kruskal's

One should use Prim's algorithm and when Kruskal's to find the minimum spanning tree? They both have easy logics, same worst cases, and only difference is implementation which might involve a bit different data structures. So what is the deciding factor . Use Prim's algorithm when you have a graph with lots of edgeFor a graph with V vertices E edges, Kruskal's algorithm runs in O(E log V) time and Prim's algorithm can run in O(E + V log V) amortized time, if you use a Fibonacci Heap. Prim's algorithm is significantly faster in the limit when you've got a really dense graph with many more edges than vertices. Kruskal performs better in typical situations (sparse graphs) because it uses simpler data structures.

So keep in mind Kruskal time complexity worst case is O(E log E),this because we need to sort the edges. Prim time complexity worst case is O(E log V) with priority queue or even better, O(E+V log V) with Fibonacci Heap. We should use Kruskal when the graph is sparse, i.e.small number of edges,like E=O(V),when the edges are already sorted or if we can sort them in linear time. We should use Prim when the graph is dense, i.e number of edges is high ,like E=O(V²). Of course we will solve minimum spanning tree problem using prims algorithm when the graph is dense . Prim's is faster than Kruskal's in the case of complex graphs.

What is the difference betweenKruskal's and Prim's algorithm ?

  1. • Prim’s algorithm initializes with a node, whereas Kruskal’s algorithm initiates with an edge.
  2. • Prim’s algorithms span from one node to another while Kruskal’s algorithm select the edges in a way that the position of the edge is not based on the last step.
  3. • In prim’s algorithm, graph must be a connected graph while the Kruskal’s can function on disconnected graphs too.
  4. • Prim’s algorithm has a time complexity of O(V^2), and Kruskal’s time complexity is O(logV).

 

Here i used Kruskal's algorithm to solve minimum spanning tree . See the source code .

Source Code with Kruskal’s Algorithm

If you have clear knowledge about Ricursion, Disjoint Set and Vector  of course you will understand my code. See this code which i used Kruskal's algorithm

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
int fathers[100];

int find(int x){
   if(fathers[x]==x){
        return x;
   }
   find(fathers[x]);
}
int main()
{
    for(int i=0; i<100; i++)
        fathers[i] = i;
    int n,m;
    int a,b,w;
    vector < pair < int , pair < int  ,int > > > edges;
    cin>>n>>m;
    for(int i=0; i<m; i++){
        cin>>a>>b>>w;
        edges.push_back(make_pair(w,make_pair(a,b)));
    }
    cout<<endl;
    int mst_weight=0, mst_edges=0;
    int mst_ni=0;
    sort(edges.begin(),edges.end());
    while(  mst_ni < m  )
    {
        a=edges[mst_ni].second.first;
        b=edges[mst_ni].second.second;
        w=edges[mst_ni].first;
        int x,y;
        x=find(a);
        y=find(b);
        if(x!=y){
            fathers[x]=y;
            mst_weight += w;
            cout<<"connected  " <<a<<" "<<b<<" "<<w<<endl;
        }
        mst_ni++;
    }
    cout<<"Minimum Spanning Tree Weight: "<<mst_weight<<endl<<endl;
    for(int i=1; i<n; i++){
        cout<<fathers[i]<<" ";
    }
    return 0;
}

That’s it. If you like this tutorial please leave a comments and share with your friends. If you find any error of this tutorial , please share this with me.

Leave a comments

LET'S SOCIALITE

Recent Tweets