upsidedown

kruskals algo

Apr 17th, 2012
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include<iostream.h>
  2. #include<conio.h>
  3. #include<stdlib.h>
  4. int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
  5.  
  6. int main()
  7. {
  8.     int dup1,dup2;
  9.     cout<<"enter no of vertices:\n";
  10.     cin>>n;
  11.     cout<<"enter no of edges:\n";
  12.     cin>>m;
  13.     cout<<"EDGE Cost:\n";
  14.     for(k=1;k<=m;k++)
  15.     {
  16.         cin>>i>>j>>c;
  17.         cost[i][j]=c;
  18.         cost[j][i]=c;
  19.     }
  20.     for(i=1;i<=n;i++)
  21.         for(j=1;j<=n;j++)
  22.             if(cost[i][j]==0)
  23.                 cost[i][j]=31999;
  24.             visit=0;
  25.             while(visit<n)
  26.             {
  27.                 v=31999;
  28.                 for(i=1;i<=n;i++)
  29.                     for(j=1;j<=n;j++)
  30.                         if(cost[i][j]!=31999 && cost[i][j]<v  && cost[i][j]!=-1 )
  31.                         {
  32.                             int count =0;
  33.                             for(p=1;p<=n;p++)
  34.                             {
  35.                                 if(visited[p]==i || visited[p]==j)
  36.                                     count++;
  37.                             }
  38.                             if(count >= 2)
  39.                             {
  40.                                 for(p=1;p<=n;p++)
  41.                                     if(cost[i][p]!=31999 && p!=j)
  42.                                         dup1=p;
  43.                                     for(p=1;p<=n;p++)
  44.                                         if(cost[j][p]!=31999 && p!=i)
  45.                                             dup2=p;
  46.  
  47.                                     if(cost[dup1][dup2]==-1)
  48.                                         continue;
  49.                             }
  50.                             l=i;
  51.                             k=j;
  52.                             v=cost[i][j];
  53.                         }
  54.                         cout<<"edge from "<<l<<"-->"<<k<<endl;
  55.                         cost[l][k]=-1;
  56.                         cost[k][l]=-1;
  57.                         visit++;
  58.                         int count=0;
  59.                         count1=0;
  60.                         for(i=1;i<=n;i++)
  61.                         {
  62.                             if(visited[i]==l)
  63.                                 count++;
  64.                             if(visited[i]==k)
  65.                                 count1++;
  66.                         }
  67.                         if(count==0)
  68.                             visited[++vst]=l;
  69.                         if(count1==0)
  70.                             visited[++vst]=k;
  71.             }
  72.             return 0;
  73. }
  74. OUTPUT:
  75. enter no of vertices:
  76. 6
  77. enter no of edges:
  78. 10
  79. EDGE Cost:
  80. 1 2 12
  81. 2 4 2
  82. 2 3 1
  83. 3 4 6
  84. 1 5 15
  85. 1 6 17
  86. 2 6 3
  87. 4 5 14
  88. 4 6 10
  89. 5 6 19
  90. edge from 2-->3
  91. edge from 2-->4
  92. edge from 2-->6
  93. edge from 4-->6
  94. edge from 1-->2
  95. edge from 4-->5
  96. Press any key to continue
Advertisement
Add Comment
Please, Sign In to add comment