贪心Kruskal算法生成树C实现代码
发布时间：2020-12-16 07:47:56 所属栏目：百科 来源：网络整理
导读：今天PHP站长网 52php.cn把收集自互联网的代码分享给大家，仅供参考。 #include iostream.h #define Max 100 typedef struct{ int u; int v; int weight; }edge; edge edges[Max]; int nodes[Max]; void interchange(edge*
|
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家，仅供参考 #include <iostream.h>
#define Max 100
typedef struct{
int u;
int v;
int weight;
}edge;
edge edges[Max];
int nodes[Max];
void interchange(edge* m,edge* n)
{
edge temp=*m;
*m=*n;
*n=temp;
}
int partition(edge array[],int p,int q)
{
int i,j;
i=p;
j=q+1;
while(1)
{
do i++;
while((array[i].weight<array[p].weight)&&(i!=q));
do j--;
while((array[j].weight>array[p].weight)&&(j!=p));
if(i<j)
interchange(&array[i],&array[j]);
else
break;
}
interchange(&array[p],&array[j]);
return j;
}
void quicksort(edge array[],int q)
{
int j;
if (p<q)
{
j=partition(array,p,q);
quicksort(array,j-1);
quicksort(array,j+1,q);
}
}
void main()
{
int i,j,m,n,nodenum,edgenum,safe,cost=0,flag=1 ;
int presult = 0;
cout<<"Input the number of nodes and edges:";
cin>>nodenum>>edgenum;
cout<<"请输入每条边的起点、终点及权值："<<endl;
for(i = 0; i < edgenum; i++)
{
cin>>edges[i].u>>edges[i].v>>edges[i].weight;
}
for(i=1;i<=nodenum;i++)
nodes[i]=0;
quicksort(edges,edgenum-1);
for(i = 0; i < edgenum ; i++)
{
m = edges[i].u;
n = edges[i].v;
safe = 0;
if(nodes[m] == 0 &&nodes[n] == 0){
nodes[m] = flag;
nodes[n] =flag;
flag++;
safe = 1;//a safe edge
}
else
{
if(nodes[m] == 0 ||nodes[n] == 0 )
{
if(nodes[m] == 0 )
nodes[m] = nodes[n];
else nodes[n]=nodes[m];
safe = 1;//a safe edge
}
else
if(nodes[m] != nodes[n])
{
for(j = 1; j <= nodenum; j++)
{
if((nodes[j] == nodes[m] || nodes[j] == nodes[n])&&(j!=m&&j!=n))
{
nodes[j] = flag;
}
}
nodes[m]=flag;
nodes[n]=flag;
flag++;
safe = 1;//a safe edge
}
}
if(safe == 1){//reserve a safe edge
edges[presult].u = m;
edges[presult].v = n;
edges[presult].weight = edges[i].weight;
presult++;
}
if(presult == nodenum-1 ){//found mst
break;
}
}
cout<<"Print the result:"<<endl;
cout<<"起点 终点 权值"<<endl;
for(i = 0; i < presult; i++)
{
cost=cost+edges[i].weight;
cout<<edges[i].u<<" "<< edges[i].v<<" "<< edges[i].weight<<endl;
}
cout<<"最小生成树的权值为："<<cost<<endl;
}
以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助，欢迎收藏、点赞、推荐、分享。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |