# define INFINITY 0
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n,y=-1,k,flag;
struct group
{
int cost,e1,e2;
}ob[12];
int main()
{
int i,j,m,b,c=0,sum=0;
cout<<"\nEnter the number of nodes:";
cin>>n;
fflush(stdin);
char name[n];
int adj[n][n],test[n],path[n][n],path_copy[n][n];
for(i=0;i<n;i++)
{
cout<<"\n\a\aEnter the name on node:";
cin>>name[i];
for(j=0;j<n;j++)
{
fflush(stdin);
cout<<"\n\nEnter cost at position ("<<i+1<<","<<j+1<<") : ";
cin>>adj[i][j];
path[i][j]=0;
path_copy[i][j]=0;
if(j>i && adj[i][j]!=INFINITY)
{
ob[++y].cost=adj[i][j];
ob[y].e1=i;
ob[y].e2=j;
}
}
}
system("cls");
cout<<"\nThe adjacency matrix::\n\n";
cout<<" ";
for(i=0;i<n;i++)
{
cout<<" ";
cout<<name[i];
}
cout<<endl;
for(i=0;i<n;i++)
{
cout<<name[i]<<" ";
for(j=0;j<n;j++)
{
cout<<adj[i][j];
cout<<" ";
}
cout<<endl;
}
system("pause");
system("cls");
//Sort(Selection)
for(i=0;i<=y;i++)
{
k=0;
for(j=1;j<=y-i;j++)
{
if((ob[j].cost)>(ob[k].cost))
k=j;
}
swap(ob[k],ob[j-1]);
}
cout<<"\nCost Edge\n\n";
for(i=0;i<=y;i++)
{
m=0;b=0,flag=1;
for(j=0;j<i;j++)
{
if(ob[i].e1==ob[j].e1 || ob[i].e1==ob[j].e2)
{m++;}
if(ob[i].e2==ob[j].e1 || ob[i].e2==ob[j].e2)
{b++;}
}
if(m>0 && b>0 && c<n-1)
{
//Warshall
int f,g,k;
for(k=0;k<n;k++)
{
for(f=0;f<n;f++)
{
for(g=0;g<n;g++)
{
if(path[f][k]*path[k][g]==1)
path[f][g]=1;
}
}
}
if(path[ob[i].e1][ob[i].e2]==1)
flag=0;
else
{
path_copy[ob[i].e1][ob[i].e2]=1;
path_copy[ob[i].e2][ob[i].e1]=1;
//For restoring path matrix
for(int u=0;u<n;u++)
{
for(int v=0;v<n;v++)
path[u][v]=path_copy[u][v];
}
}
}
else
{
path[ob[i].e1][ob[i].e2]=1;
path[ob[i].e2][ob[i].e1]=1;
path_copy[ob[i].e1][ob[i].e2]=1;
path_copy[ob[i].e2][ob[i].e1]=1;
}
if(flag==1 && c<n-1)
{
cout<<ob[i].cost<<" "<<"("<<name[ob[i].e1]<<","<<name[ob[i].e2]<<")"<<endl<<endl;
c++;
sum+=ob[i].cost;
}
}
cout<<"----\n"<<sum<<endl<<endl;
return 0;
}
#include<iostream>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
int n,y=-1,k,flag;
struct group
{
int cost,e1,e2;
}ob[12];
int main()
{
int i,j,m,b,c=0,sum=0;
cout<<"\nEnter the number of nodes:";
cin>>n;
fflush(stdin);
char name[n];
int adj[n][n],test[n],path[n][n],path_copy[n][n];
for(i=0;i<n;i++)
{
cout<<"\n\a\aEnter the name on node:";
cin>>name[i];
for(j=0;j<n;j++)
{
fflush(stdin);
cout<<"\n\nEnter cost at position ("<<i+1<<","<<j+1<<") : ";
cin>>adj[i][j];
path[i][j]=0;
path_copy[i][j]=0;
if(j>i && adj[i][j]!=INFINITY)
{
ob[++y].cost=adj[i][j];
ob[y].e1=i;
ob[y].e2=j;
}
}
}
system("cls");
cout<<"\nThe adjacency matrix::\n\n";
cout<<" ";
for(i=0;i<n;i++)
{
cout<<" ";
cout<<name[i];
}
cout<<endl;
for(i=0;i<n;i++)
{
cout<<name[i]<<" ";
for(j=0;j<n;j++)
{
cout<<adj[i][j];
cout<<" ";
}
cout<<endl;
}
system("pause");
system("cls");
//Sort(Selection)
for(i=0;i<=y;i++)
{
k=0;
for(j=1;j<=y-i;j++)
{
if((ob[j].cost)>(ob[k].cost))
k=j;
}
swap(ob[k],ob[j-1]);
}
cout<<"\nCost Edge\n\n";
for(i=0;i<=y;i++)
{
m=0;b=0,flag=1;
for(j=0;j<i;j++)
{
if(ob[i].e1==ob[j].e1 || ob[i].e1==ob[j].e2)
{m++;}
if(ob[i].e2==ob[j].e1 || ob[i].e2==ob[j].e2)
{b++;}
}
if(m>0 && b>0 && c<n-1)
{
//Warshall
int f,g,k;
for(k=0;k<n;k++)
{
for(f=0;f<n;f++)
{
for(g=0;g<n;g++)
{
if(path[f][k]*path[k][g]==1)
path[f][g]=1;
}
}
}
if(path[ob[i].e1][ob[i].e2]==1)
flag=0;
else
{
path_copy[ob[i].e1][ob[i].e2]=1;
path_copy[ob[i].e2][ob[i].e1]=1;
//For restoring path matrix
for(int u=0;u<n;u++)
{
for(int v=0;v<n;v++)
path[u][v]=path_copy[u][v];
}
}
}
else
{
path[ob[i].e1][ob[i].e2]=1;
path[ob[i].e2][ob[i].e1]=1;
path_copy[ob[i].e1][ob[i].e2]=1;
path_copy[ob[i].e2][ob[i].e1]=1;
}
if(flag==1 && c<n-1)
{
cout<<ob[i].cost<<" "<<"("<<name[ob[i].e1]<<","<<name[ob[i].e2]<<")"<<endl<<endl;
c++;
sum+=ob[i].cost;
}
}
cout<<"----\n"<<sum<<endl<<endl;
return 0;
}
No comments:
Post a Comment