最小生成树问题课程设计报告

最小生成树（Minimum Spanning Tree）实验报告1. 实验目的本实验旨在通过实践掌握最小生成树算法的基本原理和实现方法。

最小生成树是图论中的一个重要概念，用于解决具有权重的连通图的最优路径问题。

通过本实验，我们将学习如何使用最小生成树算法找到一棵连接图的所有节点且总权重最小的树。

2. 实验原理最小生成树是一个连通图的一种生成树，它的所有边的权重之和最小。

最小生成树的求解算法有多种，其中两种常用的算法是 Prim 算法和 Kruskal 算法。

2.1 Prim 算法Prim 算法是一种贪心算法，从一个节点开始，逐步扩展最小生成树的边。

具体步骤如下： 1. 选择一个起始节点作为最小生成树的根节点。

2. 在当前最小生成树的所有节点中选择一个与该树相连接的权重最小的边，将其加入最小生成树。

3. 将该节点标记为已访问。

4. 重复步骤 2 和步骤 3，直到所有节点都被访问。

2.2 Kruskal 算法Kruskal 算法也是一种贪心算法，通过不断选择权重最小的边来构建最小生成树。

具体步骤如下： 1. 对所有边按照权重进行排序。

2. 依次选择权重最小的边，如果该边的两个端点不在同一个连通分量中，则将该边加入最小生成树，并将这两个端点合并到同一个连通分量中。

3. 重复步骤 2，直到所有节点都在同一个连通分量中，即最小生成树构建完成。

3. 实验步骤本实验将使用 Prim 算法和 Kruskal 算法分别求解给定图的最小生成树。

3.1 数据准备首先，我们需要准备一个具有权重的连通图作为实验数据。

假设该图有 n 个节点和 m 条边，我们可以使用邻接矩阵或邻接表来表示这个图。

3.2 Prim 算法求解最小生成树1.首先，选择一个起始节点作为最小生成树的根节点，并将该节点标记为已访问。

2.初始化一个空的最小生成树，用于存储最终的结果。

3.重复以下步骤，直到所有节点都被访问：1.在当前最小生成树的所有节点中选择一个与该树相连接的权重最小的边，将其加入最小生成树。

运筹学课程设计报告书专业班级学号姓名LMZZ日期2011.09.01设计题目：最小生成树问题设计方案：本设计是在C语言环境下运行的，主要有:minitree_KRUSKAL()此函数包含几个算法有对树的邻接矩阵的构造，数据的输入，克鲁斯卡尔算法（又称Kruskal算法，其类似于求生成树的“避圈法”）求网的最小生成树，最小生成树的最小代价，输出最小生成树的顶点及其最小代价。

ljjzprint(int n)定义并输出邻接矩阵。

主程序：int main(){minitree_KRUSKAL(); （函数调用）printf("输出邻接矩阵是：\n");ljjzprint(n); （函数调用）}方案实施：• 1、定义结构体以及各个变量；• 2、数据的输入；• 3、采用克鲁斯卡尔算法求出该图的最小生成树；• 4、采用邻接矩阵做储存结构创建图；• 5 、在主函数中分别调用以上各个函数，最终实现设计目的。

克鲁斯卡尔算法的表示：while (i <n){ min=INFINITE;for (j=0;j <m;j++){if (e[j].weight <min&&e[j].flag==0){min=e[j].weight;sum+=min;k=j;}}if (t[e[k].vexh].jihe!=t[e[k].vext].jihe) {e[k].flag=1;for (j=1;j <=n;j++)if (t[j].jihe==t[e[k].vext].jihe)t[j].jihe=t[e[k].vexh].jihe;t[e[k].vext].jihe=t[e[k].vexh].jihe;i++;}else e[k].flag=2;}邻接矩阵的表示：void ljjzprint(int n)/*定义并输出邻接矩阵*/{int i,j;for(i=1;i<=n;i++){for(j=1;j<=n;j++)printf("%d\t",adjmatrix[i][j]);printf("\n");}}int main(){minitree_KRUSKAL(); 函数调用printf("输出邻接矩阵是：\n");ljjzprint(n); 输出矩阵return 0;}调试过程：原设计在定义输出矩阵函数时，没有形参，在调用时必须输入树的定点数这和前面的函数在输入树的数据时重复操作，为了避免重复如果这个函数添加一个参数为n的形参，再main函数调用minitree_KRUSKAL();后n为定值，n为了在ljjzprint(n)中为已知量则需在程序的开头定义一个全局变量n即可。

武夷学院课程设计报告课程名称：数据结构设计题目：最小生成树的应用学生班级：09计科2班学生姓名：蒋家权，陈相财，吴继伟，梁丽春指导教师：林丽惠完成日期：2011-1-19课程设计项目研究报告目录一、问题分析和任务定义....................................................................................... - 1 -二、实现本程序需要解决的问题如下................................................................... - 1 -三、测试数据........................................................................................................... - 2 -四、算法思想........................................................................................................... - 3 -五、模块划分........................................................................................................... - 4 -六、算法设计与分析............................................................................................... - 7 -七、源程序............................................................................................................. - 11 -八、测试数据......................................................................................................... - 14 -九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 -十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 -一、问题分析和任务定义在n个城市间建立通信网络，需架设n-1条线路。

