Question

[INPUT] First line number of vertex v adjacency matrix of graph Second v+1 line (If not connected, 1 If connected, weight on the edge) [OUTPUT First line For completed MST Second line Completed MST cost as a result of running dfs(0) [EXAMPLE] input,txt 7 -1 28 -1 -1 -1 10 -1 28 -1 16 -1 -1 -1 14 -1 16 -1 12 -1 -1 -1 -1 -1 12 -1 22 -1 18 -1 -1 -1 22 -1 25 24 10 -1 -1-1 25 -1 -1 -1 14 -1 18 24 -1 -1 output.txt 0 5 4 3 21 6 99 Write a C code that finds a minimum cost spnning tree using Kruskal's algorithm You can use the union and find function and the sort function or the min heap function [Condition] Be sure to write in C adjacency list Express the graph as an Use file input/output Assume that the number of vertex starts at zero

Answer 1

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

#define MAX 100

struct edge                           //TO STORE EDGE AND WEIGHT OF GRAPH
{
int x;
int y;
   int weight;
   struct edge *link;
}*front = NULL;

int Print(int a,int Arr[],int k);
void create_tree(int V,struct edge tree[]);
void insert_queue(int i, int j, int wt);
struct edge *delete_queue();
int isEmpty();

int main()
{
   int V;
int i=0,j=0;
scanf("%d",&V);                  
int A[V][V];                   //Array for storing the values of all edges
  
   for(i=0;i<V;i++)
       for(j=0;j<V;j++)
       {
           scanf("%d",&A[i][j]);
           if( A[i][j]!=-1 && i<j )         //Inserting edges
           insert_queue(i,j,A[i][j]);
   }
  
struct edge tree[MAX];
int tree_weight = 0;
   create_tree(V,tree);                   //creating tree
  
int k=0,Arr[V],a,b;
   for(i=1; i<=V-1; i++)                   //storing all vertices in spanning tree
{                                       //also calculating total cost
a=tree[i].x;
k=Print(a,Arr,k);
       b=tree[i].y;
   k=Print(b,Arr,k);
tree_weight = tree_weight + tree[i].weight;
   }
  
for(i=0;i<k;i++)                       //printing the edges in spanning tree
   printf("%d ",Arr[i]);
printf("\n%d\n", tree_weight);       //printing total cost or weight
return 0;
}

void create_tree(int V,struct edge tree[])           //function for creating tree
{
struct edge *tmp;
int y1, y2, root_y1, root_y2;
int parent[MAX];
int i, count = 0;
for(i = 0; i < V; i++)
{
parent[i] = -1;
}
while(!isEmpty( ) && count < V - 1)
{
tmp = delete_queue();
y1 = tmp->x;
y2 = tmp->y;
while(y1 != -1)
{
root_y1 = y1;
y1 = parent[y1];
}
while(y2 != -1)
{
root_y2 = y2;
y2 = parent[y2];
}
if(root_y1 != root_y2)
{
count++;
tree[count].x = tmp->x;
tree[count].y = tmp->y;
tree[count].weight = tmp->weight;
parent[root_y2] = root_y1;
}
}
}

void insert_queue(int i, int j, int wt)               //function for storing edges and weight
{
struct edge *tmp, *q;
tmp = (struct edge *)malloc(sizeof(struct edge));
tmp->x = i;
tmp->y = j;
tmp->weight = wt;
if(front == NULL || tmp->weight < front->weight)
{
tmp->link = front;
front = tmp;
}
else
{
q = front;
while(q->link != NULL && q->link->weight <= tmp->weight)
{
q = q->link;
}
tmp->link = q->link;
q->link = tmp;
if(q->link == NULL)
{
tmp->link = NULL;
}
}
}

int Print(int a,int Arr[],int k)                   //function for storing vertices of spanning tree
{
   int i=0,j=0;
   for(i=0;i<k;i++)
   {
       if(Arr[i]==a)
           return k;
   }
   Arr[k++]=a;
   return k;
}

struct edge *delete_queue()                               //function for delete node
{
struct edge *tmp;
tmp = front;
front = front->link;
return tmp;
}

int isEmpty()                                           //function to check the list
{
if(front == NULL)
return 1;
else
return 0;
}

THE INPUT OUTPUT EXAMPLE IS AS FOLLOWS:-

7 -1 28 -1 -1 -1 10 -1 28 -1 16 -1 -1 -1 14 -1 16 -1 12-1 -1 -1 -1 -1 12 -1 22 -1 18 -1 -1 -1 22 -1 25 24 10 -1-1 -1 25 -1 -1 -1 14 -1 18 24 -1 -1 0 5 2 3 1 6 4 99