实验二：最小生成树
摘要：
Prim 算法是最小生成树一般算法的特例, Prim 算法的特点是集合 A 的边总是只
形成单棵树.
问题重述
求最小生成树：
(1) 根据 Prim 算法编写一个求最小生成树的程序；
(2) 试求无向赋权图
[1 2 7;1 3 8;1 4 2;1 7 4;2 3 1;2 5 2;2 8 3;3 4 4;3 5 2;
3 6 7;4 6 3;4 7 6;5 6 5;5 8 1;6 7 4;6 8 3;7 8 6]
问题分析
求最小生成树，要保证连通图无圈，总权最小，可采用 Prim 算法进行求解。
该算法基本思路是：任选一个顶点（本实验取①为起始点），将其涂红，其余
顶点为白点；在一个端点为红色，另一个端点为白色的边中，找一条权最小的
边涂红，把该边的白端点也涂成红色；如此，每次将一条边和一个顶点涂成红
色，直到所有顶点都成红色、确定 n-1 条边为止。（注：图必须是无圈的连通
图）。 在每个白点到各红点的边中，必有一最短的白边，将红、白关联的最短
白边列入候选集，试验中以 V 为点集，以 q 为边权集，将点、边、权以矩阵形
式表示出来便于计算，结果所得的 result 矩阵中一、二、三行分别表示最小生
成树边的起点、终点、权集合。
问题分析
假设 V 是图中顶点的集合,E 是图中边的集合,TE 为最小生成树中的边的集合,
则 prim 算法通过以下步骤可以得到最小生成树:
1:初始化:U={u 0},TE={�}。设立一个只有结点 u 0 的结点集 U 和一个空
的边集 TE 作为最小生成树的初始行态,在随后的算法执行中,这个行态会不断的
发生变化,直到得到最小生成树为止。
2:在所有 u∈U,v∈V－U 的边(u,v)∈E 中,找一条权最小的边(u 0,v 0)，将此
边加进集合 TE 中，并将此边的非 U 中顶点加入 U 中。这步骤执行多次,每执行
一次,集合 TE 和 U 都将发生变化,分别增加一条边和一个顶点。
3:如果 U=V,则算法结束;否则重复步骤 2。可以把本步骤看成循环终止条件。
我们可以算出当 U=V 时,步骤 2 共执行了 n－1 次(设 n 为图中顶点的数目),TE
评论6