最小生成树问题

最小生成树普利姆算法：
#include
using namespace std;
const int maxvertexnum=20;
const int maxedgenum=40;
typedef int adjmatrix[maxvertexnum][maxvertexnum];
struct edgenode
{
int frontvex;
int rearvex;
int weight;
};
typedef edgenode adgeset[maxedgenum];
//===============================================
void insitadj(adjmatrix &GA);
void setadj(adjmatrix &GA,int n);
void fun(adjmatrix GA,adgeset >,int n);
void display(adgeset GT,int n);
void insit(adgeset >,int n,adjmatrix GA);
//=============================================
void insit(adgeset>,int n,adjmatrix GA)
{
for(int i=0;i{
GT[i].frontvex=0;
GT[i].rearvex=i+1;
GT[i].weight=GA[0][i+1];
}
}
void insitadj(adjmatrix &GA)
{
for(int i=0;i{
for(int j=0;j{
GA[i][j]=20000;
}
}
}
void setadj(adjmatrix &GA,int n)
{
for(int i=0;i<=n;i++)
{
for(int j=i+1;j{
cout<<"请输入第"<cin>>GA[i][j];
}
}
for(i=0;i<=n;i++)
{
for(int j=i+1;j{
GA[j][i]=GA[i][j];
}
}
}
void fun(adjmatrix GA,adgeset>,int n)
{ int i;
for(i=0;i{
int min=10000,m=i;
for(int j=i;j{
if(GT[j].weight{
min=GT[j].weight;
m=j;
}
}
edgenode temp=GT[i];
GT[i]=GT[m];
GT[m]=temp;
int k=GT[m].rearvex;
for(j=i;j{
int t=GT[j].rearvex;
int w=GA[k][t];
if(w{
GT[j].weight=w;
GT[j].frontvex=k;
}
}
}
}
void display(adgeset GT,int n)
{
for(int i=0;i{
cout<<"第"<}
cout<<"这样修建可以使距离最短！";
}
int main()
{
cout<<"你要在几个城市间建设网络？请输入："<int n;
cin>>n;
adgeset GT;
adjmatrix GA;
insitadj(GA);
setadj(GA,n);
insit(GT,n,GA);
fun(GA,GT,n);
display(GT,n);
return 0;
}





克鲁斯卡尔算法
#include
using namespace std;
const int maxvertexnum=20;
const int maxedgenum=40;
struct edgenode
{
int frontvex;
int rearvex;
int weight;
};
typedef edgenode adgeset[maxedgenum];
//===============================================
void fun(adgeset&GE,adgeset>,int n);
void display(adgeset GT,int n);
void insit(adgeset >,int n);
//=============================================
void insit(adgeset>,int n)
{
int k=0,a;
for(int i=0;i{
for(int j=i+1;j{ cout<<"请输入第"<cin>>a;
GT[k].frontvex=i;
GT[k].rearvex=j;
GT[k].weight=a;
k++;
}
}
for(i=0;i{
int min=20000,m=i;
for(int j=i;j{
if(GT[j].weight{
min=GT[j].weight;
m=j;
}
}
edgenode temp=GT[i];
GT[i]=GT[m];
GT[m]=temp;
}

}
void fun(adgeset&GE,adgeset>,int n)
{
int i,j;
bool**s=new bool*[n];
for(i=0;ifor(i=0;i{
for(j=0;j{
if(i==j)s[i][j]=true;
else s[i][j]=false;
}
}
int k=1;
int d=0;
int m1,m2;
while(k{
for(i=0;i{
if(s[i][GT[d].frontvex]==true)m1=i;
if(s[i][GT[d].rearvex]==true)m2=i;
}
if(m1!=m2)
{
GE[k-1]=GT[d];
k++;
for(j=0;j{
s[m1][j]=s[m2][j]||s[m1][j];
s[m1][j]=false;
}
}
d++;
}
for(i=0;idelete []s;
}
void display(adgeset GT,int n)
{
for(int i=0;i{
cout<<"第"<}
cout<<"这样修建可以使距离最短！";
}
int main()
{
cout<<"你要在几个城市间建设网络？请输入："<int n;
cin>>n;
adgeset GT,GE;
insit(GT,n);
fun(GE,GT,n);
display(GE,n);
return 0;
}