1.无向网图及边集数组存储示意图
vertex[6]=
2.Kruskal 方法构造最小生成树的过程
(a)一个图 (b)最小生成树过程1
V0 V1 V2 V3 V4 V5
下标 0 1 2 3 4 5 6 7 8 from 1 2 0 2 3 4 0 3 0 to
4
3 5 5 5 5 1
4 2 weight 12
17
19
25
25
26
34
38
46
V1
V0
V4 V5
V2 V3
V1
V0 V5 V2 V3 V4
(c)最小生成树过程2 （d)最小生成树过程3
(e)最小生成树过程4 3.伪代码
1）初始化辅助数组parent[vertexNum];num=0; 2) 依次考查每一条边for(i=0; i<arcNum; i++ ) vex1=edge[i].form 所在生成树的根结点 vex2=edge[i].to 所在生成树的根结点 If(vex1!=vex2)
parent[vex2]=vex1; num++;
if(num==vertexNum-1) 算法结束 4.构造过程中参数变化
顶点集 数组 parent V0 V1 V2 V3 V4 V5
被考查边 输出
说明
初始化
parent -1 -1 -1 -1 -1 -1
6棵生成树，均只有根结点 parent -1 -1 -1 -1 1 -1 (v1,v4)12 (v1,v4)12 vex1=1,vex2=4;parent[4]=1; parent -1 -1 -1 2 1 -1 (v2,v3)17 (v2,v3)17 vex1=2,vex2=3;parent[3]=2; parent -1 -1 -1 2 1 0 (v0,v5)19 (v0,v5)19 vex1=0,vex2=5;parent[5]=0; parent 2 -1 -1 2 1 0 (v2,v5)25 (v2,v5)25 vex1=2,vex2=0;parent[0]=2; parent 2 -1 -1 2 1 0 (v3,v5)25 vex1=2,vex2=2;所在根结点相同 parent 2 -1 1 2 1 0 (v4,v6)26 (v4,v6)26 vex1=1,vex2=2;parent[2]=1; parent 2
-1
1
2
1
生成树根结点是v1
5.主要代码
/**********构造函数************/
template<class DataType>
EdgeGraph<DataType>::EdgeGraph(DataType a[], int n, int e)
{
vertexNum=n; edgeNum=e;
int i,j,weight;
for (int k=0; k<vertexNum; k++)
vertex[k]=a[k];
for (k=0; k<edgeNum; k++)
{
cout<<"输入边依附的两个顶点的编号:";
cin>>i>>j;
edge[k].from=i;
edge[k].to=j;
cout<<"请输入权重：";
cin>>weight;
edge[k].weight=weight;
}
}
/**********Kruskal算法构造最小生成树************/
template <class DataType>
void EdgeGraph<DataType>::Kruskal()
{ int num;
int parent[MaxVertex], vex1, vex2;
for (int i=0; i<vertexNum; i++)
parent[i]=-1;
for (i=0,num=0; i<edgeNum; i++)
{
vex1=FindRoot(parent, edge[i].from);
vex2=FindRoot(parent, edge[i].to);
if (vex1!=vex2)
{
cout << "(" << edge[i].from <<"->"<<edge[i].to << ")" <<"weight: "<< edge[i].weight << endl;
parent[vex2]=vex1;
num++;
if (num==vertexNum-1) return;
}
}
}
/**********寻找根节点************/
template <class DataType>
int EdgeGraph<DataType>::FindRoot(int parent[], int v)
{
int t=v;
while(parent[t] > -1)
t=parent[t];
return t;
}
/**********遍历输出************/
template <class DataType>
void EdgeGraph<DataType>::Print()
{
for (int i=0; i<edgeNum; i++)
{
cout<<"("<<edge[i].from<<"
"<<edge[i].to<<")"<<"weight:"<<edge[i].weight<<endl;;
}
}
6.结果截图
发现不按大小输入weight的值则不能正确生成最小生成树如排好序输入时则得到正确的最小生成树
结果正确，所以需要按大小顺序输入权值大小的Kruskal算法实际上对较复杂无向网图来说不适用。

故思考在程序中添加一个对权值排序的函数(修改对应的from,to)。