克鲁斯卡尔算法求最小生成树
目录
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是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。
}
2.3主程序：
int main()
{
初始化；
while (条件)
{
接受命令;
处理命令;
}
return 0;
}
2.4抽象数据类型图的定义如下：
ADT Graph{
数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。
数据关系R：R={VR} VR={
基本操作P：
CreateGraph（&G，V，VR）；
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和的VR定义构造图G。
DestoryGraph（&G）；
初始条件：图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）；
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中添加弧
初始条件：图G存在，v和w是G中两个顶点。
操作结果：在G中删除弧
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行深度优先遍历。在遍历过程中对每个顶点调用函数
Visit一次且仅一次。一旦Visit（）失败，则操作失败。
BFSTravrese（G，Visit（））；
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit 一次且仅一次。一旦Visit（）失败，则操作失败。
}ADT Graph
2.5抽象数据类型树的定义如下：
ADT Tree{
数据对象D:D是具有相同特性数据元素的集合。
数据关系R：若D为空集，则称为空树；若D仅含一个元素数据，则R为空集，否则R={H}，H是如下二元关系：
（1）在D中存在唯一的称为根的数据元素root，它在关系H 下无前驱；
（2）若D-{root}≠Φ，则存在D-{root}的一个划分D1，D2，…，D m（m>0），
对任意j≠k（1≤j,k≤m）有D
j ∩D
k
=Φ，且对任意的I（1≤i≤m），惟一存在数
据元素x
i ∈D
i
有 i >∈H； （3）对应于D-{root}的划分，H-{ 1>，…， m >}有惟一的一 个划分H 1，H 2 ，…，H m （m＞0），对任意j≠k(1≤j，k≤m)有H j ∩H k =Φ，且对任 意I（1≤i≤m），H i 是D i 上的二元关系，（D i ，{H i }）是一棵符合本定义的树，称 为跟root的子树。 基本操作P： InitTree（&T）； 操作结果：构造空树T。 DestoryTree（&T）； 初始条件：树T存在。 操作结果：销毁树T。 CreateTree（&T，definition）； 初始条件：definition给出树T的定义。 操作结果：按definition构造树T。 ClearTree（&T）； 初始条件：树T存在。 操作结果：将树T清为空树。 TreeEmptey（T）； 初始条件：树T存在。 操作结果：若T为空树，则返回TRUE，否则FALSE。TreeDepth（T）； 初始条件：树T存在。 操作结果：返回T的深度。 Root（T）； 初始条件：树T存在。 操作结果：返回T的跟。 Value（T，cur_e）； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：返回cur_e的值。 Assign（T，cur_e，value）； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：结点cur_e赋值为value。 Parent（T，cur_e）； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非根结点，则返回它的双亲，否则函数值为“空”。LeftChild（T，cur_e）； 初始条件：树T存在，cur_e是T中某个结点。 操作结果：若cur_e是T的非叶子结点，则返回它的最左子，否则返回“空”。RightSibling（T，cur_e）； 初始条件：树T存在，，cur_e是T中某个结点。 操作结果：若cur_e有右兄弟，则返回它的右兄弟，否则函数值为“空”。InsertChild（&T，&p，I，c）； 初始条件：树T存在，P指向T中某个结点，1≤i≤p所指向的结点度数+1，非空树c与T不相交。 操作结果：插入c为T中p指结点的第i棵子树。 DeleteChild（&T，&p，i）； 初始条件：树T存在，p指向T中某个结点，1≤i≤p指结点的度。 操作结果：删除T中p所指结点的第i棵子树。 TraverseTree（T，Visit（））； 初始条件：树T存在，Visit是对结点操作的应用函数。 操作结果：按某种次序对T的每个结点调用函数visit（）一次且至多一次。一旦vista（）失败，则操作失败。 }ADT Tree 3.详细设计 3.1程序：如下 #include #include #include #define MAX_NAME 5 #define MAX_VERTEX_NUM 30 typedef char Vertex[MAX_NAME];/*顶点名字数组*/ typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接矩阵*/ typedef struct /*定义图*/ { Vertex vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; int LocateVex(MGraph *G,Vertex u) { int i; for(i=0;i if(strcmp(G->vexs[i],u)==0) return i; return -1; } void CreateGraph(MGraph *G) { int i,j,k,w; Vertex va,vb; printf("请输入无向网G的顶点数和边数(以空格作为间隔): \n"); scanf("%d %d",&G->vexnum,&G->arcnum); printf("请输入%d个顶点的名字(小于%d个字 符):\n",G->vexnum,MAX_NAME); for(i=0;i scanf("%s",G->vexs[i]); for(i=0;i for(j=0;j G->arcs[i][j]=0x7fffffff; printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G->arcnum); for(k=0;k { scanf("%s%s%d%*c",va,vb,&w); i=LocateVex(G,va); j=LocateVex(G,vb); G->arcs[i][j]=G->arcs[j][i]=w; /*对称*/ } } void kruskal(MGraph G) { FILE *fpt; fpt = fopen("9.txt","w");/*打开文档，写入*/ fprintf(fpt,"最小生成树的各条边为:\n"); int i,j; int k=0,a=0,b=0,min=G.arcs[a][b],min_out; printf("最小生成树的各条边为:\n"); while(k { for(i=0;i for(j=i+1;j if(G.arcs[i][j] { min=G.arcs[i][j]; a=i; b=j; } min_out=min; min=G.arcs[a][b]=0x7fffffff; printf("%s-%s-%d\n",G.vexs[a],G.vexs[b],min_out); fprintf(fpt,"%s-%s-%d\n",G.vexs[a],G.vexs[b],min_out); k++; } fclose(fpt); } void main() { MGraph g; CreateGraph(&g); kruskal(g); } 4. 调试与操作说明 4.1测试结果：如下图 图2测试结果1 图3测试结果2 4.2调试分析 本程序利用克鲁斯卡尔算法求最小生成树数据结构清晰因而调试比较顺利。在调试过程中主要是参数的传递比较不容易掌握。本程序的关键部分是如何确定一条边的两个端点是否属于同一连通分支，合并两个连通分支。 5. 课程设计总结与体会 5.1总结： 克鲁斯卡尔算法中的核心思想就是逐个在边的集合中找到最小的边，如果满足条件就将其构造，最后生成一个最小生成树。它首先是一系列的顶点集合，并没有边，然后我们从邻接矩阵中寻找最小的边，看看它是否和现有的边连接成一个环，如果连接成环，则舍弃，另外取其它的边。如果不连接成环，则接受这个边，并把其纳入集合中。 5.2体会： （1）通过求最小生成树，进一步掌握了图的含义，掌握了克鲁斯卡尔算法的基本思想及流程。知道了克鲁斯卡尔算法与普里姆算法的区别与联系。通过本次课程设计，锻炼了我们的实际操作能力，培养了我们严密的思维和严谨的态度。 （2）在编程序过程中虽然遇到了很多问题，但也使我学到了很多东西，在编制程序过程中我学到了在编程的开始需要总体设计一下自己的程序需要哪些大的模块，并想好所要用到的知识计算法，在编程过程中，特别是要画图时需要找出坐标，并研究各坐标各结点之间连线的规律，通过几句判断语句来实现多条连线问题，在编程过好还要反复调试程序，找出其中的漏洞并加以改正，在此次编程过程中就存在这样的问题，在经过反复修改后，终于可将漏洞扫除，正确的输出结果。 6.致谢 在编著过程中，感谢那些帮助我的同学，有了他们，我的课程设计才能顺利进行下去。 感谢同学在我的设计过程中提出的宝贵意见，如果没有他们的帮助，我在设计过程中出现的一些错误可能无法迅速查出解决，他们的帮助为我节省了宝贵的时间。 衷心感谢！ 7. 参考文献 [1] 严蔚敏，吴伟民.数据结构(C语言版).北京：清华大学出版社,1997.4 [2] 严蔚敏，吴伟民,米宁.数据结构题集(C语言版).北京：清华大学出版社,1999.2 1. 画出下图所示的无向图的邻接表。列出深度优先和广度优先搜索 遍历该图所的顶点序列和边的序列。 邻接表： 深度优先搜索：顶点序列：1 -2 -3- 4- 5 -6 边的序列：（1，2） （2，3） （3，4） （4，5） （5，6） 广度优先搜索：顶点序列：1 -2 -3 -6 -5-4 边的序列：（1，2） （1，3） （1，6） （1，5） （5，4） 2 已知以二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进 行遍历所得的深度优先生成树和广度优先生成树。 1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 0 0 1 0 1 0 2 0 0 1 0 0 0 1 0 0 0 3 0 0 0 1 0 0 0 1 0 0 4 0 0 0 0 1 0 0 0 1 0 5 0 0 0 0 0 1 0 0 0 1 6 1 1 0 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 1 1 5 2 4 6 3 8 1 0 0 1 0 0 0 0 1 0 9 0 0 0 0 1 0 1 0 0 1 10 1 0 0 0 0 1 0 0 0 0 解：邻接矩阵所表示的图如下： 自顶点1出发进行遍历所得的深度优先生成树： 自顶点1出发进行遍历所得的广度优先生成树： 3 请对下图的无向带权图 （1）写出它的邻接矩阵，并按普里母算法求其最小生成树。 （2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。 解：（1） 邻接矩阵： ∞ 4 3 ∞ ∞ ∞ ∞ ∞ 4 ∞ 5 5 9 ∞ ∞ ∞ 3 5 ∞ 5 ∞ ∞ ∞ 5 ∞ 5 5 ∞ 7 6 5 4 ∞ 9 ∞ 7 ∞ 3 ∞ ∞ ∞ ∞ ∞ 6 3 ∞ 2 ∞ ∞ ∞ ∞ 5 ∞ 2 ∞ 6 ∞ ∞ 5 4 ∞ ∞ 6 ∞ 普里母算法求得的最小生成树： 7 5 9 6 4 5 6 3 5 5 3 4 e d 2 5 c b h f g a 目录 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是否在同一个集合，如果在同一个集合则返回假，否则按秩合并这两个集合并返回真。 } 说明： 上机作业3道，10分 平时作业13道，10分 上机时间：第4、6、7周周六6:00-9:00 综合楼机房412 交上机作业时间：第5、7、8周周五截止。 上机作业格式：主题输入学号+姓名+第X次上机作业 平时作业：必须提交手写板 10月7日提交1-10题 10月31日提交11-13题 所有作业请按时交纳，不收补交作业。 1.设计一个非递归算法，从一棵二叉树中查找出所有结点的最大值并返回。 2.设树采用定长结点的多重链表表示，设计算法实现树的按层次遍历。 3.阅读下列算法，若有错，改正之。 BiTree InSucc(BiTree q) { // 已知q是指向中序线索二叉树上某个结点的指针， // 本函数返回指向*q的后继的指针。 r = q->rchild; if (r -> rtag==0 ) while (!r -> rtag ) r = r->rchild return r; } 4.写出二叉树的先序遍历和后序遍历的非递归算法。 5.设计一个非递归算法，计算树的叶子结点数。（要求说明树的存储方式） 6.已知带权无向图如图所示： (1). 根据普里姆（Prim）算法，设计算法,求它的从顶点a出发的最小生成树； (2). 根据克鲁斯卡尔（Kruskal）算法，求该图的最小生成树,给出添加边次序。 7．已知带权有向图如图所示： (1). 画出该图的邻接矩阵存储结构； (2). 求从顶点a到其余各顶点之间的最短路经及最短路经长度，并给出计算过程。 8．列出图中全部可能的拓扑有序序列，并指出应用7.5.1节中算法Topological Sort算法求得的是哪一个序列？ 9．对下图所示AOE网络，计算各活动弧的e(ai)和l（ai）函数值，各事件（顶点）的ve(vi)和vl(vi)函数值，列出各条关键路径。 10．试利用Floyd算法求图中所示有向图中各顶点之间的最短路径。（求解过程） 荆楚理工学院 课程设计成果 学院:_______计算机工程学院__________ 班级: 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 姓名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算法 #include cin>>c[i][j]; } } cout<<"Prim算法最小生成树选边次序如下："< 前言 从学习《数据结构》这门课程开始，我已发现了学习算法的乐趣，在学习这门课的过程中也学到了许多计算机应用基础知识，对计算机的机体也有了一个初步的了解，又在课余时间阅读了大量有关算法设计与分析的图书，在此基础上，利用贪心算法，编写了一个用prim 和kruskal算法求解最小生成树，也以此检验自己一学期所学成果，加深对算法设计与分析这门课程的理解，由于所学知识有限，难免有些繁琐和不完善之处，下面向大家介绍此程序的设计原理，方法，内容及设计的结果。 本程序是在windows 环境下利用Microsoft Visual C++ 6.0所编写的，主要利用贪心算法的思想，以及数组，for语句的循环，if语句的嵌套，运用以上所学知识编写出的prim和kruskal算法求解最小生成树，在输入其边的起始位置，种植位置以及权值后，便可分别输出此网的prim和kruskal算法最小生成树的边的起始位置，终止位置以及权值。 正文 2.1 设计方法和内容 一.软件环境：Microsoft Visual C++ 6.0 二.详细设计思想： 所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。 贪心算法的基本思路如下： 1.建立数学模型来描述问题。 2.把求解的问题分成若干个子问题。 3.对每一子问题求解，得到子问题的局部最优解。 4.把子问题的解局部最优解合成原来解问题的一个解。 1.Prim（普里姆）算法思想 无向网的最小生成树问题 此算法的思想是基于点的贪心，力求从源点到下一个点的距离最短，以此来构建临接矩阵，所以此算法的核心思想是求得源点到下一个点的最短距离，下面具体解释如何求此最短距离： 在图中任取一个顶点k作为开始点，令集合U={k},集合w=V-U,其中v为图中所 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次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） 实验报告 实验原理： 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）打印最小生成树边的顶点及权值。 实验器材（设备、元器件）： PC机一台，装有C语言集成开发环境。 数据结构与程序： #include #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; } 1.无向网图及边集数组存储示意图 vertex[6]= 2.Kruskal 方法构造最小生成树的过程 (a)一个图 (b)最小生成树过程1 V0 V1 V2 V3 V4 V5 下标 0 1 2 3 4 5 6 7 8 from 1 2 0 2 3 4 0 3 0 to 4 3 5 5 5 5 1 4 2 weight 12 17 19 25 25 26 34 38 46 V1 V0 V4 V5 V2 V3 V1 V0 V5 V2 V3 V4 (c)最小生成树过程2 （d)最小生成树过程3 (e)最小生成树过程4 3.伪代码 1）初始化辅助数组parent[vertexNum];num=0; 2) 依次考查每一条边for(i=0; i 最小生成树的两种经典算法的分析及实现 摘要：数据结构是计算机科学的算法理论基础和软件设计的技术基础，在计算机领域中有着举足轻重的作用，是计算机学科的核心课程。构造最小生成树有很多算法，本文主要介绍了图的概念、图的遍历，并分析了PRIM和KRUSKAL的两种经典算法的算法思想，对两者进行了详细的比较，最后用这两种经典算法实现了最小生成树的生成。 关键词：连通图，赋权图，最小生成树，算法，实现 1 前言 假设要在n个城市之间建立通信联络网，则连接n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在节省费用的前提下建立这个通信网？自然在每两个城市之间都可以设置一条线路，而这相应的就要付出较高的经济代价。n个城市之间最多可以设置n （n-1）/2条线路，那么如何在这些可能的线路中选择n-1 条使总的代价最小呢？可以用连通网来表示n 个城市以及n个城市之间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋予边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。一棵生成树的代价就是树上各边的代价之和。 2图的概念 2.1 定义 无序积 在无序积中， 无向图，其中为顶点(结点)集，为边集，，中元素为无向边，简称边。 有向图，其中为顶点(结点)集，为边集，，中元素为有向边，简称边。 有时，泛指有向图或无向图。 2.2 图的表示法 有向图，无向图的顶点都用小圆圈表示。 无向边——连接顶点的线段。 有向边——以为始点，以为终点的有向线段。 2.3 概念 (1)有限图——都是有限集的图。 阶图——的图。 零图——的图。特别，若又有，称平凡图。 (2)关联 (边与点关系)——设边(或)，则称与(或)关联。 无环 孤立点——无边关联的点。 环——一条边关联的两个顶点重合，称此边为环 (即两顶点重合的边)。 悬挂点——只有一条边与其关联的点，所对应的边叫悬挂边。 (3)平行边——关联于同一对顶点的若干条边称为平行边。平行边的条数称为重数。 多重图——含有平行边的图。 简单图——不含平行边和环的图。 2.4 完全图 设为阶无向简单图，若中每个顶点都与其余个顶点相邻，则 称为阶无向完全图，记作。 若有向图的任一对顶点，既有有向边，又有有向边，则 称为有向完全图。 例如： 课程设计报告 课程名称：数据结构课程设计 设计题目：克鲁斯卡尔算法求最小生成树 系别：计算机系 专业：软件技术 学生姓名：陈浩学号:2011304040133 日期: 2013年1月5日-2013年1月11日 目录 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主程序 (3) 2.4抽象数据类型图的定义 (4) 2.5抽象数据类型树的定义 (6) 3. 详细设计 (8) 3.1程序 (8) 4.调试与操作说明 (11) 4.1测试结果 (11) 4.2调试分析 (12) 5.课程设计总结与体会 (12) 5.1总结 (12) 5.2体会 (12) 6. 致谢 (13) 7. 参考文献 (13) 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.概要设计 一、树及生成树的基本概念 树是无向图的特殊情况，即对于一个N个节点的无向图，其中只有N-1条边，且图中任意两点间有且仅有一条路径，即图中不存在环，这样的图称为树，一般记为T。树定义有以下几种表述： (1)、T连通、无圈、有n个结点，连通有n－1条边；(2)、T无回路，但不相邻的两个结点间联以一边，恰得一个圈；(3)、T连通，但去掉任意一边，T就不连通了（即在点集合相同的图中，树是含边数最少的连通图）；(4)、T的任意两个结点之间恰有一条初等链。 例如：已知有六个城市，它们之间要架设电话线，要求任 意两个城市均可以互相通话，并且电话线的总长度最短。若用 六个点v1…v6代表这六个城市，在任意两个城市之间架设电话 线，即在相应的两个点之间连一条边。这样，六个城市的一个 电话网就作成一个图。任意两个城市之间均可以通话，这个图 必须是连通图，且这个图必须是无圈的。否则，从圈上任意去 掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是 一个不含圈的连通图，代表了一个电话线网。 生成树（支撑树） 定义：如果图G’是一棵包含G的所有顶点的树，则称G’是G的一个支撑树或生成树。例如,图5-7b是图5-7a的一个支撑树。 定理：一个图G有生成树的条件是G是连通图。 证明:必要性显然； 充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一生成子图G1。若G1不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一生成子图G2。依此类推，可以得到图G的一个生成子 图G K，且不含圈，从而G K是一个生成树。 寻找连通图生成树的方法： 破圈法：从图中任取一个圈，去掉一条边。再对剩下的图 重复以上步骤，直到不含圈时为止，这样就得到一个生成树。 取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3。在剩下的图 中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4。再从圈（v3,v4,v5,v3） 中去掉边e6。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7， 这样，剩下的图不含圈，于是得到一个支撑树，如图所示。 避圈法：也称为生长法，从图中某一点开始生长边，逐步扩展成长为一棵树，每步选取与已入树的边不构成圈的那些边。 #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++) { 实验5 最小生成树算法的设计与实现 一、实验目的 1、根据算法设计需要, 掌握连通图的灵活表示方法； 2、掌握最小生成树算法，如Prim、Kruskal算法； 3、基本掌握贪心算法的一般设计方法； 4、进一步掌握集合的表示与操作算法的应用。 二、实验内容 1、认真阅读算法设计教材和数据结构教材内容, 熟习连通图的不同表示方法和最小生成树算法； 2、设计Kruskal算法实验程序。 有n个城市可以用（n-1）条路将它们连通，求最小总路程的和。 设计测试问题,修改并调试程序, 输出最小生成树的各条边, 直至正确为止。 三、Kruskal算法的原理方法 边权排序: 1 3 1 4 6 2 3 6 4 1 4 5 2 3 5 3 4 5 2 5 6 1 2 6 3 5 6 5 6 6 1. 初始化时：属于最小生成树的顶点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}此时，最小生成树已完成 说明： （1）平时作业共20分； （2）交纸质作业； （3）所有作业请按时交纳，不收补交作业。 栈、队列、数组 作业一： 1． 若进栈序列为ABCD ，请写出全部可能的出栈序列和不可能的出栈序列。 2． 简要说明循环队列如何判断队满和队空？ 3． 设A 为n 阶对称矩阵，采用压缩存储存放于一维数组F[n(n+1)/2]中（从F[0] 开始存放），请分别给出存放上三角阵时任一矩阵元素a ij （1≤i,j ≤n ）的地址计算公式和存放下三角阵时任一矩阵元素a ij （1≤i,j ≤n ）的地址计算公式。 4． 写出下面稀疏矩阵的三元组顺序表和十字链表表示。 树 作业二： 1． 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 2． 已知二叉树的先序遍历序列是EABDCFHGIKJ ，中序遍历序列是ABCDEFGHIJK ， 请构造二叉树，并写出其层次遍历序列和后序遍历序列。 3． 假设用于通信的电文由7个字母{A,B,C,D,E,F,G}组成，字母在电文中出现 的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码（约定哈夫曼树中左孩子结点的权值小于等于右孩子结点的权值），并计算其带权路径长度WPL 。 4． 将下图所示的森林转换成一棵二叉树。 A B C D G H I J K E F L 5． 将下图所示的二叉树还原成树或森林。 4000005030080 00000000700200000A ?? ?????? =?? ?????? 图Array作业三: 1．已知带权有向图如图所示。 (1) 画出该图的邻接矩阵存储结构； (2) 求从顶点a到其余各顶点之间的最短路经及 最短路经长度，并给出计算过程。 2．无向图邻接表存储结构如图所示： (1) 画出该无向图； (2) 写出在该邻接表上，从顶点1出发所得到的深度优先遍历(DFS)和广度优先 遍历(BFS)序列。 1 2 3 4 5 6 7 8 3. 已知带权无向图如图所示： （1）根据普里姆（Prim）算法，求它的从顶点a出发的最 小生成树(写出过程，即添加顶点、边次序)； （2）根据克鲁斯卡尔（Kruskal）算法，求该图的最小生 成树(写出过程，即添加边次序)。 查找、排序 Kruskal 算法构造最小生成树 构造赋权图(,,)G V E W =，其中12{,,,}n V v v v = 为顶点集合,其中i v 表示第i 个顶点，12{,,,,}i E e e e = 为边的集合，()ij n n W w ?=为邻接矩阵，其中 i j i j ij i j v v v v w v v ∈??=?∞??顶点与之间的距离，当（，） E ，与之间没有边时 科茹斯克尔（Kruskal ）算法如下： （1）选1e E ∈（E 为边的集合），使得1e 是权重最小的边。 （2）若12,,e i e e …，已选好，则从12{,,e }i E e e -…，中选取1i e +，使得 i ）121{,,e }i e e +…，中无圈，且 ii ）是1i e +是12{,,e }i E e e -…，中权重最小的边。 （3）直到选得1V e - 为止。(V 是集合V 中元素的个数) 例：已知9个村庄之间的两两距离见表5，要架设通讯线路把9个村庄连接起来，求所需要通讯线的最小长度。 表5 10个村庄的两两距离数据（单位：km ） (,,)G V E W =，其中129{,, ,}V v v v = 为顶点集合,其中i v 表示第i 个村庄，12{,,,,}i E e e e = 为边的集合，99()ij W w ?=为邻接矩阵，其中 i j i j ij i j v v v v w v v ∈??=?∞??村庄与之间的距离，当（，） E ，与之间没有通讯路线时 科茹斯克尔（Kruskal ）算法如下： （1）选1e E ∈（E 为边的集合），使得1e 是距离最小的边。 Prim 算法和Kruskal 算法的Matlab 实现 连线问题应用举例： 欲铺设连接n 个城市的高速公路，若i 城与j 城之间的高速公路造价为ij C ，试设计一个线路图，使总的造价最低。 连线问题的数学模型就是图论中在连通的赋权图上求权最小的支撑树。试用Matlab 分别实现求最小支撑数的Prim 算法和Krusal 算法（避圈法）。 一.基本要求： （1） 画出程序流程图； （2） 对关键算法、变量和步骤进行解释说明； （3） 用如下两图对所写算法的正确性进行验证。即输入图的信息，输出对应图 的最小支撑树及其权值。 v 1 v 74 5 v 216 19 6 6 11 2183020 51514 9241 67 53 48 44 （4）分析两种算法的实现复杂度。 二.扩展要求： （1）提供对算法效率（复杂度）进行评估的方法，并通过举例验证，与分析得到的算法复杂度结果相对照； （2）从降低内存消耗、减少计算时间的角度，对算法进行优化。 三．实验步骤 I.用Prim 算法求最小生成树 i ．算法分析及需求分析，程序设计 prim 算法的基本思想是：设G=（V ，E ）是一个无向连通网，令T=（U ，TE ）是G 的最小生成树。T 的初始状态为U={v0}（v0 ）TE={}，然后重复执行下述操作：在所有u U ， v V-U 的边中找一条代价最小的边（u ，v ）并入集合TE ，同时v 并入U ，直至U=V 为止。 显然，Prim 算法的基本思想是以局部最优化谋求全局的最优化，而且，还涉及到起始结点的问题。 本程序完成的功能是：从图中的任意结点出发，都能够找出最小生成树 Kruskal算法求最小生成树（JA V A） 代码： package homework; import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; class Edge { public int start;//始边 public int end;//终边 public double cost;//权重 } public class MinSpanningTree_Kruskal{ private static int MAX = 100; private ArrayList数据结构课后作业答案
克鲁斯卡尔算法求最小生成树
(二)作业
Kruskal算法求最小生成树
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
贪心算法实验(最小生成树)
普里姆和克鲁斯卡尔算法
最小生成树算法分析
克鲁斯卡尔算法实验报告
kruskal算法求最小生成树
Kruskal算法说明及图解
最小生成树经典算法
课程设计---克鲁斯卡尔算法求最小生成树
最小生成树(Prim、Kruskal算法)整理版
最小生成树的Kruskal算法实现
(完整word版)实验5 最小生成树算法的设计与实现(报告)
研究生数据结构作业2016(更新版)
Kruskal算法
Prim算法和Kruskal算法的Matlab实现
Kruskal算法求最小生成树(java)
相关文档
- 数学建模-最小生成树-kruskal算法及各种代码
- 算法合集之《最小生成树算法及其应用》
- 最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
- Kruskal算法求最小生成树(java)
- 一种基于二进制编码的最小生成树算法
- 最小生成树算法
- 最小生成树及其算法
- 最小生成树经典算法
- c语言实现最小生成树算法
- 改进的最小生成树算法.
- 最小生成树算法(一)
- 最小生成树算法
- 几种求解最小生成树的算法 (论文)
- 经典最小生成树prim与kruskal算法分析比较
- 最小生成树算法讲解分解
- 图的最小生成树_prim算法
- 最小生成树算法详解.ppt
- 数据结构课程设计报告最小生成树Kruskal算法[1]4545
- 数学建模-最小生成树-kruskal算法及各种代码
- 最小生成树算法详解