实验5 最小生成树算法的设计与实现一、实验目的1、根据算法设计需要, 掌握连通图的灵活表示方法；2、掌握最小生成树算法，如Prim、Kruskal算法；3、基本掌握贪心算法的一般设计方法；4、进一步掌握集合的表示与操作算法的应用。

二、实验内容1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法；2、设计Kruskal算法实验程序。

有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。

设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。

三、Kruskal算法的原理方法边权排序:1 3 14 6 23 6 41 4 52 3 53 4 52 5 61 2 63 5 65 6 61. 初始化时：属于最小生成树的顶点U={}不属于最小生成树的顶点V={1，2，3，4，5，6}2. 根据边权排序，选出还没有连接并且权最小的边（1 3 1），属于最小生成树的顶点U={1，3}，不属于最小生成树的顶点V={2,4,5,6}3. 根据边权排序，选出还没有连接并且权最小的边（4 6 2），属于最小生成树的顶点U={{1，3}，{4，6}}（还没有合在一起，有两颗子树），不属于最小生成树的顶点V={2,5}4. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，3，4，6}（合在一起），不属于最小生成树的顶点V={2,5}5. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，6},，不属于最小生成树的顶点V={5}6. 根据边权排序，选出还没有连接并且权最小的边（3 6 4），属于最小生成树的顶点U={1，2，3，4，5，6}此时，最小生成树已完成四、实验程序的功能模块功能模块：bool cmp(Edge a,Edge b)； //定义比较方法x)；//在并查集森林中找到x的祖先int g etfa(intint s ame(int x,int y)； //判断祖先是否是同一个，即是否联通 void merge(int x,int y); //合并子树，即联通两子树sort(e+1,e+m+1,cmp); //对边按边权进行升序排序详细代码：#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#define M AXN_E 100000#define M AXN_V 100000using namespace std;struct Edge{int f m,to,dist;//边的起始顶点，边的到达顶点，边权}e[MAXN_E];int f a[MAXN_V],n,m; //顶点数组，顶点总数，边总数 //定义比较，只是边权比较bool cmp(Edge a,Edge b){return a.dist < b.dist;}//查找x的祖先是在并查集森林中找到x的祖先x){//getfaint g etfa(intreturn fa[x];if(fa[x]==x)else r eturn fa[x] = getfa(fa[x]);}//判断祖先是否是同一个，即是否联通int s ame(int x,int y){return getfa(x)==getfa(y);}//合并两棵树void merge(int x,int y){int f ax=getfa(x),fay=getfa(y);fa[fax]=fay;}int m ain(){int i;cout<<"请输入顶点数目和边数目："<<endl;cin>>n>>m;//n为点数，m为边数//输出顶点信息cout<<"各个顶点值依次为："<<endl;for(i=0;i<n;i++){fa[i]=i;if(i!=0)cout<<fa[i]<<" ";}cout<<endl;cout<<"请输入边的信息（例子：1 4 5 从顶点1到顶点4的边权为5）"<<endl;for(i=1;i<=m;i++)用边集数组存放边，方便排序和调用 cin>>e[i].fm>>e[i].to>>e[i].dist;//sort(e+1,e+m+1,cmp); //对边按边权进行升序排序表示目前的点共存在于多少个集合中，初始情况是每 int r st=n,ans=0;//rst个点都在不同的集合中for(i=1;i<=m && rst>1;i++){int x=e[i].fm,y=e[i].to;函数是查询两个点是否在同一集合中 if(same(x,y))continue;//sameelse{函数用来将两个点合并到同一集合中 merge(x,y);//mergerst--;//每次将两个不同集合中的点合并，都将使rst值减1这条边是最小生成树中的边，将答案加上边权 ans+=e[i].dist;//}}cout<<ans;return 0;}五、测试数据和相应的最小生成树Input:6 101 2 61 3 11 4 52 3 52 5 63 4 53 5 63 6 44 6 25 6 6Putout:18生成树为：七、思考题1、微软面试题一个大院子里住了50户人家，每家都养了一条狗，有一天他们接到通知说院子里有狗生病了，并要求所有主人在发现自己家狗生病的当天就要把狗枪杀掉。

二○一○届课程设计论文《算法与数据结构》二〇一〇年六月目录一、引言…………………………………………二、设计目的与任务………………………………1·课程设计的目的2·课程设计的任务三、设计方案………………………………………1·需求分析2·概要设计3·详细设计4·程序清单四、调试分析………………………………………五、测试结果………………………………………六、附录……………………………………………七、工作环境………………………………………八、参考文献……………………………《数据结构》课程设计——最小生成树问题一、引言《数据结构》是计算机科学与技术专业和信息系统专业的必修课之一，是一门综合的专业技术课。

本课程较系统的介绍了软件开发过程中常用的数据结构及相应的实现算法。

如线性表、栈、队列、树和二叉树，图、检索和排列等，并对性能进行分析和比较，内容非常丰富。

本课程设计我们要解决的是最小生成树问题。

要用到图的相关数据结构和最小生成树的克鲁斯卡尔算法，以及存储图的边和点的邻接矩阵。

本课程设计要解决的问题是构造连通图的最小生成树我们首先要做的是都造一个邻接表，用以存储图，然后我们要想好怎样利用克鲁斯卡尔算法构造最小生成树，把这个算法写入主程序，调试好程序，最后完成报告。

二、设计目的与任务1·课程设计的目的本课程设计是为了了解并掌握数据结构及算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的相关步骤；提高运用所学理论知识独立分析和解决问题的能力；训练用系统的观点和软件开发的一般规范进行软件开发。

2·课程设计的任务问题描述：若要在n个城市之间建设通信网络，只需架设n—1条线路即可。

如何以最低的经济代价建设这个通信网，是一个最小生成树的问题。

三、设计方案1·需求分析（1）利用克鲁斯卡尔算法求最小生成树；（2）实现教科书6.5节中抽象数据类型MFSet。

课程设计报告问题描述:已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。

对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。

我们要选择一棵生成树，使总的耗费最小（1）需求分析：在N地建设网络保证连通即可求最小的架设方式，任务完成可分为两个部分：A 存储N中任意两地之间的权（采用邻接表，邻接矩阵）B 用prim和克鲁斯卡尔两种算法分别求出N地中最优架设方式即最小生成树。

C 按顺序输出生成树中各条边以及它们的权值。

（2）概要设计：程序分为两大部分 1 存储部分，2 算法部分；存储部分分为邻接矩阵和邻接表，而且包含了两者直接的互相转换；算法部分分为普里母算法和克鲁斯卡尔算法。

Prim算法的思想：假设V是图中顶点的集合,E是图中边的集合,TE为最小生成树中的边的集合,则prim算法通过以下步骤可以得到最小生成树:1:初始化:U={u 0},TE={f}。

此步骤设立一个只有结点u 0的结点集U 和一个空的边集TE作为最小生成树的初始形态,在随后的算法执行中,这个形态会不断的发生变化,直到得到最小生成树为止。

2:在所有u∈U,v∈V－U的边(u,v)∈E中,找一条权最小的边(u 0,v 0)，将此边加进集合TE中，并将此边的非U中顶点加入U中。

此步骤的功能是在边集E中找一条边,要求这条边满足以下条件:首先边的两个顶点要分别在顶点集合U和V－U中,其次边的权要最小。

找到这条边以后,把这条边放到边集TE中,并把这条边上不在U中的那个顶点加入到U中。

这一步骤在算法中应执行多次,每执行一次,集合TE和U都将发生变化,分别增加一条边和一个顶点,因此,TE和U是两个动态的集合,这一点在理解算法时要密切注意。

3:如果U=V,则算法结束;否则重复步骤2。

可以把本步骤看成循环终止条件。

我们可以算出当U=V时,步骤2共执行了n－1次(设n为图中顶点的数目),TE中也增加了n－1条边,这n－1条边就是需要求出的最小生成树的边。

最小生成树问题课程设计一、课程目标知识目标：1. 理解最小生成树的概念，掌握其定义及性质；2. 学会运用普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法求解最小生成树问题；3. 了解最小生成树在实际问题中的应用，如网络设计、电路设计等。

技能目标：1. 能够运用普里姆和克鲁斯卡尔算法解决最小生成树问题，并进行算法分析；2. 能够运用所学知识解决实际问题，具备一定的算法设计能力；3. 能够通过合作与交流，提高问题分析和解决问题的能力。

情感态度价值观目标：1. 培养学生对数据结构与算法的兴趣，激发学习热情；2. 培养学生的团队合作意识，学会倾听、尊重他人意见；3. 培养学生面对问题勇于挑战、积极进取的精神。

课程性质：本课程为计算机科学与技术专业的高年级课程，旨在帮助学生掌握图论中的最小生成树问题及其求解方法。

学生特点：学生具备一定的编程基础和图论知识，对算法有一定的了解，但可能对最小生成树问题尚不熟悉。

教学要求：结合学生特点，采用案例教学、任务驱动等方法，注重理论与实践相结合，培养学生的实际操作能力和创新思维。

通过本课程的学习，使学生能够将所学知识应用于实际问题中，提高解决复杂问题的能力。

二、教学内容1. 最小生成树概念与性质- 定义、性质及定理- 最小生成树的构建方法2. 普里姆算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用3. 克鲁斯卡尔算法- 算法原理与步骤- 算法实现与复杂度分析- 举例应用4. 最小生成树在实际问题中的应用- 网络设计- 电路设计- 其他领域应用案例5. 算法比较与优化- 普里姆与克鲁斯卡尔算法的比较- 算法优化方法及其适用场景6. 实践环节- 编程实现普里姆和克鲁斯卡尔算法- 分析并解决实际问题- 小组讨论与成果展示教学内容依据课程目标进行选择和组织，注重科学性和系统性。

