《提高实验—最小生成树的Prim算法一实验目的和要求根据算法设计需要,掌握连通网的灵活表示方法.docx》由会员分享，可在线阅读，更多相关《提高实验—最小生成树的Prim算法一实验目的和要求根据算法设计需要,掌握连通网的灵活表示方法.docx（6页珍藏版）》请在三一文库上搜索。
1、最小生成树 (Prim 算法 )算法演示程序设计说明040648 范成同济大学 2004 级计算机 4 班一、设计要求题目：编写Prim 算法的最小生成树程序，输出一个给定无向带权图的最小生成树。二、设计思想最小生成树的定义：假设一个单位要在n 个办公地点之间建立通信网，则连通n 个地点只需要n-1 条线路。可以用连通的无向网来表示n 个地点以及它们之间可能设置的通信线路，其中网的顶点表示城市，边表示两地间的线路，赋于边的权值表示相应的代价。对于n 个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以表示一个通信网。其中一棵使总的耗费最少，即边的权值之和最小的生成树，称为最小生成树 。构
2、造最小生成树可以用多种算法。其中多数算法利用了最小生成树的下面一种简称为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 控制台应用程序开发平台及程序运行截图：