最小生成树算法实验报告.docx

最小生成树算法
问题描述
设G=(V,E)是一个无向连通带权图，E中每条边(v,w)的权为c(v,w)。如 果G的一个子图G'是一棵包含G的所有顶点的书，则称G'为G的生成树。 生成树上各边权的总和称为该生成树的耗费，在 G的所有生成树中，耗费最
小的生成树就称为G的最小生成树。给定一个无向连通带权图，构造一个最 小生成树。
设计思想
利用 Prim 算法求最小生成树， Prim 算法是利用贪心策略设计的算法。
设G=(V,E)是一个连通带权图，V={1, 2,…，n}。构造G的一棵最小生成树 的Prim算法的基本思想是：首先置 U={1},然后，只要U是V的真子集，就 做如下的贪心选择：选取满足条件 i € U,j € V-U,且使c(i,j)达到最小的边 (i,j), 并将顶点j添加到U中。这个过程一致进行到U=V时为止。在这个过 程中选取到的所有边恰好构成G的一棵最小生成树。
时间复杂度
Prim 算法的 Pascal 语言描述如下：
Procedure PRIM(c:array[1..n,1..n] of real);
Var
lowcost:array[1..n] of real; closest:array[1..n] of integer; i,j,k,min,integer; begin
for i:=2 to n do
⑵begin{初始化，此时U只含有顶点1}
lowcost[i]:=c[1,i];
Closest[i]:=1;
end;
for i:=2 to n do
begin {寻找顶点分别在V-U与U中边权最小的边}
min:=lowcost[i];
j:=i;
For k:=2 to n do
If lowcost[k]<min then
Begin
Min:=lowcost[k];
j:=k;
End;
print(j,closest[j]);{ 输出找到的边 }
Lowcost[j]:= %;{将 j 添加到 U}
For k:=2 to n do { 调整 lowcost 和 closest}
if(c[j,k]<lowcost[k])and(lowcost[k]< %)then
Begin
Lowcost[k]:=c[j,k];
Closest[k]:=j;
End
End
End;{PRIM}
上述过程中第 (6)~(24) 行的 for 循环要执行 n-1 次，每次执行时，第 (10)~(15)行和第(18)~(23)行的for循环都要0(n)时间，所以Prim算 法所需的计算时间为 O(n2 )。
实验源代码
图定义头文件 ：
const int MaxV=10;// 最多顶点数
const int MaxValue=99;// 最大权值
// 定义边集数组中的元素类型
struct RCW
{int row,col;
int weight;
};
class adjMList
{
private:
int numE;// 当前边数
int GA[MaxV][MaxV];// 定义邻接矩阵
public:
// 构造函数 , 初始化图的邻接矩阵与边集数组
adjMList(RCW