参考教材相关章节，制定以下教学安排：第1周：最小生成树概念与性质第2周：普里姆算法第3周：克鲁斯卡尔算法第4周：最小生成树在实际问题中的应用第5周：算法比较与优化第6周：实践环节与总结三、教学方法本课程将采用以下多样化的教学方法，以激发学生的学习兴趣和主动性：1. 讲授法：教师通过生动的语言和形象的比喻，对最小生成树的概念、性质、算法原理等基础知识进行讲解，使学生快速掌握课程内容。

数据结构实验报告-最小生成树（精选5篇）第一篇：数据结构实验报告-最小生成树电子科技大学实验报告学生姓名：XXX 学号：20***指导教师：刘峤实验地点：信软楼306实验时间：5月17日一、实验室名称：软件实验室二、实验项目名称：数据结构与算法—图三、实验学时：4四、实验原理：Kruskal 算法是一种按照图中边的权值递增的顺序构造最小生成树的方法。

其基本思想是：设无向连通网为G＝（V，E），令G 的最小生成树为T，其初态为T＝（V，{}），即开始时，最小生成树T 由图G 中的n 个顶点构成，顶点之间没有一条边，这样T 中各顶点各自构成一个连通分量。

然后，按照边的权值由小到大的顺序，考察G 的边集E 中的各条边。

若被考察的边的两个顶点属于T 的两个不同的连通分量，则将此边作为最小生成树的边加入到T 中，同时把两个连通分量连接为一个连通分量；若被考察边的两个顶点属于同一个连通分量，则舍去此边，以免造成回路，如此下去，当T 中的连通分量个数为1 时，此连通分量便为G 的一棵最小生成树。

如教材153页的图4.21(a)所示，按照Kruskal 方法构造最小生成树的过程如图4.21 所示。

在构造过程中，按照网中边的权值由小到大的顺序，不断选取当前未被选取的边集中权值最小的边。

依据生成树的概念，n 个结点的生成树，有n－1 条边，故反复上述过程，直到选取了n－1 条边为止，就构成了一棵最小生成树。

五、实验目的：本实验通过实现最小生成树的算法，使学生理解图的数据结构存储表示，并能理解最小生成树Kruskal 算法。

通过练习，加强对算法的理解，提高编程能力。

六、实验内容：（1）假定每对顶点表示图的一条边，每条边对应一个权值；（2）输入每条边的顶点和权值；（3）输入每条边后，计算出最小生成树；（4）打印最小生成树边的顶点及权值。

七、实验器材（设备、元器件）：八、数据结构及程序#include #include #include typedefstruct {intvex;intgno;}TVex,*TpVex;typedefstruct {intvhead, vtail;intwght;intflag;}TEdge,*TpEdge;typedef struct{TpVex VexList;TpEdge EdgeList;int nvex, nedge;}TGraph, *TpGraph;void begin(TpGraph G){ int i;for(i=1;i<=G->nvex;i++){G->VexList[i-1].gno=i;G->EdgeList[i-1].flag=0;} } int findmin(TpGraph G){ int i,j;int minwght=G->EdgeList[0].wght;for(i=0,j=-1;inedge;i++){ PC机一台，装有C/C++语言集成开发环境。

最小生成树问题课程设计报告案场各岗位服务流程销售大厅服务岗：1、销售大厅服务岗岗位职责：1)为来访客户提供全程的休息区域及饮品;2)保持销售区域台面整洁;3)及时补足销售大厅物资,如糖果或杂志等;4)收集客户意见、建议及现场问题点；2、销售大厅服务岗工作及服务流程阶段工作及服务流程班前阶段1）自检仪容仪表以饱满的精神面貌进入工作区域2）检查使用工具及销售大厅物资情况，异常情况及时登记并报告上级。

班中工作程序服务流程行为规范迎接指引递阅资料上饮品（糕点）添加茶水工作要求1）眼神关注客人，当客人距3米距离时，应主动跨出自己的位置迎宾，然后侯客迎询问客户送客户注意事项15度鞠躬微笑问候：“您好！欢迎光临！”2）在客人前方1-2米距离领位，指引请客人向休息区，在客人入座后问客人对座位是否满意：“您好！请问坐这儿可以吗？”得到同意后为客人拉椅入座“好的，请入座！”3）若客人无置业顾问陪同，可询问：请问您有专属的置业顾问吗？，为客人取阅项目资料，并礼貌的告知请客人稍等，置业顾问会很快过来介绍，同时请置业顾问关注该客人；4）问候的起始语应为“先生-小姐-女士早上好，这里是XX销售中心，这边请”5）问候时间段为8:30-11:30 早上好11:30-14:30 中午好 14:30-18:00下午好6）关注客人物品，如物品较多，则主动询问是否需要帮助（如拾到物品须两名人员在场方能打开，提示客人注意贵重物品）；7）在满座位的情况下，须先向客人致歉，在请其到沙盘区进行观摩稍作等待；阶段工作及服务流程班中工作程序工作要求注意事项饮料（糕点服务）1）在所有饮料（糕点）服务中必须使用托盘；2）所有饮料服务均已“对不起，打扰一下，请问您需要什么饮品”为起始；3）服务方向：从客人的右面服务；4）当客人的饮料杯中只剩三分之一时，必须询问客人是否需要再添一杯，在二次服务中特别注意瓶口绝对不可以与客人使用的杯子接触；5）在客人再次需要饮料时必须更换杯子；下班程序1）检查使用的工具及销售案场物资情况，异常情况及时记录并报告上级领导；2）填写物资领用申请表并整理客户意见；3）参加班后总结会；4）积极配合销售人员的接待工作，如果下班时间已经到，必须待客人离开后下班；1.3.3.3吧台服务岗1.3.3.3.1吧台服务岗岗位职责1）为来访的客人提供全程的休息及饮品服务；2）保持吧台区域的整洁；3)饮品使用的器皿必须消毒；4）及时补充吧台物资；5）收集客户意见、建议及问题点；1.3.3.3.2吧台服务岗工作及流程阶段工作及服务流程班前阶段1）自检仪容仪表以饱满的精神面貌进入工作区域2）检查使用工具及销售大厅物资情况，异常情况及时登记并报告上级。

