| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 512 人关注过本帖
标题:Kruskal 有什么问题
取消只看楼主 加入收藏
fjfhfv
Rank: 1
等 级:新手上路
帖 子:2
专家分:0
注 册:2006-5-31
收藏
 问题点数:0 回复次数:0 
Kruskal 有什么问题

为什么只能求出两个呢,而不是全部最小生成树

include "graph2.h" //包含图的头文件
#define N 10 //设定最大的顶点数
#define M 30 //设定结果数组中行的长度,应大于4*(n-1)
#define MAX 32767 //设定最大的边长

int A[N][N],gtree[N][M],gt=0,n; //定义全局变量
datagraph G,grp[N];

void kruscal(int inserted,int tree[]) //求所有最小生成树的函数kruscal
{
int v,w,i,weight,temp,tree1[N]; //定义变量
if(inserted<n-1) //若边数小于n-1
{
weight=MAX; //weight的值设为最大边长
for(v=1;v<=n;v++) //遍历所有边
{
w=firstadj(G,v);
while(w!=0)
{
if(tree[v]!=tree[w]) //求出可取的最小边长weight
{
temp=A[v][w];
if(temp<weight) weight=temp;
}
w=nextadj(G,v,w);
}
}
for(v=1;v<=n;v++) //再次遍历所有边
{
w=firstadj(G,v);
while(w!=0)
{
temp=A[v][w];
if(temp==weight&&tree[v]!=tree[w]) //若v,w之间的边为可取的最小边
{
for (i=0;i<=n;i++) //将tree数组复制进tree1数组
tree1[i]=tree[i];
copy_all_vertex(G,grp[inserted+1],0,0); //复制grp[inserted]的图结构进grp[inserted+1]中
copy_all_edge(grp[inserted],grp[inserted+1]);
copy_edge(G,v,w,grp[inserted+1]); //在grp[inserted+1]中插入v,w间的新边
display_graph("kruscal",grp[inserted+1]);Wait(); //显示插入后的图
for(i=1;i<=n;i++) //将w树中的点转变为v树中点
if(tree[i]==tree[w])
tree1[i]=tree[v];
kruscal(inserted+1,tree1); //递归调用kruscal函数
setnull_graph(grp[inserted+1],true,false); //递归结束,将图初始化
}
w=nextadj(G,v,w);
}
}
}
else //当插入了n-1条边后进行结果检测
{
int k,j=0;
for(i=0;i<gt;i++) //遍历gtree数组中保存的各解
{k=0;
while(k<(n*4-5))
{
v=gtree[i][k];k++; //得到v,w的值
w=gtree[i][k];k++;
if(!have_edge(grp[inserted],v,w)) break; //检测图中是否有v,w之间的边
}
if(k==n*4-4) return; //若有若有此解则返回
else j++; //若无此解则j自增
}
if(j==gt) //j与解数相同,结果数组中无此解,应添加此解
{i=0; //写入此解
for(v=1;v<=n;v++)
{
w=firstadj(grp[inserted],v);
while(w!=0)
{
gtree[gt][i]=v;i++;
gtree[gt][i]=w;i++;
w=nextadj(grp[inserted],v,w);
}
}
gt++; //解数加1
}
display_graph("最小生成树",grp[inserted]);Wait(); //显示此最小生成树
return; //返回
}
}

void matrix() //由原图得到邻接矩阵
{
int v,w;
for(v=1;v<=n;v++) //遍历各顶点
for(w=1;w<=n;w++)
{
if(have_edge(G,v,w)) //若v,w有边,则邻接矩阵中A[v][w]的值就为边的权值
A[v][w]=edge_weight(G,v,w);
else A[v][w]=MAX; //若无此边则邻接矩阵的值为最大边长(无穷远)
}
}

void krus() //库鲁斯科尔算法
{
int i,tree[N];
n=nodes(G); //求定点数
matrix(); //产生邻接矩阵
for (i=1;i<=n;i++) //初始化tree数组
tree[i]=i;
copy_all_vertex(G,grp[0],0,0); //初始化图grp[0]
kruscal(0,tree); //调用kruscal函数,开始计算
}

void main() //主函数
{
load_graph_file(G,"graphs\\gtest.grp"); //读取图结构至G
display_graph("Origin graph",G); //显示原图
Wait();
krus(); //求解kruscal最小生成树
}

搜索更多相关主题的帖子: Kruskal 
2006-05-31 18:30
快速回复:Kruskal 有什么问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.025695 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved