《最小生成树(Prim算法)》算法演示程序设计说明

0408 范成 

同济大学2004级计算机4班

一、设计要求

题目：编写Prim算法的最小生成树程序，输出一个给定无向带权图的最小生成树。

二、设计思想

最小生成树的定义：

假设一个单位要在n个办公地点之间建立通信网，则连通n个地点只需要n-1条线路。可以用连通的无向网来表示n个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树。

构造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为MST的性质：假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集。若(u,v)是一条具有最小权值（代价）的边，其中u∈U，v∈V-U，则必存在一棵包含边 (u.v)的最小生成树。

普里姆（Prim）算法即是利用MST性质构造最小生成树的算法。

算法思想如下：

假设N=(V,{E})和是连通网，TE是N上最小生成树中边的集合。算法从U={u0}( u0∈V)，TE={}开始，重复执行下述操作：在所有u∈U，v∈V-U的边(u, v) ∈E中找一条代价最小的边(u0, v0)并入集合TE，同时v0并入U，直到U=V为止。此时TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。

本程序中，采用图的邻接矩阵表示法，并使用二维数组表示网的邻接矩阵。

三、其他相关信息

开发平台：Microsoft Visual Studio.NET 2005 Professional

程序类型：Win32控制台应用程序

开发平台及程序运行截图：