nkb29597

Prim's Algorithm

Oct 22nd, 2019
155
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.78 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <conio.h>
  4. #include<limits.h>
  5. #define V 5
  6.  
  7. int minKey(int key[],int visited [])
  8. {
  9.     int min=INT_MAX;
  10.     int i;
  11.     int min_index=0;
  12.     for(i=0;i<V;i++)
  13.     {
  14.         if(visited[i]==0 && key[i]<min)
  15.         {
  16.             min=key[i];
  17.             min_index=i;
  18.         }
  19.     }
  20.     return min_index;
  21. }
  22.  
  23. void printMST(int parent[],int n,int graph[V][V])
  24. {
  25.     int i;
  26.     printf("Edge\tWeight\n");
  27.     for(i=1;i<n;i++)
  28.     {
  29.         printf("%d - %d\t%d \n",parent[i],i,graph[i][parent[i]]);
  30.     }
  31. }
  32. void prims(int graph[V][V])
  33. {
  34.  
  35.     int parent[V],key[V],visited[V],i,count,v;
  36.     for(i=0;i<V;i++)
  37.     {
  38.  
  39.         key[i]=INT_MAX;
  40.         visited[i]=0;
  41.     }
  42.     key[0]=0;
  43.     parent[0]=-1;
  44.     for(count=0;count<V-1;count++)
  45.     {
  46.         int u=minKey(key,visited);
  47.         visited[u]=1;
  48.         for(v=0;v<V;v++)
  49.         {
  50.             if(graph[u][v] && visited[v]==0 && graph[u][v]<key[v])
  51.             {
  52.                 parent[v]=u;
  53.                 key[v]=graph[u][v];
  54.             }
  55.         }
  56.  
  57.     }
  58.     printMST(parent,V,graph);
  59. }
  60. int main()
  61. {
  62.     /*int graph[9][9]={
  63.                      {0,4,0,0,0,0,0,8,0},
  64.                      {4,0,8,0,0,0,0,11,0},
  65.                      {0,8,0,7,0,4,0,0,2},
  66.                      {0,0,7,0,9,14,0,0,0},
  67.                      {0,0,0,9,0,10,0,0,0},
  68.                      {0,4,14,10,0,2,0,1,6},
  69.                      {0,0,0,0,0,2,0,1,6},
  70.                      {8,11,0,0,0,0,1,0,7},
  71.                      {0,0,2,0,0,0,6,7,0}
  72.                       };*/
  73.  
  74.     int graph[5][5]={{0,1,2,0,0},
  75.                      {1,0,5,4,3},
  76.                      {2,5,0,0,6},
  77.                      {0,4,0,0,2},
  78.                      {0,3,6,2,0}};
  79. //    clrscr();
  80.     prims(graph);
  81.     getch();
  82. }
Advertisement
Add Comment
Please, Sign In to add comment