Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <conio.h>
- #include<limits.h>
- #define V 5
- int minKey(int key[],int visited [])
- {
- int min=INT_MAX;
- int i;
- int min_index=0;
- for(i=0;i<V;i++)
- {
- if(visited[i]==0 && key[i]<min)
- {
- min=key[i];
- min_index=i;
- }
- }
- return min_index;
- }
- void printMST(int parent[],int n,int graph[V][V])
- {
- int i;
- printf("Edge\tWeight\n");
- for(i=1;i<n;i++)
- {
- printf("%d - %d\t%d \n",parent[i],i,graph[i][parent[i]]);
- }
- }
- void prims(int graph[V][V])
- {
- int parent[V],key[V],visited[V],i,count,v;
- for(i=0;i<V;i++)
- {
- key[i]=INT_MAX;
- visited[i]=0;
- }
- key[0]=0;
- parent[0]=-1;
- for(count=0;count<V-1;count++)
- {
- int u=minKey(key,visited);
- visited[u]=1;
- for(v=0;v<V;v++)
- {
- if(graph[u][v] && visited[v]==0 && graph[u][v]<key[v])
- {
- parent[v]=u;
- key[v]=graph[u][v];
- }
- }
- }
- printMST(parent,V,graph);
- }
- int main()
- {
- /*int graph[9][9]={
- {0,4,0,0,0,0,0,8,0},
- {4,0,8,0,0,0,0,11,0},
- {0,8,0,7,0,4,0,0,2},
- {0,0,7,0,9,14,0,0,0},
- {0,0,0,9,0,10,0,0,0},
- {0,4,14,10,0,2,0,1,6},
- {0,0,0,0,0,2,0,1,6},
- {8,11,0,0,0,0,1,0,7},
- {0,0,2,0,0,0,6,7,0}
- };*/
- int graph[5][5]={{0,1,2,0,0},
- {1,0,5,4,3},
- {2,5,0,0,6},
- {0,4,0,0,2},
- {0,3,6,2,0}};
- // clrscr();
- prims(graph);
- getch();
- }
Advertisement
Add Comment
Please, Sign In to add comment