兰州商学院陇桥学院工学系课程设计报告设计题目：最小生成树系别：专业 (方向)：年级、班：学生姓名：学生学号：指导教师：年月日目录一、系统开发的背景 (1)二、系统分析与设计 (1)（一）系统功能要求 (1)（二）系统模块结构设计 (1)三、系统的设计与实现 (2)(一)输入城市信息：CREATE () (2)（二）判断是否能够生成最小生成树：JUDGE( ) (2)（三）求最小生成树：KRUSKAL( ) (3)四、系统测试 (4)（一）测试INT MENU ()函数 (4)（二）测试VOID CREATE ()函数 (4)（三）测试VOID JUDGE()函数 (5)（四）测试VOID K RUSKAL()函数 (5)（五）测试EXIT()函数 (5)五、总结 (6)六、附件（代码、图表） (6)最小生成树一、系统开发的背景为了在保证连通即可的n个城市之间建设网络，求出最经济的架设方法，因此设计了这个程序。

二、系统分析与设计（一）系统功能要求可以对给定的网和起点，用PRIM算法和kruskal算法的基本思想求解出所有的最小生成树。

存储结构可自行选择；（二）系统模块结构设计通过对系统功能的分析，最小生成树功能如图1所示。

图1 最小生成树功能图通过上图的功能分析，把整个系统划分为4个模块：1、输入城市信息，该模块主要实现：输入城市的个数以及输入城市之间的邻接矩阵，借助函数create( )来实现；2、判断是否生成模块，该模块主要实现判断是否能够生成最小生成树，借助函数judge ( )来实现；3、求最小生成树模块，该模块主要实现显示所输入城市之间各路段的权值，求出最小生成树，借助函数Kruskal( )来实现；4、退出模块，该模块主要实现终止正在执行的程序，借助函数exit( )来实现；三、系统的设计与实现(一)输入城市信息：create ( )分析：首先输入城市的基本信息。

该模块的具体代码如下所示：void create(){int i,j;printf("请输入城市的个数:\n");scanf("%d",&n);printf("输入%d个城市的邻接矩阵:\n",n);for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d",&arcs[i][j]);}}（二）判断是否能够生成最小生成树：judge( )该模块的具体代码如下所示：void judge(){ int close[100],low[100],i,j,ans=0;int use[100];use[1]=1;for(i=2;i<=n;i++){low[i]=arcs[1][i];close[i]=1;use[i]=0;}for(i=1;i<n;i++){ int min=100000000,k=0;for(j=2;j<=n;j++){if(use[j]==0&&min>low[j]){ min=low[j];k=j;}}for(j=2;j<=n;j++){ if(use[j]==0&&low[j]>arcs[k][j]){low[j]=arcs[k][j];close[j]=k;}}ans+=arcs[close[k]][k];}if(ans>=100000000)printf("不能构成最小生成树\n");elseprintf("能构成最小生成树\n");}（三）求最小生成树：Kruskal( )该模块的具体代码如下所示：void Kruskal(){ int ans=0,i,j,k=0;int index;int count=0;for(i=1;i<=n;i++)set(i);for(i=1;i<=n;i++){for(j=i+1;j<=n;j++){ p[++k].str=i;p[k].end=j;p[k].dis=arcs[i][j];}}for(i=1;i<=k;i++){ index=i;for(j=i+1;j<=k;j++)if(p[j].dis <p[index].dis)index=j;temp=p[index];p[index]=p[i];p[i]=temp;}for(i=1;i<=k;i++){if(find(p[i].str)!=find(p[i].end)){printf("\t第%d条路段为：%d - %d,权值是%d\n",++count,p[i].str,p[i].end,p[i].dis);ans+=p[i].dis;Union(p[i].str,p[i].end);}}printf("\t遍历所有城市得到最小生成树的代价为: %d\n\n",ans);}四、系统测试（一）测试int menu ( )函数测试该函数使用的测试方法，测试的具体步骤，测试用例的选取，测试的结果。

《数据结构》课程设计报告课程名称：最小生成树课题负责人名（学号）:同组成员名单（角色）：指导教师：评阅成绩：评阅意见：提交报告时间：2011年12月19日最小生成树计算机科学与技术专业学生：指导老师：[摘要]选择一颗生成树，使之总的消费最少，也就是要构造连通网的最小代价生成树（简称为最小生成树）的问题，一颗生成树的代价就是树上各边的代价之和，构造最小生成树可以有多种算法，其中多数算法利用了MST的性质。

关键词：最小生成树连通图普里姆算法克鲁斯卡尔算法 MST一、设计目的1.了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3.提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4.训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。

二、算法思想分析该设计的要求是在n个城市之间建设网络，不仅要保证连通，还要求是最经济的架设方法。

根据克鲁斯卡尔和普里姆算法的不同之处，该程序将城市个数大于十个时应用普里姆算法求最小生成树，而城市个数小于十个时则应用克鲁斯卡尔进行计算。

1.算法思想1)普里姆（Prim）算法思想a)选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；b)在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；c)重复b)直到所有的节点出列。

