最小生成树问题
榆林学院12届课程设计
《最小生成树问题》
课程设计说明书
学生姓名：赵佳
学号：1412210112
院系：信息工程学院
专业：计算机科学与技术
班级：计14本1
指导教师：
答辩时间：年月日
最小生成树问题
一、问题陈述
最小生成树问题
设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。
二、需求分析
1.在n个城市之间建设网络，只需保证连通即可。
2.求城市之间最经济的架设方法。
3.采用多种存储结构，求解算法也采用多种。
三、概要设计
1、功能模块图
2、功能描述
（1) CreateUDG()
创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。
（2) Switch()
功能选择：给用户提示信息，让用户选择相应功能。
（3) Adjacency_Matrix()
建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。
（4) Adjacency_List()
建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。
（5) MiniSpanTree_KRSL()
kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。
（6) MiniSpanTree_PRIM()
PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。
四、详细设计
本次课程设计采用两种存储结构以及两种求解算法。
1、两种存储结构的存储定义如下：
typedef struct Arcell
{
double adj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX_VERTEX_NUM]; //节点数组
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前节点数和弧数
}MGraph;
typedef struct Pnode //用于普利姆算法
{ char adjvex; //节点
double lowcost; //权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
char ch1; //节点1
char ch2; //节点2
double value;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
2、求解算法采用Prim算法和Kruskal算法。
（1）普里姆算法(Prim)算法
普里姆算法(Prim)算法是一种构造性算法，生成最小生成树的步骤如下：初始化U={v}。以v到其他顶点的所有边为候选边。
重复一下步骤(n-1)次，使得其他(n-1)个顶点被加入到U中。
○1从候选边中挑选权值最小的边加入TE，设该边在V—U中的顶点是vk，将顶点vk加入到U中;
○2考察当前V—U中的所有顶点vj ，修改候选边：若(vk,vj)的权值小于原来和vj关联的候选边，则用(vk,vj)取代后者作为候选边。
（2）克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔(Kruskal)算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。假设G=(V,E)是一个具有n个顶点的带权连通无向图，T=(U,TE)是G的最小生成树，则构造最小生成树的步骤如下：
置U的初值等于V（即包含有G中的全部顶点），TE的初值为空集（即图T 中每一个顶点都构成一个分量）。
将图G中的边按权值从小到大的顺序依次选取：若选取的边未使生成树T 形成回路，则加入TE，否则舍弃，直到TE中包含(n-1)条边为止。
3、使用的函数
int CreateUDG(MGraph & G,Dgevalue & dgevalue); int LocateVex(MGraph G,char ch);
int Minimum(MGraph G,Closedge closedge);
void MiniSpanTree_PRIM(MGraph G,char u);
void Sortdge(Dgevalue & dgevalue,MGraph G); void Adjacency_Matrix(MGraph G);
void Adjacency_List(MGraph G,Dgevalue dgevalue);
函数之间的调用关系图：
五、程序代码
#include
#include
#include
#define MAX_VERTEX_NUM 20
#define OK 1
#define ERROR 0
#define MAX 1000
typedef struct Arcell
{
double adj;
}Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
char vexs[MAX_VERTEX_NUM]; //节点数组
AdjMatrix arcs; //邻接矩阵
int vexnum,arcnum; //图的当前节点数和弧数
}MGraph;
typedef struct Pnode //用于普利姆算法
{
char adjvex; //节点
double lowcost; //权值
}Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的辅助数组定义
typedef struct Knode//用于克鲁斯卡尔算法中存储一条边及其对应的2个节点
{
char ch1; //节点1
char ch2; //节点2
double value;//权值
}Knode,Dgevalue[MAX_VERTEX_NUM];
int CreateUDG(MGraph & G,Dgevalue & dgevalue);
int LocateVex(MGraph G,char ch);
int Minimum(MGraph G,Closedge closedge);
void MiniSpanTree_PRIM(MGraph G,char u);
void Sortdge(Dgevalue & dgevalue,MGraph G);
void Adjacency_Matrix(MGraph G);
void Adjacency_List(MGraph G,Dgevalue dgevalue);
int CreateUDG(MGraph & G,Dgevalue & dgevalue)//构造无向加权图的邻接矩阵
{
int i,j,k;
cout<<"请输入城市个数及其之间的可连接线路数目：";
cin>>G.vexnum>>G.arcnum;
cout<<"请输入各个城市名称(分别用一个字符代替)：";
for(i=0;i cin>>G.vexs[i]; for(i=0;i for(j=0;j { G.arcs[i][j].adj=MAX; } cout<<"请输入两个城市名称及其连接费用(严禁连接重复输入!)："< for(k=0;k { cin >> dgevalue[k].ch1 >> dgevalue[k].ch2 >> dgevalue[k].value; i = LocateVex(G,dgevalue[k].ch1); j = LocateVex(G,dgevalue[k].ch2); G.arcs[i][j].adj = dgevalue[k].value; G.arcs[j][i].adj = G.arcs[i][j].adj; } return OK; } int LocateVex(MGraph G,char ch) //确定节点ch在图G.vexs中的位置{ int a ; for(int i=0; i if(G.vexs[i] == ch) a=i; return a; } void Adjacency_Matrix(MGraph G) //用邻接矩阵存储数据 { int i,j; for(i=0; i { for(j=0; j if(G.arcs[i][j].adj==MAX) cout<<0<<" "; else cout< cout< } } void Adjacency_List(MGraph G,Dgevalue dgevalue) //用邻接表储存数据{ int i,j; for(i=0;i { cout< for(j=0;j if(dgevalue[j].ch1==G.vexs[i]&&dgevalue[j].ch2!=G.vexs[i]) cout< else if(dgevalue[j].ch1!=G.vexs[i]&&dgevalue[j].ch2==G.vexs[i]) cout< cout<<"\b\b "< } } void MiniSpanTree_KRSL(MGraph G,Dgevalue & dgevalue)//克鲁斯卡尔算法求最小生成树 { int p1,p2,i,j; int bj[MAX_VERTEX_NUM]; //标记数组 for(i=0; i bj[i]=i; Sortdge(dgevalue,G);//将所有权值按从小到大排序 for(i=0; i { p1 = bj[LocateVex(G,dgevalue[i].ch1)]; p2 = bj[LocateVex(G,dgevalue[i].ch2)]; if(p1 != p2) { cout<<" 城市"< for(j=0; j { if(bj[j] == p2) bj[j] = p1; } } } } void Sortdge(Dgevalue & dgevalue,MGraph G)//对dgevalue中各元素按权值按从小到大排序 { int i,j; double temp; char ch1,ch2; for(i=0; i { for(j=i; j { if(dgevalue[i].value > dgevalue[j].value) { temp = dgevalue[i].value; dgevalue[i].value = dgevalue[j].value; dgevalue[j].value = temp; ch1 = dgevalue[i].ch1; dgevalue[i].ch1 = dgevalue[j].ch1; dgevalue[j].ch1 = ch1; ch2 = dgevalue[i].ch2; dgevalue[i].ch2 = dgevalue[j].ch2; dgevalue[j].ch2 = ch2; } } } } void MiniSpanTree_PRIM(MGraph G,char u)//普里姆算法求最小生成树 { int i,j,k; Closedge closedge; k = LocateVex(G,u); for(j=0; j { if(j != k) { closedge[j].adjvex = u; closedge[j].lowcost = G.arcs[k][j].adj; } } closedge[k].lowcost = 0; for(i=1; i { k = Minimum(G,closedge); cout<<" 城市"< closedge[k].lowcost = 0; for(j=0; j { if(G.arcs[k][j].adj < closedge[j].lowcost) { closedge[j].adjvex = G.vexs[k]; closedge[j].lowcost= G.arcs[k][j].adj; } } } } int Minimum(MGraph G,Closedge closedge) //求closedge中权值最小的边，并返回其顶点在vexs中的位置 { int i,j; double k = 1000; for(i=0; i { if(closedge[i].lowcost != 0 && closedge[i].lowcost < k) { k = closedge[i].lowcost; j = i; } } return j; } void main() { MGraph G; Dgevalue dgevalue; CreateUDG(G,dgevalue); char u; cout<<"图创建成功。"; cout<<"请根据如下菜单选择操作。\n"; cout<<"1、用邻接矩阵存储："< cout<<"2、用邻接表存储："< cout<<"3、克鲁斯卡尔算法求最经济的连接方案"< int s; char y='y'; while(y='y') { cout<<"请选择菜单："< cin>>s; switch(s) { case 1: cout<<"用邻接矩阵存储为："< Adjacency_Matrix(G); break; case 2: cout<<"用邻接表存储为："< Adjacency_List(G,dgevalue); break; case 3: cout<<"克鲁斯卡尔算法最经济的连接方案为:"< break; case 4: cout<<"普里姆算法最经济的连接方案为:"< cout<<"请输入起始城市名称："; cin>>u; MiniSpanTree_PRIM(G,u); break; default: cout<<"输入有误!"; break; } cout< cin>>y; if(y=='n') break; } } 六、运行结果与测试 七、设计体会与总结 通过本次课程设计，我在程序设计中，用邻接矩阵和邻接表这两种存储结构进行编程，且对Prim算法和Kruskal算法生成最小生成树有了一个初步的了解， 同时也为日后的毕业设计打下了良好的基础。而且通过课程设计在下述各方面得到了锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 在本次课程设计中，知道如何在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。并且用了多种求解方式。 这几天的课程设计让我充分地体会到了上机实践对于计算机编程的重要性。 只顾学习理论是远远不够的。实践中可以发现许许多多的问题，然后通过同学老师的帮助，得以解决，让自己的编程能力得到极大的提升。 实验五 实验名称： 得到最小生成树 实验目的： 1.熟悉地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。 2.掌握图论中的最小生成树及Prim 和 Kruskal 算法等，进一步能用它们来解决实际问题。 实验内容： 输入一个图的权矩阵，得到该图的生成树，用Kruskal算法的最小生成树，用Prim算法的最小生成树。 Kruskal算法 假设T中的边和顶点均涂成红色，其余边为白色。开始时G中的边均为白色。 1）将所有顶点涂成红色； 2）在白色边中，挑选一条权最小的边，使其与红色边不形成圈，将该白色边涂红； 3）重复2）直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。 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条边就是需要求出的最小生成树的边。 榆林学院12届课程设计 《最小生成树问题》 课程设计说明书 学生姓名：赵佳 学号： 1412210112 院系：信息工程学院 专业：计算机科学与技术 班级：计14本1 指导教师： 答辩时间：年月日 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方 法。存储结构采用多种。求解算法多种。 二、需求分析 1.在n个城市之间建设网络，只需保证连通即可。 2.求城市之间最经济的架设方法。 3.采用多种存储结构，求解算法也采用多种。 三、概要设计 1、功能模块图 2、功能描述 （1) CreateUDG() 创建一个图：通过给用户信息提示，让用户将城市信息及城市之间的联系关系和连接权值写入程序，并根据写入的数据创建成一个图。 （2) Switch() 功能选择：给用户提示信息，让用户选择相应功能。 （3) Adjacency_Matrix() 建立邻接矩阵：将用户输入的数据整理成邻接矩阵并显现在屏幕上。 （4) Adjacency_List() 建立邻接表：将用户输入的数据整理成临接表并显现在屏幕上。 （5) MiniSpanTree_KRSL() kruskal算法：利用kruskal算法求出图的最小生成树，即：城市之间最经济的连接方案。 （6) MiniSpanTree_PRIM() PRIM算法：利用PRIM算法求出图的最小生成树，即：城市之间最经济的连接方案。 四、详细设计 本次课程设计采用两种存储结构以及两种求解算法。 1、两种存储结构的存储定义如下： typedef struct Arcell { double adj; }Arcell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct { char vexs[MAX_VERTEX_NUM]; //节点数组 AdjMatrix arcs; //邻接矩阵 int vexnum,arcnum; //图的当前节点数和弧数 }MGraph; typedef struct Pnode //用于普利姆算法 { char adjvex; //节点 double lowcost; //权值 }Pnode,Closedge[MAX_VERTEX_NUM];//记录顶点集U到V-U的代价最小的边的 目录 1.需求分析 (2) 1.1 设计题目 (2) 1.2 设计任务及要求 (2) 1.3课程设计思想 (2) 1.4 程序运行流程 (2) 1.5软硬件运行环境及开发工具 (2) 2.概要设计 (2) 2.1流程图 (2) 2.2抽象数据类型MFSet的定义 (3) 2.3主程序 (4) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (5) 3.详细设计 (7) 3.1程序 (7) 4.调试与操作说明 (10) 4.1测试结果 (10) 4.2调试分析 (11) 5.课程设计总结与体会 (11) 5.1总结 (11) 5.2体会 (11) 6. 致谢 (12) 7. 参考文献 (12) 1.需求分析 1.1 设计题目：最小生成树 1.2 设计任务及要求：任意创建一个图，利用克鲁斯卡尔算法，求出该图的最小生成树。 1.3 课程设计思想：Kruskal算法采用了最短边策略(设G=(V,E)是一个无向连通网，令T=(U，TE)是G的最小生成树。最短边策略从TE={}开始，每一次贪心选择都是在边集E中选择最短边(u,v)，如果边(u,v)加入集合TE中不产生回路，则将边(u,v)加入边集TE中，并将它在集合E中删去。)，它使生成树以一种任意的方式生长，先让森林中的树木随意生长，每生长一次就将两棵树合并，最后合并成一棵树。 1.4程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出； 1.5 软硬件运行环境及开发工具：VC 2.概要设计 2.1流程图 图1流程图 2.2抽象数据类型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 数组初始化0 Find(x):查找x所在集合的代表元素。即查找根，确定x所在的集合，并路径压缩。 Merge(x, y):检查x与y是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 } 数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (1) 三．概要设计 (1) 1、功能模块图 (1) 2、各个模块详细的功能描述 (2) 四．详细设计 (3) 1．主函数和其他函数的伪码算法 (3) 2、主要函数的程序流程图 (7) 3、函数之间的调用关系图 (15) 五．测试数据及运行结果 (15) 1．正常测试数据及运行结果 (16) 2、非正常测试数据及运行结果 (17) 六．调试情况，设计技巧及体会 (18) 七．参考文献 (19) 八．附录：源代码 (19) 一. 设计目的 课程设计是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。能够在设计中逐步提高程序设计能力，培养科学的软件工作方法。而且通过数据结构课程设计能够在下述各方面得到锻炼： 1、能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2、提高程序设计和调试能力。通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3、培养算法分析能力。分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。 二. 设计内容 最小生成树问题: 设计要求：在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 三．概要设计 1、功能模块图 荆楚理工学院 课程设计成果 学院:_______计算机工程学院__________ 班级: 14计算机科学与技术一班 学生姓名: 志杰学号: 2014407020137 设计地点（单位）_____B5101_________ ____________ 设计题目:克鲁斯卡尔算法求最小生成树__________________________________ 完成日期：2015年1月6日 指导教师评语: ______________ _________________________ ___________________________________________________________________________________ ___________________________________________________________________________________________ ___________________________ __________ _ 成绩(五级记分制):_____ _ __________ 教师签名:__________ _______________ 注：介于A和C之间为B级，低于C为D级和E级。按各项指标打分后，总分在90～100为优，80～89为良，70～79为中，60～69为及格，60分以下为不及格。 目录 1 需求分析 (1) 1.1系统目标 (1) 1.2主体功能 (1) 1.3开发环境 (1) 2 概要设计 (1) 2.1功能模块划分 (1) 2.2 系统流程图 (2) 3 详细设计 (3) 3.1 数据结构 (3) 3.2 模块设计 (3) 4测试 (3) 4.1 测试数据 (3) 4.2测试分析 (4) 5总结与体会 (6) 5.1总结： (6) 5.2体会： (6) 参考文献 (7) 附录全部代码 (8) 数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 2011—2012年度第 2 学期 一、需求分析 1.问题描述： 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 2.基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 3.输入输出 以文本形式输出最小生成树，同时输出它们的权值。通过人机对话方式即用户通过自行选择命令来输入数据和生成相应的数据结果。 二、概要设计 1.设计思路： 因为是最小生成树问题，所以采用了课本上介绍过的克鲁斯卡尔算法和 prim算法两种方法来生成最小生成树。根据要求，需采用多种存储结构，所以我选择采用了邻接表和邻接矩阵两种存储结构。 2.数据结构设计： 图状结构： ADT Graph{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={ 初始条件：图G存在。 操作结果：销毁图G。 LocateVex( G, u ) 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返 回其它信息。 GetVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex( &G, v, value ) 初始条件：图G存在，v是G中某个顶点。 操作结果：对v赋值value。 FirstAdjVex( G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻接顶点， 则返回“空”。 NextAdjVex( G, v, w ) 初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的 最后一个邻接点，则返回“空”。 InsertVex( &G, v ) 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex( &G, v ) 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc( &G, v, w ) 算法分析与设计实验报告第一次附加实验 附录： 完整代码（贪心法） //贪心算法最小生成树prim算法 #include cin>>c[i][j]; } } cout<<"Prim算法最小生成树选边次序如下："< #include { int u, v, w; }EG[5010]; bool cmp(eage a, eage b) //排序调用 { return a.w < b.w; } int Find(int x) //寻找根节点，判断是否在同一棵树中的依据 { if(parent[x] == -1) return x; return Find(parent[x]); } void Kruskal() //Kruskal算法，parent能够还原一棵生成树，或者森林{ memset(parent, -1, sizeof(parent)); sort(EG+1, EG+m+1, cmp); //按权值将边从小到大排序 ans = 0; for(int i = 1; i <= m; i++) //按权值从小到大选择边 { int t1 = Find(EG[i].u), t2 = Find(EG[i].v); if(t1 != t2) //若不在同一棵树种则选择该边，合并两棵树 { ans += EG[i].w; parent[t1] = t2; printf("最小生成树加入的边为:%d %d\n",EG[i].u,EG[i].v); } } } int main() { printf("输入顶点数和边数:"); while(~scanf("%d%d", &n,&m)) { for(int i = 1; i <= m; i++) scanf("%d%d%d", &EG[i].u, &EG[i].v, &EG[i].w); Kruskal(); printf("最小生成树权值之和为:%d\n", ans); } return 0; } 算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级2011 姓名XXX 学号 2013年5 月19 日 题目：最小生成树问题的算法实现及复杂度分析 摘要：该程序操作简单，具有一定的应用性。数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。而最小生成树算法是算法设计与分析中的重要算法，最小生成树也是最短路径算法。最短路径的问题在现实生活中应用非常广泛，如邮递员送信、公路造价等问题。本设计以Visual Studio 2010作为开发平台，C/C++语言作为编程语言，以邻接矩阵作为存储结构，编程实现了最小生成树算法。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM 经典算法的算法思想，最后用这种经典算法实现了最小生成树的生成。 引言：假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n（n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。 沈阳航空航天大学 课程设计报告 课程设计名称：数据结构课程设计 课程设计题目：Prim算法求最小生成树 院（系）：计算机学院 专业：计算机科学与技术（物联网方向） 班级： 学号： 姓名： 指导教师： 学术诚信声明 本人声明：所呈交的报告（含电子版及数据文件）是我个人在导师指导下独立进行设计工作及取得的研究结果。尽我所知，除了文中特别加以标注或致谢中所罗列的内容以外，报告中不包含其他人己经发表或撰写过的研究结果，也不包含其它教育机构使用过的材料。与我一同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明并表示了谢意。报告资料及实验数据若有不实之处，本人愿意接受本教学环节“不及格”和“重修或重做”的评分结论并承担相关一切后果。 本人签名: 日期：2015 年 1 月15 日 沈阳航空航天大学 课程设计任务书 计算机科学与技术课程设计名称数据结构课程设计专业 （物联网方向） 学生姓名班级学号 题目名称Prim算法生成最小生成树 起止日期2015 年 1 月 5 日起至2015 年 1 月16 日止 课设内容和要求： 在n个城市之间建立网络，只需保证连通即可，求最经济的架设方法，利用Prim算法输出n个城市之间网络图，输出n个节点的最小生成树。其中，n个城市表示n个节点，两个城市间如果有路则用边连接，生成一个n个节点的边权树，要求键盘输入。 参考资料： 算法与数据结构，严蔚敏、吴伟民，清华大学出版社，2006 C程序设计，谭浩强，清华大学出版社，2010 教研室审核意见：教研室主任签字： 指导教师（签名）年月日 学生（签名）2015 年 1 月15 日 最小生成树模型与实验 第六章 最小生成树模型与实验 树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。 §6.1树与树的性质 上章已讨论了图和树的简单基本性质。为使更清楚明了，现在使用实例来说明。 例6.1 已知有五个城市，要在它们之 间架设电话线，要求任何两个城市都可以互相 通话（允许通过其它城市），并且电话线的根 数最少。 用五个点54321,,,,v v v v v 代表五个城市，如果 在某两个城市之间架设电话线，则在相应的两个点之间联一条边，这样一个电话线网就可以用一个图来表示。为了任何两个城市都可以通话，这样的图必须是连通的。其次，若图中有圈的话，从圈上任意去掉一条边，余下的图仍是连通的，这样可以省去一根电话线。因而，满足要求的电话线网所对应的图必定是不含圈的连通图。图6.1的表达式满足要求的一个电话线网。 定义6.1 一个无圈的连通图称为树. 例6.2 某大学的组织机构如下所示: v 5v 4v 图 教务处 研究处 校行政办公室 研究生院 财务科 行政科 理工学院 人事学院 外语学院 …… 如果用图表示，该工厂的组织机构图就是一个树。上章给出了一些树的性质，为使能进一步研究这部分知识，先再列出常用一些树和生成树的性质。 树的性质： （1） 树必连通，但无回路（圈）； （2） n 个顶点的树必有1-n 条边； （3） 树中任意两点间，恰有一条初等链； （4） 树连通，但去掉任一条边，必变为不连通； （5） 树无回路（圈），但不相邻顶点连一条边，恰得一回路（圈）。 生成树与最小树 定义6.2 设图),(11E V G =是图},{E V G =的生成子图，如果1G 是一棵树，记),(1E V T =，则称T 是G 的一棵生成树。 定理6.1 图G 有生成树的充分必要条件是图G 的连通的。 数学物理文科 理校教学校长 xx学院 《数据结构与算法》课程设计 报告书 课程设计题目 PRIM算法求最小生成树 院系名称计算机科学与技术系 专业（班级） 姓名（学号） 指导教师 完成时间 一、问题分析和任务定义 在该部分中主要包括两个方面：问题分析和任务定义； 1 问题分析 本次课程设计是通过PRIM（普里姆）算法，实现通过任意给定网和起点，将该网所对应的所有生成树求解出来。 在实现该本设计功能之前，必须弄清以下三个问题： 1．1 关于图、网的一些基本概念 1．1．1 图图G由两个集合V和E组成，记为G=（V，E），其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集，这些顶点偶对称为边。通常，V（G）和E（G）分别表示图G的顶点集合和边集合。E（G）也可以为空集。则图G只有顶点而没有边。1．1．2 无向图对于一个图G，若边集E（G）为无向边的集合，则称该图为无向图。1．1．3 子图设有两个图G=（V，E）G’=（V’，）,若V’是V的子集，即V’?V ，且E’是E的子集，即E’?E，称G’是G的子图。 1．1．4 连通图若图G中任意两个顶点都连通，则称G为连通图。 1．1．5 权和网在一个图中，每条边可以标上具有某种含义的数值，该数值称为该边的权。把边上带权的图称为网。如图1所示。 1．2 理解生成树和最小生成树之间的区别和联系 1．2．1 生成树在一个连通图G中，如果取它的全部顶点和一部分边构成一个子图G’，即：V（G’）= V（G）和E（G’）?E（G），若边集E（G’）中的边既将图中的所有顶点连通又不形成回路，则称子图G’是原图G的一棵生成树。 1．2．2 最小生成树图的生成树不是唯一的，把具有权最小的生成树称为图G的最小生成树，即生成树中每条边上的权值之和达到最小。如图1所示。 图1．网转化为最小生成树 1．3 理解PRIM（普里姆）算法的基本思想 1．3．1 PRIM算法（普里姆算法）的基本思想假设G =（V，E）是一个具有n个顶点的连通网，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，U和TE的初值均为空集。算法开始时，首先从V中任取一个顶点（假定取V0），将它并入U中，此时U={V0}，然后只要U是V的真子集，就从那些其一个端点已在T中，另一个端点仍在T外的所有边中，找一条最短（即权值最小）边，假定为（i,j），其中V i∈U,V j∈(V-U),并把该边（i,j）和顶点j分别并入T的边集TE和顶点集U，如此进行下去，每次往生成树里并入一个顶点和一条边，直到n-1次后就把所有n个顶点都并入到生成树T的顶点集中，此时U=V，TE中含有n-1条边，T就是最后得到的最小生成树。可以看出，在普利姆算法中，是采用逐步增加U中的顶点，常称为“加点法”。为了实现这个算法在本设计中需要设置一个辅助数组 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。 对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后一般不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs 或dfs，这样得到的是生成森林。 由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。 可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。 二、求图的最小生成树算法 严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V， E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。 对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。 求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。 例1、城市公交网 [问题描述] 有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。 [输入] n（城市数，1<=n<=100） e（边数） 以下e行，每行3个数i,j,w ij，表示在城市i,j之间修建高速公路的造价。 [输出] n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。 [举例] 下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。 [问题分析] 出发点：具有n个顶点的带权连通图，其对应的生成树有n-1条边。那么选哪n-1条边呢？设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。 1、用Prim算法求最小生成树的思想如下： ①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集； ②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S； ③重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中X∈S，not (Y∈S)； 将顶点Y加入集合S，边（X，Y）加入集合TE； ④得到最小生成树T =（S，TE） 数据结构实验报告 姓名：邱金梁 班级：rJBJava101 学号：201007092137指导老师：杨关 时间：2012年6月13日 一、最小生成树#include 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;//对象G int 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< 求出下图的最小生成树 解：MATLAB程序： % 求图的最小生成树的prim算法。 % result的第一、二、三行分别表示生成树边的起点、终点、权集合 % p——记录生成树的的顶点，tb=V\p clc;clear; % a(1,2)=50; a(1,3)=60; % a(2,4)=65; a(2,5)=40; % a(3,4)=52;a(3,7)=45; % a(4,5)=50; a(4,6)=30;a(4,7)=42; % a(5,6)=70; % a=[a;zeros(2,7)]; e=[1 2 20;1 4 7;2 3 18;2 13 8;3 5 14;3 14 14;4 7 10;5 6 30;5 9 25;5 10 9;6 10 30;6 11 30;7 8 2;7 13 5;8 9 4;8 14 2;9 10 6;9 14 3;10 11 11;11 12 30]; n=max([e(:,1);e(:,2)]); % 顶点数 m=size(e,1); % 边数 M=sum(e(:,3)); % 代表无穷大 a=zeros(n,n); for k=1:m a(e(k,1),e(k,2))=e(k,3); end a=a+a'; a(find(a==0))=M; % 形成图的邻接矩阵 result=[];p=1; % 设置生成树的起始顶点 tb=2:length(a); % 设置生成树以外顶点 while length(result)~=length(a)-1 % 边数不足顶点数-1 temp=a(p,tb);temp=temp(:); % 取出与p关联的所有边 d=min(temp); % 取上述边中的最小边 [jb,kb]=find(a(p,tb)==d); % 寻找最小边的两个端点(可能不止一个) j=p(jb(1));k=tb(kb(1)); % 确定最小边的两个端点 result=[result,[j;k;d]]; % 记录最小生成树的新边 p=[p,k]; % 扩展生成树的顶点 tb(find(tb==k))=[]; % 缩减生成树以外顶点 end result % 显示生成树（点、点、边长） weight=sum(result(3,:)) % 计算生成树的权 程序结果： result = 1 4 7 8 14 7 9 13 10 10 14 10 11 4 7 8 14 9 13 10 2 5 11 3 6 12 7 10 2 2 3 5 6 8 9 11 1 4 30 30 weight = 137 附图 最小生成树的权是137 编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 2013-2014学年第1 学期论文题目：最小生成树在旅游路线选择中的应用 学院名称： 学生姓名： 专业： 学号： 指导教师： 重庆邮电大学教务处制 摘要 随着生活节奏的加快，人民生活水平的提高，人们越来越热衷于四处旅游，同时，大家也不愿意将大部分的时间花费在路途上，人们旅游目的在于放松、赏景、游玩，旅游公司就不得不根据游客要求做出相应的旅游路线安排。很多旅游景点之间都相隔一定的距离，那么如何在众多旅游景点路线中选择最近的一条呢？因此，如何做到即保证游览各个景点又确保路途最近地从众多可行路线中选出最优路线成为了解决此问题的关键。 图论最小生成树理论常用于交通线路选择中，本文将其运用于旅游交通优化与线路组织上，即在赋权图中找出一颗最优树，以满足以最短路径最小连接各旅游目的城市和最小的建设成本。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法。本文涉及的抽象图形结构较为简单，使用各类算法的差别在此并无明显体现，一般来说，Kruskal 算法应用较为普遍，因此本文采用Kruskal 算法实现最优路径求取。 文中通过一个例子应用，将最小生成树的Kruskal 算法实际化，通过算法步骤分析，以及在VC++6.0中程序的运行，最终求出的最小生成树与实际相符，该算法思想成立，并具有一般性，能够增删节点、修改权值，也可运用到其他问题的解决中。 关键词：旅游路线问题 Kruskal算法最优路线最小生成树 一、引言 旅游交通是为旅游者由客源地到旅游目的地的往返，以及在旅游目的地各处旅游活动而提供的交通设施及服务，其便利程度，是衡量旅游业发达程度的重要标志。与一般交通不同，旅游交通过程本身也是旅游体验过程，对于游客来说，立足于最小的时间与经济成本获得最多的旅游体验，对于旅游组织者来说，则立足于最小的建设成本与最大的社会、经济、生态效益。道路是交通的载体，具有高度通达性、完善的旅游服务功能和景观化、生态化、人性化的道路是区域旅游交通完善的重要标志，基于此，有学者提出“风景道”、“旅游交通干道”等规划建设理念与原则。其中，旅游交通系统的优化很大程度取决于合理的道路布局，而如何使道路通达性与建设成本之间获得平衡，达到性价比最优，成为道路系统优化的重要指标。因此，其实质上可以简化为最短距离连接各旅游目的地最优解问题[1]。 旅游路线组织是旅游地理学研究的重要内容，其研究主要以游客的行为空间模式为导向，旅游路线是旅游产品的组成部分，作为产品就必须满足游客的需求，因此游客的行为模式就成为旅游路线设计的重要依据。 二、背景知识 1、图和树 图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。树是无圈连通无向图，如果树T的节点数为n，那么树的边数为n-1。 2、生成树 连通图G 上的一个子图，该子图连通，无回路且包含图G 的所有节点，称为连通图的极小连通子图。一个连通图可以有多棵不同的生成树。 3、最小生成树 对一个带权连通图，也有多可不同的生成树。由于该图是带权图，各边的权值不一定相等，因此这些生成树的各边权值之和也不一定相同，其中权值最小的生成树被称为该带权连通图的最小生成树[4]。 三、最小生成树的求解方法 构造最小生成树可以有多种算法。我们所学《图论及其算法》教材中介绍了其中的三种算法Prim 算法、Kruskal 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。 #include { printf("请输入有边的2个顶点\n"); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || n > G->vexnum) { printf("输入的数字不符合要求请重新输入:\n"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); printf("请输入%d与%d之间的权值:\n", n, m); scanf("%d",&G->arc[n][m].weight); } printf("邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } void sort(edge edges[],MGraph *G)//对权值进行排序{ int i, j; for ( i = 1; i < G->arcnum; i++) { for ( j = i + 1; j <= G->arcnum; j++) { if (edges[i].weight > edges[j].weight) { Swapn(edges, i, j); } } } printf("权排序之后的为:\n"); for (i = 1; i < G->arcnum; i++) { 武 夷 学 院 课程设计报告 课程名称： 数据结构（C 言语版本） 设计题目： 最小生成树的应用 学生班级： 10计科1班 学生姓名： 陈娟，谢贤根，黄伟伟，陈开槟 指导教师： 林丽惠 完成日期： 2012-01-05 课程设计项目研究报告 目录 一、问题描述及基本要求....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................. - 1 - 三、测试数据......................................................................................................... - 2 - 四、算法思想......................................................................................................... - 3 - 五、模块划分............................................................................ 错误！未定义书签。 六、算法设计与分析............................................................................................. - 7 - 七、源程序........................................................................................................... - 11 - 八、测试数据....................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表................................... - 15 - 十、设计心得....................................................................................................... - 16 -十一参考文献....................................................................................................... - 17 -离散数学 最小生成树
最小生成树问题
克鲁斯卡尔算法求最小生成树
最小生成树问题课程设计报告
Kruskal算法求最小生成树
最小生成树实验报告
贪心算法实验(最小生成树)
kruskal算法求最小生成树
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
(完整word版)普里姆算法求最小生成树
最小生成树模型与实验
PRIM算法求最小生成树
最小生成树算法分析
最短路径与最小生成树
求出下图的最小生成树
最小生成树在旅游路线选择中的应用概况
最小生成树的Kruskal算法实现
最小生成树的应用