Please write the complete algorith in c language that can work in Visual Studio
ID: 3817591 • Letter: P
Question
Please write the complete algorith in c language that can work in Visual Studio 2015
Write a C function that prints the minimum spanning tree of a graph. At the end,
print the weight of the spanning tree. A suggested report format is shown in the
following example.
Source Vertex To Vertex Weight
A B 2
A C 4
B D 3
D E 1
Total weight of spanning tree: 10
Your main program will read a graph from DataIn file to an adjacency table
before calling the function, which is given in eLearning system for use.
Explanation / Answer
#include<stdio.h>
#include<limits.h>
#define V 5
int findMinKey(int *key,int mstSet[])
{
int min=INT_MAX,i,min_index;
for(i=0;i<V;i++)
{
if(mstSet[i]==0 && key[i]<min)
{
min=key[i];
min_index=i;
}
}
return min_index;
}
void printMST(int *parent,int graph[V][V])
{
int i,total=0;
for(i=1;i<V;i++)
{
printf("%d - %d : %d ",parent[i],i,graph[i][parent[i]]);
total+=graph[i][parent[i]];
}
printf("total weight of spanning tree :%d",total);
}
void primMST(int graph[V][V])//O(V^2)takes
{
int parent[V],key[V],mstSet[V];
int count,i,u,v;
for(i=0;i<V;i++)
{
parent[i]=-1;
key[i]=INT_MAX;
mstSet[i]=0;
}
key[0]=0;
for(count=0;count<V-1;count++)
{
u=findMinKey(key,mstSet);
mstSet[u]=1;
for(v=0;v<V;v++)
{
if(graph[u][v] && mstSet[v]==0 && graph[u][v]<key[v])
{
parent[v]=u;
key[v]=graph[u][v];
}
}
}
printMST(parent,graph);
}
int main()
{
int graph[V][V]={{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
primMST(graph);
return 0;
}
/*
Time Complexity is O(V^2).
*/