最小生成树算法实验报告

作业1最小生成树的生成算法

1.1算法应用背景

在实际生活中，图的最小花费生成树问题有着广泛的应用。例如，用图的顶点代表城市，顶点与顶点之间的边代表城市之间的道路或通信线路，用边的权代表道路的长度或通信线路的费用，则最小花费生成树问题，就表示为城市之间最短的道路或费用最小的通信线路问题。其中普里姆算法是使用贪婪法策略设计的典型算法。

1.2算法原理

在一给定的无向图G = (V, E) 中，(u, v) 代表连接顶点 u 与顶点 v 的边（即），而 w(u, v) 代表此边的权重，若存在 T 为 E 的子集（即）且为无循环图，使得的 w(T) 最小，则此 T 为 G 的最小生成树。

许多应用问题都是一个求无向连通图的最小生成树问题。例如：要在n个城市之间铺设光缆，主要目标是要使这 n 个城市的任意两个之间都可以通信，但铺设光缆的费用很高，且各个城市之间铺设光缆的费用不同；另一个目标是要使铺设光缆的总费用最低。这就需要找到带权的最小生成树。

1.3算法描述

1)最小生成树之普里姆算法描述：

令G=(V,E,W)，为简单期间，令顶点集为V={0,1,2…，n-1}。假定与顶点i，j相关联的边为ei，j, ei，j的权用c[i][j]表示，T是最小花费生成树的边集。这个算法维护两个顶点集合S和N，开始时：令T=Ф,S={0},N=V-S。然后，进行贪婪选择，选取i∈S，j∈N，并且c[i][j]最小的i和j；并使S=S∪S{j},N=N-{j},T=T∪{ei，j}.重复上述步骤，直到N为空，或找到n-1条边为止。此时，T中的边集，就是所要求取的G中的最小花费生成树。由此，可描述普里姆算法的步骤如下：

（1）T=Ф，S={0},N=V-S。

（2）如果N为空，算法结束；否则，转步骤（3）。 （3）寻找使i∈S，j∈N，并且c[i][j]最小的i和j。 （4）S=S∪S{j},N=N-{j},T=T∪{ei，j}；转步骤（2）。 2)用贪心策略解普里姆算法的正确性证明

普里姆算法所产生的最小代价生成树的边集是 T，无向赋权图G 的最小代价生成树的

边集是T* ，用归纳法证明 T=T* 。

1. 开始时， T= Φ ，上述论点为真； 2. 把边e=(i,j) 加入到T 之前，论点为真.

令 G*=(S,T)是G的最小代价生成树的子树，按照算法，选择e=(i,j) 加入 T时， i∈S ，j∈ N,并且 c[i][j]最小, 并令 ， S`=S∪{j}， T`=T∪{e} ， G`=(S`,T`) 。

此时，有：

(1) G`是树。因为e 只和 S中的一个顶点关联，加入 后不会使G` 构成回路，且 G`仍然连通。

(2) G`是 G的最小代价生成树的子树。

因为，如果e∈T* ，这个结论成立；如果e∈T* ，那么，与 e关联的顶点，必是 T*中两个不相邻接的顶点，根据性质4， T* ∪{e} 将包含回路。

e是回路的一条边，且 ， e=(i,j) ， i∈S ，j∈ N 。则回路中必存在另一条边 ， e`=(x,y) ，x∈S ，y∈ N 。按算法的选择，e的权小于或等于e`的权。 令 T** =T*∪{e}- {e`}。则 T**的权小于或等于 T*的权。

若T**的权小于T*的权，与T* 是最小代价生成树的边集相矛盾，所以， e∈T* ；若T**的权等于T*的权，这时，用新的 T*来标记T** 。

在这两种情况下，都有 e1∈T* 。

综上所述T=T* ，普里姆算法所产生的生成树是 的最小代价生成树。

1.4程序实现及程序截图 1.4.1程序源码

#include "stdio.h" #define true 1 #define false 0

float int_max=0x7fff,graph[100][100]; int neig[100],key_point[100]; int s[100];//集合s

void prim(int end,int v); int main() {

2

int v,e; int i,j; int x=1; int start,end; float distance;

printf("请输入连通带权图的顶点数和边数："); while(scanf("%d%d",&v,&e)) {

printf("\n----------------------"); for(i=1;i<=v;i++)

{

for(j=1;j<=v;j++) graph[i][j]=int_max;

}

printf("\n请输入%d条边的起点和终点，以及权值。\n",e);

printf("\n-------------------------\n");

while(e--)

{

printf("第%d条边的起点：终点：权值",x); scanf("%d%d%f",&start,&end,&distance); graph[start][end]=graph[end][start]=distance; x=x+1;

}

printf("\n--------------------------\n"); prim(1,v); printf("\n"); }

return 0; }

void prim(int end,int v) { int i,j; float min; s[1]=true;//s={1} for(i=2;i<=v;i++) {

neig[i]=end;//顶点i的近邻

key_point[i]=graph[end][i];//顶点i的与近邻的

关联边的权值 s[i]=false; }

key_point[end]=0; for(i=2;i<=v;i++) {

end=1;

min=int_max;

for(j=1;j<=v;j++)//在n集合中检索与s最接近的顶点end

if(!s[j]&&key_point[j]<min)

{ end=j;

min=key_point[j];

}

if (end==1) break;//图非连通，退出循环

printf("起点%d-->终点%d连通",neig[end],end);

printf(" 权值为%0.2f\n",min); s[end]=true;

for(j=1;j<=v;j++) //更新n集合中的顶点的近邻信息 if(!s[j]&&graph[end][j]<key_point[j]) { key_point[j]=graph[end][j];

neig[j]=end;

}

} }

3

1.4.2程序截图

1.5学习或程序调试心得

2n这个算法在prim函数中有一个两层循环，那么最后共花费Θ（）时间，由于需要

使用数组存储解空间，则所需空间为Θ（n）。

4