利用kruska，prim算法求解图的最小生成树，并比较算法的效率

这是我们的一个作业，要用C++编写，我不太会，希望哥哥姐姐们帮帮小弟，不胜感激！

adjmatrix GA 邻接矩阵GA
struct edgeset
{
int fromvex; 起始点
int endvex; 终点
int weight; 权值
}
void prim(adjmatrix GA,edgeset CT,int n)
{
int i,j,k,min,t,m,w;
for(i=0;i {
CT[i].fromvex=0;
CT[i].endvex=i+1;
CT[i].weight=GA[0][i+1];
}
for(k=1;k {
min=10000000; m=k-1;
for(j=k-1;j if(CT[j].weight {min=CT[j].weight; m=j;}
edge temp=CT[k-1];
CT[k-1]=CT[m];
CT[m]=temp;
j=CT[k-1].endvex;
for(i=k;i {
t=CT[i].endvex; w=GA[j][t];
if(w {
CT[i].weight=w; CT[i].fromvex=j;
}
}
}
}

void Kruckal(engeset GE,edgeset CT,int n)
{
int i,j;
bool**s=new bool**[n];
for(i=0;i s[i]=new bool[n];
for(i=0;i {
for(j=0;j if(i==j) s[i][j]=true;
else s[i][j]=false;
}
int k=1,d=0,m1,m2;
while(k {
for(i=0;i {
if(s[i][GE[d].fromvex]==true) m1=i;
if(s[i][GE[d].endvex]==true) m2=i;
}
if(m1!=m2)
{
CT[k-1]=GE[d]; k++;
for(j=0;j {
s[m1][j]=s[m1][j]||s[m2][j];
s[m2][j]=false;
}
}
d++;
}
for(i=0;i delete[]s[j];
delete[]s;
}
就这么多了kruckal算法的复杂度是O(n*n+n+lgn)
prim 算法的复杂度是O(n*n);

我不会~~~但还是要微笑~~~：）

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息