2)克鲁斯卡尔（Kruskal）算法思想为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。

具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。

##大学数据结构课程设计报告题目：图的最小生成树院（系）：学生姓名:班级：学号:起迄日期:指导教师:2011—2012年度第 2 学期一、需求分析1.问题描述：设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

存储结构采用多种。

求解算法多种。

该题目需要运用最小生成树来解决。

最小生成树的代价之和最小，所以是一种最经济的架设方法。

2.基本功能该程序是解决城市间架设网络问题的，采用邻接表与邻接矩阵对构造的图进行存储，用普利姆与克鲁斯卡尔算法进行求解。

3.输入输出首先输入顶点的个数以及边的个数，格式如:4 6。

然后输入边的权值，格式如：a b 1。

输出分为四种输出，输出邻接表，邻接矩阵，普利姆算法求得的最小生成树，克鲁斯卡尔求得的最小生成树。

最小生成树的格式为：<顶点名顶点名>权值。

二、概要设计1.设计思路：问题的解决分别采用普利姆算法已经克鲁斯卡尔算法。

1）普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。

然后选择该顶点与V中顶点之间权值最小的一条边，依此类推，如果到达最后一个则返回上一个顶点。

2）克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，依此类推，最终要有个判断是是否生成环，不生成则得到克鲁斯卡尔的最小生成树。

2.数据结构设计：1.抽象数据类型如下：ADT Graph{ 数据对象 V：v是具有相同特征的数据元素的集合，称为顶点集。

数据关系 R：R={VR}VR={<v,w>|v,w属于v且p（v,w）表示从v到w的弧，谓词p（v,w）定义了弧<v,w>的意义或信息}基本操作：1)GreatGraph（&G,V,VR）；初始条件：V是图的顶点集，VR是图中弧的集合。

操作条件：按V和VR的定义构造图G。

2）LocateVex（G,u）；初始条件：图G存在，u和G中顶点有相同的特征。

操作条件：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。

数据结构课程设计学院专业班级姓名学号指导教师2011 年x 月x 日一．需求分析1.可以用连通网来表示n个城市间可能设置的通信网络，其中网的顶点表示城市，边表示两城市之间的路线，边的权值表示相应的费用。

对于n个顶点的连通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。

现在，我们要选择这样一棵生成树，它使总的费用最少，这棵树就是最小生成树。

一棵生成树的费用就是树上各边的费用之和。

2.本程序的目的是要建设一个最经济的通信网，根据用户输入的网，输出相应的最小生成树。

在这里城市以及两城市之间的费用都用整型数来代替。

3．程序执行的命令包括：（1）利用克鲁斯卡尔算法求最小生成树。

（2）构造最小生成树中的连通分量。

（3）权值应存放在定义的数组中。

（4）输入城市个数。

（5）用堆排序找出权值最小的边。

（6）输出费用最少的生成树并将数据存放在文本文档中。

（7）结束。

4．测试数据用户自定义输入城市个数即图的顶点数及边数，输入结束后回车即显示生成的最小生成树及最小开销。

