Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream.h>
- #include<conio.h>
- #include<stdlib.h>
- int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;
- int main()
- {
- int dup1,dup2;
- cout<<"enter no of vertices:\n";
- cin>>n;
- cout<<"enter no of edges:\n";
- cin>>m;
- cout<<"EDGE Cost:\n";
- for(k=1;k<=m;k++)
- {
- cin>>i>>j>>c;
- cost[i][j]=c;
- cost[j][i]=c;
- }
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- if(cost[i][j]==0)
- cost[i][j]=31999;
- visit=0;
- while(visit<n)
- {
- v=31999;
- for(i=1;i<=n;i++)
- for(j=1;j<=n;j++)
- if(cost[i][j]!=31999 && cost[i][j]<v && cost[i][j]!=-1 )
- {
- int count =0;
- for(p=1;p<=n;p++)
- {
- if(visited[p]==i || visited[p]==j)
- count++;
- }
- if(count >= 2)
- {
- for(p=1;p<=n;p++)
- if(cost[i][p]!=31999 && p!=j)
- dup1=p;
- for(p=1;p<=n;p++)
- if(cost[j][p]!=31999 && p!=i)
- dup2=p;
- if(cost[dup1][dup2]==-1)
- continue;
- }
- l=i;
- k=j;
- v=cost[i][j];
- }
- cout<<"edge from "<<l<<"-->"<<k<<endl;
- cost[l][k]=-1;
- cost[k][l]=-1;
- visit++;
- int count=0;
- count1=0;
- for(i=1;i<=n;i++)
- {
- if(visited[i]==l)
- count++;
- if(visited[i]==k)
- count1++;
- }
- if(count==0)
- visited[++vst]=l;
- if(count1==0)
- visited[++vst]=k;
- }
- return 0;
- }
- OUTPUT:
- enter no of vertices:
- 6
- enter no of edges:
- 10
- EDGE Cost:
- 1 2 12
- 2 4 2
- 2 3 1
- 3 4 6
- 1 5 15
- 1 6 17
- 2 6 3
- 4 5 14
- 4 6 10
- 5 6 19
- edge from 2-->3
- edge from 2-->4
- edge from 2-->6
- edge from 4-->6
- edge from 1-->2
- edge from 4-->5
- Press any key to continue
Advertisement
Add Comment
Please, Sign In to add comment