提高实验—最小生成树的Prim算法一实验目的和要求根据算法设计需要,掌握连通网的灵活表示方法

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=uO( u0 V), TE=开始，重复执行下述操作：在所有 u U , v V-U的边(u, v) E中找一条代价最 小的边(u0, v0)并入集合TE,同时v0

3、并入U，直到U=V为止。此时TE中必有n-1条边，则 T=(V,TE) 为 N 的最小生成树。本程序中，采用图的 邻接矩阵 表示法，并使用二维数组表示网的邻接矩阵。三、其他相关信息开发平台：Microsoft Visual Studio.NET 2005 Professio nal'关于 Mier050Ft VfsudL Studio-pF X "Micrawfr Visual Studio 2005Professional Edition授祝给:KENSHINTongji UniversityMicrosoft Visual Studio 20050,50727,42 (R

4、TMX50727-4200) © 3005 Microsoft 匚orporation. 保整所有权利.Microsoft .NET Framework版本 © 2005 Microsoft 匚orporation D 保留所有枚利。已安装的产品（D：亘制信息©系统信息（勺Microsoft Visual 说朮 2005 77933 1987 McrosoFt Visual C# 2005 7798341967啊iur停Mt WebI匚十十辽了了箱3-如勺-0心兀卩-斗1無7Microsoft Visual J#

5、 2005 779S341937Microsoft Visual Web Developer 2005 779S3-O09-QQO0CO7- 419S7产品详细信息:Microsoft Visual C+2005警告：本计算机程序受版权法和国际案约保护.如未经授权而擅自复制或俺播 本程序（或苴中任何部分），将受到严厉的民爭和刑爭制社 > 并将在法逹许可的 畐大限度內受到起诉程序类型：Win32控制台应用程序开发平台及程序运行截图:最小生成轲(Trim算法) Mcroofl Visual Studio文件0）貓辑）视圉辺项目g）生成d）调试）工具阿口地）社区

6、69; 桔助Qi）» Release Win32Dr aw Active 詡杲小生成树（Pri.n法）刁D头文件h stdafx. h-源文件 std&fx. cpp色最小生成轲（Prirrffl法）. 刁资湧文件 Re&dMe. txt解决方寒资憑管理器-二 Q X星小生«« CPri.fi法）cpp起赠页 X准局范團）BBvoid mainOi nt choi c=6“ «x i st=0;while （choice!=0）printf CnniS选择操作:nn"）; printfCl.祖一个无向网并显示其最小生成树廿）:

7、pnntfC2.显示当前无向网及其最小生成树rT）: printfCO 退出5“）：scwfUchoi Ct):switch(choice)case 1:CreateUDNCG);MiniSpanTree_PRIM(G); xist=l;break;ctst 2：if (exist)Di,p“yUDN(G)： iniSpanTree PRIM(G);Is* printf CniW先创建一个无向网？ n")： break;1珂星小生成树（Prin译 Visual Studio Pr.枫 咼 ©® F:Visual Studio Projects040648范成-计算

8、机科学与技术可执行文件最小生成树GVim算法）.exe X请选择操作：1.创建一个无向网并显丞其最小生成树2 .显示当前无向网及其巖小生成树 0 退由zl-|g|x|駅F 'Visual Studio Projcts040648-范成-计算机科学与技术可执行文件最小生成树（Trim算法）.x导选择操作：.创建一个无向网并显衣其最小生成树显不当前无向网及其巖小生成树退由先创建一个无向网!导选择操作：警轉釀隸鸚成树意彈黯矗权驟聽豁觀结果岀错；如此两顶点间不存在边,输入0日-日Bl、-日-日Bl、 、 2345345455 与与与与与与与与与与 1111222334 点点点点点点点点点点 瓦瓦瓦瓦瓦瓦瓦瓦瓦瓦4687259A3（括号内的数字为边的权值）:页点顶点2 页点l-<4>-顶点3 页点2 - <2-顶点4 页点4-<3>-顶点5请选择操作:-J«5营F:Visual Studio P“jcts040648-范成计算机科学与技术可执行文件焜小生成树Grim算法）.exe导选择操作讎轉釀隸鸚成树（共有5个顶点,括号內的数字为两顶点间的边的权值）:111122234点点点点