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

来源:百度知道 编辑:UC知道 时间:2024/09/20 09:23:51
这是我们的一个作业,要用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<n-1;i++)
{
CT[i].fromvex=0;
CT[i].endvex=i+1;
CT[i].weight=GA[0][i+1];
}
for(k=1;k<n;k++)
{
min=10000000; m=k-1;
for(j=k-1;j<n-1;j++)
if(CT[j].weight<min)
{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<n-1;i++)
{
t=CT[i].endvex; w=GA[j][t];
if(w<CT[i].weight)
{
CT[i].weight=w; CT[i].fromvex=j;
}
}
}
}

void Kruckal(engeset GE,edgeset CT,int n)
{
int i,j;