二．概要设计1：抽象数据类型MFSet的定义：ADT MFSet {数据对象：若设S是MFSet型的集合，则它由n(n>0)个子集Si（i = 1,2...,n）构成，每个子集的成员代表在这个子集中的城市。

数据关系： S1 U S2 U S3 U... U Sn = S, Si包含于S（i = 1,2,...n）Init (n): 初始化集合，构造n个集合，每个集合都是单成员，根是其本身。

rank 数组初始化0Find(x):查找x所在集合的代表元素。

即查找根，确定x所在的集合，并路径压缩。

Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。

}2：主程序：int main(){初始化；while (条件){接受命令;处理命令;}return 0;}3：抽象数据类型图的定义如下：ADT Graph{数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。

实验五最小生成树一、需求分析1、本程序的目的是要建设一个最经济的网，，输出相应的最小生成树。

在这里都用整型数来代替。

2、测试数据见下程序。

二、概要设计主程序：int main(){初始化；while (条件){接受命令;处理命令;}return 0;}三、详细设计#include<iostream>//头文件using namespace std;#define MAX_VERTEX_NUM 20//最大结点数#define MAX 200typedef struct Close//结构体{char adjvex;int lowcost;}Close,close[MAX_VERTEX_NUM];typedef struct ArcNode{int adjvex;ArcNode *nextarc;int info;}ArcNode;typedef struct VNode{char data;ArcNode *firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedef struct{AdjList verties;int vexnum,arcnum;}ALGraph;ALGraph G;//对象Gint LocateVek(ALGraph ,char );//返回结点位置int minimum(close);//返回最小数void MinSpanTree_PRIM(ALGraph,char);//最小生成树void Create(ALGraph &);//创建邻接表int main(){char a;int i=1;Create(G);/*for(int i=1;i<=G.vexnum;i++){for(s=G.verties[i].firstarc;s!=NULL;s=s->nextarc)cout<<G.verties[i].data<<"---"<<G.verties[s->adjvex].data<<"===="<<s->info<<endl; }*/while(i){cout<<"输入起点 : ";cin>>a;MinSpanTree_PRIM(G,a);cout<<"如果结束输入'0',否则输入'1':";cin>>i;}return 0;}int LocateVek(ALGraph G,char u){int i;for(i=1;i<=G.vexnum;i++)if(u==G.verties[i].data)return i;return -1;}int minimum(close m)//返回最小数{int i=0,j,n=200;for(i=1;i<=G.vexnum;i++)if(m[i].lowcost<n&&m[i].lowcost!=0){n=m[i].lowcost;j=i;}return j;}void MinSpanTree_PRIM(ALGraph G,char u){int j,k,a;close closedge;ArcNode *s,*p,*q;for(j=1;j<=MAX_VERTEX_NUM;j++)closedge[j].lowcost=MAX;//把所有值都赋为最大k=LocateVek(G,u);for(j=1;j<=G.vexnum;j++)if(j!=k){closedge[j].adjvex=u;for(s=G.verties[k].firstarc;s!=NULL;s=s->nextarc)if(j==s->adjvex){closedge[j].lowcost=s->info;break;}}closedge[k].lowcost=0;cout<<"最小生成树 : "<<"{";//查找并输出最小生成树for(j=1;j<G.vexnum;j++){k=minimum(closedge);cout<<"("<<closedge[k].adjvex<<","<<G.verties[k].data<<")";closedge[k].lowcost=0;for(int i=1;i<=G.vexnum;i++){for(p=G.verties[k].firstarc;p!=NULL;p=p->nextarc)if(p->info<closedge[i].lowcost&&i==p->adjvex){closedge[i].adjvex=G.verties[k].data;closedge[i].lowcost=p->info;}}}cout<<"}"<<endl;cout<<"边及对应权值: "<<endl;//输出边及对应权值for(j=G.vexnum;j>=1;j--){if(closedge[j].lowcost==0&&G.verties[j].data!=u){ cout<<"("<<closedge[j].adjvex<<","<<G.verties[j].data<<") ==";a=closedge[j].adjvex;for(q=G.verties[j].firstarc;q!=NULL;q=q->nextarc)if(a-64==q->adjvex)cout<<q->info<<endl;}}}void Create(ALGraph &G){int i,j,k,x;char a,b;ArcNode *s;cout<<"输入顶点数(1-20):";cin>>G.vexnum;cout<<"输入边数:";cin>>G.arcnum;cout<<"输入顶点信息:"<<endl;for(i=1;i<=G.vexnum;i++){cin>>G.verties[i].data;G.verties[i].firstarc=NULL;}for(i=1;i<=G.arcnum;i++){cout<<"输入相邻两结点和权值 ";cin>>a>>b;cin>>x;j=a-64;k=b-64;//将字符型转化成整数型s=new ArcNode;s->info=x;s->adjvex=k;s->nextarc=G.verties[j].firstarc;G.verties[j].firstarc=s;s=new ArcNode;s->info=x;s->adjvex=j;s->nextarc=G.verties[k].firstarc;G.verties[k].firstarc=s;}}四、调试分析1、在写程序时遇到很多有关专业名词的C语言编译，没有完全套用书上的固有解释，而是按照自己有限的英语词汇的理解去编译的。

数据结构实验最小生成树数据结构实验报告最小生成树问题一、问题描述:若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。

如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题基本要求(1)从文件中读入图的信息。

(2)利用克鲁斯卡尔算法求网的最小生成树。

(3)以文本形式生成树中各条边以及他们的权值。

二(需求分析:1、需定义结构体数组，根据权值逐一选择边。

三(概要设计抽象数据类型:需定义结构体数组，存储每条边的起点，终点，权值。

算法的基本思想:1、图的信息的读取:定义结构体数组，存储每条边的起点，终点，权值。

2、对每条边在数组中的位置处理:选边需从最小的开始，故按边的权值从小到大进行排序。

3、边的选取: 从最小的边的开始，若边的两端点不属于同一集合，则选取该边。

并将该边的两个顶点所在的两个集合合并成为一个。

因为有n个顶点，故只需选取n-1条边。

程序的流程:(1) 输入模块: 读入图的信息(顶点和边，用结构体数组进行存储)。

(2) 处理模块:Kruskal算法。

(3) 输出模块:将结果输出。

四(详细设计:算法的具体步骤:struct G{int fromvex;int endvex;int weight;}GE[100],cur[100];void swap(G* GE,int i,int j){ //交换函数int temp=GE[i].fromvex;GE[i].fromvex=GE[j].fromvex;GE[j].fromvex=temp;temp=GE[i].endvex;GE[i].endvex=GE[j].endvex;GE[j].endvex=temp;temp=GE[i].weight;GE[i].weight=GE[j].weight;GE[j].weight=temp;}void Kruskal(int n){int i,j,k=0,pos=-1,m1,m2;bool** s=new bool *[n];//定义一个二维数组，用来判断是否为同一类for(i=0;i<n;i++)s[i]=new bool[n];for(i=0;i<n;i++){for(j=0;j<n;j++){if(i==j)s[i][j]=true; //初始化数组elses[i][j]=false;}}while(k<n-1){for(i=0;i<n;i++){if(s[i][GE[k].fromvex]==1)m1=i;if(s[i][GE[k].endvex]==1)m2=i;}if(m1!=m2){//判断是否为同一类,如果为同一类(该类中所有的点到起点和终//点的边在s 数组中赋为1)，cur[++pos].fromvex=GE[k].fromvex;cur[pos].endvex=GE[k].endvex;cur[pos].weight=GE[k].weight;for(i=0;i<n;i++){if(s[m1][i] || s[m2][i])//把该点添加到该类，并和并两个类s[m1][i]=1;elses[m1][i]=0;s[m2][i]=0;}}k++;}for(i=0;i<n;i++){delete []s[i];}}int main(){int i,j;int numVertex,numEdge;cout<<"请输入点的个数和边的条数:"<<endl; cin>>numVertex>>numEdge;cout<<"请输入边的起始位置和边的权值:"<<endl;for(i=0;i<numEdge;i++)cin>>GE[i].fromvex>>GE[i].endvex>>GE[i].weight;for(i=0;i<numEdge;i++)for(j=i;j<numEdge;j++){if(GE[j].weight<GE[i].weight)//将边的权值按从小到大排列swap(GE,i,j);}Kruskal(numEdge);for(i=0;i<numVertex-1;i++) cout<<cur[i].fromvex<<"->"<<cur[i].endvex<<":"<<cur[i].weight<<endl;system("pause");return 0;}五(调试分析:将选边的过程输出来检验算法的正确性。

数据结构课程设计报告题目：最小生成树问题院（系）：计算机工程学院学生姓名: XXX班级： XXX 学号: XXXXXXXXX起迄日期: 2015.07.13-2015.07.24指导教师: XXX XXX任务书最小生成树问题[问题描述]在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。

[设计要求]（1）通过输入建立一无向网，存储结构可以采用多种；（2）要求分别采用普里姆算法和克鲁斯卡尔算法实现；（3）若以图形界面输出可以适当加分。

一、需求分析1.问题描述：该程序主要实现最小生成树功能，在给定的中国铁路网中，选择城市，生成最小生成树。

此外，改程序实现了城市介绍，指定城市到其它城市的最短距离，指定城市之间的最短距离等图论的基本操作。

直观、清晰的为用户提供全国铁路网的最基本情况。

该程序最具体的任务是最小生成树的实现，需要用到Prim算法和Kruskal算法实现。

输入指定的城市求出最小生成树，方便查询城市间的最短连通量。

另外添加了显示全国主要铁路网的功能，在跳出的界面，选择城市，程序会通过textBox控件显示选定的城市的相关介绍。

该程序实现了指定城市到其它城市之间的最短距离。

通过在地图上选择城市，程序通过Dijkstra算法计算出指定城市到其它城市之间的最短距离，并通过textBox控件显示，一目了然。

具有较强的人机和谐性。

还可以实现指定城市之间的最短路，输入两个指定的城市，通过Floyd算法求出选定城市间的最短距离。

并在图形界面上标注要经过的城市。

2.基本功能：（1）通过输入建立一无向网，存储结构采用了邻接矩阵。

（2）要求分别采用Prim算法和Kruskal算法实现，分别对应Prim.cs和Kruskal.cs。

（3）若以图形界面输出会适当加分。

3.附加功能：（1）城市的介绍，在输出的全国铁路网中，点击相应的城市会出现对该城市相应的介绍。

主要实现代码在Map.cs中。

（2）指定城市到其它城市的最短距离，在地图上点击指定城市，程序会显示指定城市到其它城市的最短距离。

课程设计报告课程设计名称：数据结构课程设计课程设计题目：最小生成树研究院(系)：专业：班级：学号：姓名：指导教师：完成日期：目录第 1 章概要设计 ....................................................................1.1题目介绍.........................................................................1.2功能要求.........................................................................1.3总体结构.........................................................................第 2 章详细设计 ....................................................................2.1 主函数的流程图 ................................................................. 2.2 权值位置判断流程图 .............................................................2.3创建邻接矩阵流程图 .............................................................2.4 最小生成树流程图................................................................ 第 3 章调试分析 ....................................................................第 4 章使用说明 ....................................................................参考文献 ............................................................................附录(程序清单) .................................................................第 1 章概要设计1.1题目介绍若要在 n 个城市之间建设通讯网络，只需要架设 n-1条路线即可。