8.5 最小生成树—构造最小生成树的Kruskal算法
Kruskal 算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。
对于图8.23(a)所示的网，按照Kruskal 方法构造最小生成树的过程如图8.25 所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
下面介绍Kruskal 算法的实现。
设置一个结构数组Edges 存储网中所有的边，边的结构类型包括构成的顶点信息和边权值，定义如下：
#define MAXEDGE <图中的最大边数>
typedef struct {
elemtype v1;
elemtype v2;
int cost;
} EdgeType;
EdgeType edges[MAXEDGE];
在结构数组edges 中，每个分量edges[i]代表网中的一条边，其中edges[i].v1 和edges[i].v2 表示该边的两个顶点，edges[i].cost 表示这条边的权值。为了方便选取当前权值最小的边，事先把数组edges 中的各元素按照其cost 域值由小到大的顺序排列。在对连通分量合并时，采用7.5.2 节所介绍的集合的合并方法。对于有n 个顶点的网，设置一个数组father[n]，其初值为father[i]=-1（i＝0，1，…，n－1），表示各个顶点在不同的连通分量上，然后，依次取出edges 数组中的每条边的两个顶点，查找它们所属的连通分量，假设vf1和vf2 为两顶点所在的树的根结点在father 数组中的序号，若vf1 不等于vf2，表明这条边的两个顶点不属于同一分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量。
下面用C 语言实现Kruskal 算法，其中函数Find 的作用是寻找图中顶点所在树的根结点在数组father 中的序号。需说明的是，在程序中将顶点的数据类型定义成整型，而在实际应用中，可依据实际需要来设定。
typedef int elemtype;
typedef struct {
elemtype v1;
elemtype v2;
int cost;
}EdgeType;
void Kruskal（EdgeType edges[ ]，int n）
/*用Kruskal 方法构造有n 个顶点的图edges 的最小生成树*/
{ int father[MAXEDGE];
int i,j,vf1,vf2;
for (i=0;i<n;i++) father[i]=-1;
i=0;j=0;
while(i<MAXEDGE && j<n-1)
{ vf1=Find(father,edges[i].v1);
vf2=Find(father,edges[i].v2);
if (vf1!=vf2)
{ father[vf2]=vf1;
j++;
printf(“%3d%3d\n”,edges[i].v1,edges[i].v2);
}
i++;
}
}
算法8.15
int Find（int father[ ]，int v）
/*寻找顶点v 所在树的根结点*/
{ int t;
t=v;
while(father[t]>=0)
t=father[t];
return(t);
}
算法8.16
在Kruskal 算法中，第二个while 循环是影响时间效率的主要操作，其循环次数最多为MAXEDGE 次数，其内部调用的Find 函数的内部循环次数最多为n，所以Kruskal 算法的时间复杂度为O（n·MAXEDGE）。
对于图8.23(a)所示的网，按照Kruskal 方法构造最小生成树的过程如图8.25 所示。在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。
下面介绍Kruskal 算法的实现。
设置一个结构数组Edges 存储网中所有的边，边的结构类型包括构成的顶点信息和边权值，定义如下：
#define MAXEDGE <图中的最大边数>
typedef struct {
elemtype v1;
elemtype v2;
int cost;
} EdgeType;
EdgeType edges[MAXEDGE];
在结构数组edges 中，每个分量edges[i]代表网中的一条边，其中edges[i].v1 和edges[i].v2 表示该边的两个顶点，edges[i].cost 表示这条边的权值。为了方便选取当前权值最小的边，事先把数组edges 中的各元素按照其cost 域值由小到大的顺序排列。在对连通分量合并时，采用7.5.2 节所介绍的集合的合并方法。对于有n 个顶点的网，设置一个数组father[n]，其初值为father[i]=-1（i＝0，1，…，n－1），表示各个顶点在不同的连通分量上，然后，依次取出edges 数组中的每条边的两个顶点，查找它们所属的连通分量，假设vf1和vf2 为两顶点所在的树的根结点在father 数组中的序号，若vf1 不等于vf2，表明这条边的两个顶点不属于同一分量，则将这条边作为最小生成树的边输出，并合并它们所属的两个连通分量。
下面用C 语言实现Kruskal 算法，其中函数Find 的作用是寻找图中顶点所在树的根结点在数组father 中的序号。需说明的是，在程序中将顶点的数据类型定义成整型，而在实际应用中，可依据实际需要来设定。
typedef int elemtype;
typedef struct {
elemtype v1;
elemtype v2;
int cost;
}EdgeType;
void Kruskal（EdgeType edges[ ]，int n）
/*用Kruskal 方法构造有n 个顶点的图edges 的最小生成树*/
{ int father[MAXEDGE];
int i,j,vf1,vf2;
for (i=0;i<n;i++) father[i]=-1;
i=0;j=0;
while(i<MAXEDGE && j<n-1)
{ vf1=Find(father,edges[i].v1);
vf2=Find(father,edges[i].v2);
if (vf1!=vf2)
{ father[vf2]=vf1;
j++;
printf(“%3d%3d\n”,edges[i].v1,edges[i].v2);
}
i++;
}
}
算法8.15
int Find（int father[ ]，int v）
/*寻找顶点v 所在树的根结点*/
{ int t;
t=v;
while(father[t]>=0)
t=father[t];
return(t);
}
算法8.16
在Kruskal 算法中，第二个while 循环是影响时间效率的主要操作，其循环次数最多为MAXEDGE 次数，其内部调用的Find 函数的内部循环次数最多为n，所以Kruskal 算法的时间复杂度为O（n·MAXEDGE）。
