Computer Science‎ > ‎

### Algorithms: Minimum Spanning Trees in Graphs - The Kruskal Algorithm ( with C Program source code)

Kruskal’s Algorithm

Kruskal’s Algorithm is based on generic minimum spanning tree algorithm. It finds an edge
to add to the growing forest by finding an edge of least weight from all the edges that connect
any two trees in the forest. It is a greedy algorithm, because at each step it adds to the forest an
edge of least possible weight. It is basically used to connect all the nodes in the graph, with least
possible cost. Input graph must be undirected, weighted and connected.

Analysis:
Time complexity is O(E logE). Initialization takes O(V) time. Sorting the edges takes O(E logE)
time and there are O(E) operations on the dis-joint forest set which in total take O(logE) time.

## Graphs - Kruskal Algorithm - C Program source code

`#include<stdio.h>#include<stdlib.h>#include<string.h>#define maxVertices 1000#define maxEdges 1000000int graph[maxVertices][maxVertices];/* Input graph must be undirected,weighted and connected*/typedef struct Edge{        int from,to,weight;}Edge;int compare(const void * x,const void * y){        return (*(Edge *)x).weight - (*(Edge *)y).weight;}Edge E[maxEdges];int parent[maxVertices];void init(int vertices){        int iter=0;        for(iter=0;iter<vertices;iter++)        {                parent[iter]=-1;        }}int Find(int vertex){        if(parent[vertex]==-1)return vertex;        return parent[vertex] = Find(parent[vertex]); /* Finding its parent as well as updating the parent                                                          of all vertices along this path */}int Union(int parent1,int parent2){        /* This can be implemented in many other ways. This is one of them */        parent[parent1] = parent2;}void Kruskal(int vertices,int edges){        memset(graph,-1,sizeof(graph)); /* -1 represents the absence of edge between them */        /* Sort the edges according to the weight */        qsort(E,edges,sizeof(Edge),compare);        /* Initialize parents of all vertices to be -1.*/        init(vertices);        int totalEdges = 0,edgePos=0,from,to,weight;        Edge now;        while(totalEdges < vertices -1)        {                if(edgePos==edges)                {                        /* Input Graph is not connected*/                        exit(0);                }                now = E[edgePos++];                from = now.from;                to = now.to;                weight=now.weight;                /* See If vetices from,to are connected. If they are connected do not add this edge. */                int parent1 = Find(from);                int parent2 = Find(to);                if(parent1!=parent2)                {                        graph[from][to] = weight;                        Union(parent1,parent2);                        totalEdges++;                }        }}int main(){        int vertices,edges;        scanf("%d%d",&vertices,&edges);        int iter,jter;        int from,to,weight;        for(iter=0;iter<edges;iter++)        {                scanf("%d%d%d",&from,&to,&weight);                E[iter].from = from;                 E[iter].to = to;                 E[iter].weight = weight;        }        /* Finding MST */        Kruskal(vertices,edges);        /* Printing the MST */        for(iter=0;iter<vertices;iter++)        {                for(jter=0;jter<vertices;jter++)                {                        if(graph[iter][jter]!=-1)                        {                                printf("Vertex %d and %d, weight %d\n",iter,jter,graph[iter][jter]);                        }                }        }        return 0;}`

Some Important Data Structures and Algorithms, at a glance:

 Arrays : Popular Sorting and Searching Algorithms Bubble Sort Insertion Sort Selection Sort Shell Sort Merge Sort Quick Sort Heap Sort Binary Search Algorithm Basic Data Structures  and Operations on them Stacks Queues Single Linked List Double Linked List Circular Linked List
 Tree Data Structures Binary Search Trees Heaps Height Balanced Trees Graphs and Graph Algorithms Depth First Search Breadth First Search Minimum Spanning Trees: Kruskal Algorithm Minumum Spanning Trees: Prim's Algorithm Dijkstra Algorithm for Shortest Paths Floyd Warshall Algorithm for Shortest Paths Bellman Ford Algorithm Popular Algorithms in Dynamic Programming Dynamic Programming Integer Knapsack problem Matrix Chain Multiplication Longest Common Subsequence Greedy Algorithms Elementary cases : Fractional Knapsack Problem, Task Scheduling Data Compression using Huffman Trees