为什么只能求出两个呢,而不是全部最小生成树
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最小生成树
}