Answers for "Kruskal's Algorithm for minimum spanning tree"

Kruskal's Algorithm for minimum spanning tree

#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
	int source;
	int destination;
	int weight;
} Edge;

typedef struct Graph
{
	int num_of_vertex;
	int num_of_edge;
	Edge *edge;
} Graph;

typedef struct subset
{
	int parent;
	int rank;
} Subset;



Graph *create_graph (int V, int E)
{
	Graph *new_graph = (Graph *) malloc (sizeof (Graph));
	new_graph -> num_of_vertex = V;
	new_graph -> num_of_edge = E;

	new_graph -> edge = (Edge *) malloc (new_graph -> num_of_edge * sizeof (Edge));
	return new_graph;
}


int find_set (Subset subset[], int i)
{
	if (subset[i]. parent != i)
	{
		subset[i]. parent = find_set (subset, subset[i]. parent);
	}

	return subset[i]. parent;
}


void Union (Subset subset[], int x, int y)
{
	int x_parent = find_set (subset, x);
	int y_parent = find_set (subset, y);

	if (subset [x_parent]. rank < subset [y_parent]. rank)
	{
		subset [x_parent]. parent = y_parent;
		subset [y_parent]. rank += 1;
	}

	else
	{
		subset [y_parent]. parent = x_parent;
		subset [x_parent]. rank += 1;
	}
}


int comparison (const void *a, const void *b)
{
	Edge *a1 = (Edge *) a;
	Edge *b1 = (Edge *) b;
	return a1 -> weight > b1 -> weight;
}


void KruskalMST (Graph *graph)
{
	int V = graph -> num_of_vertex;
	Edge result [V];
	qsort (graph -> edge, graph -> num_of_edge, sizeof (graph -> edge [0]), comparison);

	Subset *subset = (Subset *) malloc (V * sizeof (Subset));
	for (int i = 0; i < V; i++)
	{
		subset [i]. parent = i;
		subset [i]. rank = 0;
	}

	int e = 0;
	int i = 0;
	while (e < V-1)
	{
		Edge temp_edge = graph -> edge[i];
		i++;

		int parent_src = find_set (subset, temp_edge. source);
		int parent_dest = find_set (subset, temp_edge. destination);

		if (parent_src != parent_dest)
		{
			result [e] = temp_edge;
			e++;
			Union (subset, parent_src, parent_dest);
		}
	}

	printf("Following are the edges in the constructed MST\n");
    for (i = 0; i < e; i++)
        printf("%d -- %d == %d\n", result[i]. source, result[i]. destination, result[i]. weight);
}




void main()
{
    int V = 4;
    int E = 5;
    Graph* graph = create_graph(V, E);


    // add edge 0-1
    graph->edge[0].source = 0;
    graph->edge[0].destination = 1;
    graph->edge[0].weight = 10;

    // add edge 0-2
    graph->edge[1].source = 0;
    graph->edge[1].destination = 2;
    graph->edge[1].weight = 6;

    // add edge 0-3
    graph->edge[2].source = 0;
    graph->edge[2].destination = 3;
    graph->edge[2].weight = 5;

    // add edge 1-3
    graph->edge[3].source = 1;
    graph->edge[3].destination = 3;
    graph->edge[3].weight = 15;

    // add edge 2-3
    graph->edge[4].source = 2;
    graph->edge[4].destination = 3;
    graph->edge[4].weight = 4;

    KruskalMST(graph);
}

kruskal's algorithm

#include<bits/stdc++.h>

using namespace std;

int  main()
{
	int n = 9;
	
	int mat[9][9] = {
	{100,4,100,100,100,100,100,8,100},
	{4,100,8,100,100,100,100,100,100},
	{100,8,100,7,100,4,100,100,2},
	{100,100,7,100,9,14,100,100,100},
	{100,100,100,9,100,10,100,100,100},
	{100,100,4,14,10,100,2,100,100},
	{100,100,100,100,100,2,100,1,6},
	{8,100,100,100,100,100,1,100,7},
	{100,100,2,100,100,100,6,7,100}};
	
	int parent[n];
	
	int edges[100][3];
	int count = 0;
	
	for(int i=0;i<n;i++)
		for(int j=i;j<n;j++)
		{
			if(mat[i][j] != 100)
			{
				edges[count][0] = i;
				edges[count][1] = j;
				edges[count++][2] = mat[i][j];	
			}		
		}

	for(int i=0;i<count-1;i++)
		for(int j=0;j<count-i-1;j++)
			if(edges[j][2] > edges[j+1][2])
				{
					int t1=edges[j][0], t2=edges[j][1], t3=edges[j][2];
					
					edges[j][0] = edges[j+1][0];
					edges[j][1] = edges[j+1][1];
					edges[j][2] = edges[j+1][2];
					
					edges[j+1][0] = t1;
					edges[j+1][1] = t2;
					edges[j+1][2] = t3;
				}
				
	int mst[n-1][2];
	int mstVal = 0;
	int l = 0;
	
	cout<<endl;
	
	for(int i=0;i<n;i++)
		parent[i] = -1;
	cout<<endl;
				
	for(int i=0;i<count;i++)
	{
		if((parent[edges[i][0]] == -1 && parent[edges[i][1]] == -1))
		{
			parent[edges[i][0]] = edges[i][0];
			parent[edges[i][1]] = edges[i][0];
			
			mst[l][0] = edges[i][0];
			mst[l++][1] = edges[i][1];
			
			mstVal += edges[i][2];
		}
		
		else if((parent[edges[i][0]] == -1 && parent[edges[i][1]] != -1))
		{
			parent[edges[i][0]] = parent[edges[i][1]];
			
			mst[l][0] = edges[i][1];
			mst[l++][1] = edges[i][0];
			
			mstVal += edges[i][2];
		}
		
		else if((parent[edges[i][0]] != -1 && parent[edges[i][1]] == -1))
		{
			parent[edges[i][1]] = parent[edges[i][0]];
			
			mst[l][0] = edges[i][0];
			mst[l++][1] = edges[i][1];
			
			mstVal += edges[i][2];
		}
		
		else if(parent[edges[i][0]] != -1 && parent[edges[i][1]] != -1 && parent[edges[i][0]] != parent[edges[i][1]])
		{
			int p = parent[edges[i][1]];
			for(int j=0;j<n;j++)
				if(parent[j] == p)
					parent[j] = parent[edges[i][0]];
			
			mst[l][0] = edges[i][0];
			mst[l++][1] = edges[i][1];
			
			mstVal += edges[i][2];
		}
	}
	
	for(int i=0;i<l;i++)
		cout<<mst[i][0]<<" -> "<<mst[i][1]<<endl;
	
	cout<<endl;
	cout<<mstVal<<endl;
		
	return(0);
}