构造可以使n个城市连接的最小生成树课案
《数据结构》
课程设计报告
设计题目：构造可以使n个城市连接的最小生成树姓名：
学号：
专业：物联网工程（嵌入式培养）
院系：计算机技术与科学学院
班级：1405
指导教师：
2016年01 月09 日
摘要
本次课程设计的要求是给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。将该地区的城市用顶点表示，城市间的公路用边表示，公路的长度作为边的权值，最终这个问题可以归结为网图中，求顶点A到顶点B的所有路径中，边的权值之和最少的那条路径。
关键词：
最小生成树
Prim算法
C++语言源程序
Abstract
The curr iculum design requirements is given a region n city, the distance between the net with the Prim algorithm to establish minimum spanning tree, and calculated the price of minimum spanning tree. Cities in the region with vertex said, between highway in the city edge, said the length of the road as the edge of the right values, finally the problem can be summed up in network diagram, and all the paths of vertex A to B, the edge of the weights of the sum of the minimum path. Keywords:
minimum spanning tree
Prim algorithm
C++ language source program
目录
一、问题描述 (4)
1.1题目内容 (4)
1.2基本要求 (4)
二、需求分析 (4)
三、概要设计 (4)
3.1邻接矩阵的建立 (5)
3.2图的建立 (5)
3.3求最小生成树 (6)
四、数据结构设计 (7)
五、算法设计 (8)
5.1算法分析 (8)
5.2算法实现 (8)
六、程序测试与实现 (9)
6.1主程序 (9)
6.2测试结果 (10)
七、调试分析 (10)
八、遇到的问题及解决办法 (10)
九、心得体会 (10)
十、附录 (11)
一、问题描述
1．题目内容：给定一个地区的n个城市间的距离网，用Prim算法建立最小生成树，并计算得到的最小生成树的代价。
2．基本要求：
a)城市间的距离网采用邻接矩阵表示，若两个城市之间不存在
道路，则将相应边的权值设为自己定义的无穷大值。（要求
至少10个城市，15条边）
b)最小生成树中包括的边及其权值，并显示得到的最小生成树
的代价。
二、需求分析
本程序的功能包括图的建立（采用邻接矩阵存储）和求最小生成树。
①图的建立涉及到顶点数组data[n]和邻接矩阵Edge[n][n]，顶点数组运用顺序表完成，操作有：顶点的插入即顺序表的插入；邻接矩阵的建立，操作有：插入弧和对应的权值,输出邻接矩阵
②最小生成树是通过Prim算法完成的。Prim里涉及到候选最短边集，用数组shortEdge[n]表示候选最短边集，数组元素包括候选最短边的的邻接点（adjvex）和权值（lowcost）两个域
三、概要设计
1.邻接矩阵的建立
①邻接矩阵的初始化，顶点自己对自己的权值为0，其余的
权值均为MaxWeight（自定义的无穷大,999）
AdjMatGraph::AdjMatGraph(const int sz)//sz是顶点数，有参构造函数
{
for(int i=0;i for(int j=0;j { if(i==j) Edge[i][j]=0; else Edge[i][j]=MaxWeight;//无穷大 } numOfEdges=0; } ②邻接矩阵中点与点之间有弧的，则将两个顶点之间的权值 设为weight取代MaxWeight（无穷大,999） void AdjMatGraph::InsertEdge(const int v1,const int v2,int weight)//插入弧 为weight { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { cout<<"参数v1,v2有误2"< exit(0); } Edge[v1][v2]=weight; Edge[v2][v1]=weight; numOfEdges++; } 2.图的建立 struct RowColWeight//边信息三元组 { int row; int col; int weight; }; void AdjMatCreateGraph(AdjMatGraph &G,DataType V[],int n,RowColWeight E[],int e)//用一个存储边权信息的三元组来生成图 { int i; for( i=0;i G.InsertVertex(V[i]);//填充顶点信息 for(i=0;i G.InsertEdge(E[i].row,E[i].col,E[i].weight); } 3.求最小生成树 struct shortEdge { int lowcost; int adjvex; }; void AdjMatGraph::Prim() { int k,w,cost=0; for(int i=1;i { shortEdge[i].lowcost=Edge[0][i]; shortEdge[i].adjvex=0; } shortEdge[0].lowcost=0; for(int i=1;i { w=MaxWeight ; for(int j=1;j { if(shortEdge[j].lowcost!=0 && shortEdge[j].lowcost { w=shortEdge[j].lowcost; k=j; } } shortEdge[k].lowcost=0; for(int j=1;j { if(Edge[k][j] < shortEdge[j].lowcost) { shortEdge[j].lowcost=Edge[k][j]; shortEdge[j].adjvex=k; } } } cout<<"最小生成树为："< for(int i=1;i { cout< cost=cost+Edge[i][shortEdge[i].adjvex]; } cout<<"最小生成树代价为："< } 四、数据结构设计 元素类型，结点类型 class SeqList { private: DataType data[MaxListSize]; int size; public: SeqList(); int ListSize()const;//返回元素的个数size void Insert(const DataType & item,int pos);//在位置pos插入元素item }; struct RowColWeight//边信息三元组 { int row; int col; int weight; }; struct RowColWeight//边信息三元组 { int row; int col; int weight; }; class AdjMatGraph { private: SeqList Vertices;//用顺序表存储结点信息 int Edge[MaxVertices][MaxVertices];//用数组存储带权或不带权的边 int numOfEdges;//边数 shortEdge shortEdge[MaxSize]; public: AdjMatGraph(const int sz=MaxVertices); //有参构造函数,sz为顶点数 int numOfVertices()//返回结点数目 { return Vertices.ListSize(); } int numOfEdge()//返回边数 { return numOfEdges; } void InsertVertex(const VerT &vertex);//插入结点vertex void InsertEdge(const int v1,const int v2,int weight);//插入弧 void printMGraph(); void Prim(); }; 五、算法设计 1.算法分析 根据用Prim算法求最小生成树，设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是G的最小生成树，T的初始状态为U={u0}( u0∈V）),TE={ },重复执行下述操作：在所有u∈U,v∈V-U的边中找一条代价最小的边（u，v）并入集合TE,同时v并入U,直至U=V0,最后计算得到的最小生成树的代价 2.算法实现 void AdjMatGraph::Prim() { int k,w,cost=0; for(int i=1;i { shortEdge[i].lowcost=Edge[0][i]; shortEdge[i].adjvex=0; } shortEdge[0].lowcost=0; for(int i=1;i { w=MaxWeight ; for(int j=1;j { if(shortEdge[j].lowcost!=0 && shortEdge[j].lowcost { w=shortEdge[j].lowcost; k=j; } } shortEdge[k].lowcost=0; for(int j=1;j { if(Edge[k][j] < shortEdge[j].lowcost) { shortEdge[j].lowcost=Edge[k][j]; shortEdge[j].adjvex=k; } } } cout<<"最小生成树为："< for(int i=1;i { cout< cost=cost+Edge[i][shortEdge[i].adjvex]; } cout<<"最小生成树代价为："< } 六、程序测试与实现 1.主程序 void main() { AdjMatGraph g; char a[]={'A','B','C','D','E','F','G','H','I','J'}; RowColWeight rcw[]={{0,4,1},{0,1,2},{4,5,3},{0,5,4},{1,5,5},{5,6,6},{1,2,7},{2,6,8}, {2,7,9},{2,3,10},{3,7,11},{3,9,12},{8,9,13},{7,8,14},{6,7,15}}; int n=10,e=15;//10个顶点，15条边 AdjMatCreateGraph(g,a,n,rcw,e); cout << "当前的顶点个数为：" << g.numOfVertices() << endl; cout << "当前的边的条数为：" << g.numOfEdge() << endl; g.printMGraph(); g.Prim(); } 2.测试结果（999是我自己设置的无穷大） 七、调试分析 1．图的邻接矩阵是一个n*n的矩阵，所以其空间代价是O(n2) 2．在求解最小生成树的过程中，会不断的读取任意两个顶点之间边的权值，所以采用邻接矩阵 八、遇到的问题及解决办法 在求解利用Prim求解最小生成树的过程中，算法能够看懂，但是利用C++程序去实现，还是有问题的。最后反复看代码，构造了一个最短候选边集，即数组shortEdge[n]。 九、心得体会 本次课程设计用到了顺序表的建立与插入，图的邻接矩阵存储，最终实现了求n个城市之间的相同公路之间的最短距离，我主要学到了将实际问题转换为自己所学到的知识，做到了学以致用。 十、附录（源代码） SeqList.h #include using namespace std; class SeqList { private: DataType data[MaxListSize]; int size; public: SeqList(); int ListSize()const;//返回元素的个数 void Insert(const DataType & item,int pos);//在位置pos插入元素 }; SeqList::SeqList() { size=0; } int SeqList::ListSize()const { return size; } void SeqList::Insert(const DataType & item,int pos)//在位置pos插入元素item { int i; if(size==MaxListSize) { cout<<"顺序表已满无法插入！"< exit(1); } if(pos<0||pos>size)//当pos等于size时表示插入在最后 { cout<<"参数pos越界出错!"< exit(1); } //从后向前把前一个元素迁移到后一个元素位置直到存储位置pos为止 for(i=size;i>pos;i--) data[i]=data[i-1]; data[pos]=item;//在pos位置插入item size++;//数据元素个数size加1 } AdjMatGraphLib.h struct RowColWeight//边信息三元组 { int row; int col; int weight; }; void AdjMatCreateGraph(AdjMatGraph &G,DataType V[],int n,RowColWeight E[],int e)//用一个存储边权信息的三元组来生成图 { int i; for( i=0;i G.InsertVertex(V[i]);//填充顶点信息 for(i=0;i G.InsertEdge(E[i].row,E[i].col,E[i].weight); } AdjMatGraph.h #include const int MaxSize=100; struct shortEdge { int lowcost; int adjvex; }; class AdjMatGraph { private: SeqList Vertices;//用顺序表存储结点信息 int Edge[MaxVertices][MaxVertices];//用数组存储带权或不带权的边 int numOfEdges;//边数 shortEdge shortEdge[MaxSize]; public: AdjMatGraph(const int sz=MaxVertices); //有参构造函数,sz为顶点数 int numOfVertices()//返回结点数目 { return Vertices.ListSize(); } int numOfEdge()//返回边数 { return numOfEdges; } void InsertVertex(const VerT &vertex);//插入结点vertex void InsertEdge(const int v1,const int v2,int weight);//插入弧 void Prim(); }; AdjMatGraph::AdjMatGraph(const int sz)//sz是顶点数，有参构造函数 { for(int i=0;i for(int j=0;j { if(i==j) Edge[i][j]=0; else Edge[i][j]=MaxWeight;//无穷大 } numOfEdges=0; } void AdjMatGraph::InsertVertex(const VerT &vertex)//插入结点vertex { Vertices.Insert(vertex,Vertices.ListSize()); } void AdjMatGraph::InsertEdge(const int v1,const int v2,int weight)//插入弧 { if(v1<0||v1>Vertices.ListSize()||v2<0||v2>Vertices.ListSize()) { cout<<"参数v1,v2有误2"< exit(0); } Edge[v1][v2]=weight; Edge[v2][v1]=weight; numOfEdges++; } void AdjMatGraph::printMGraph() { cout<<"邻接矩阵是："< for(int i=0;i { for(int j=0;j { cout< } cout< cout< } } void AdjMatGraph::Prim() { int k,w,cost=0; for(int i=1;i { shortEdge[i].lowcost=Edge[0][i]; shortEdge[i].adjvex=0; } shortEdge[0].lowcost=0; for(int i=1;i { w=MaxWeight ; for(int j=1;j { if(shortEdge[j].lowcost!=0 && shortEdge[j].lowcost { w=shortEdge[j].lowcost; k=j; } } shortEdge[k].lowcost=0; for(int j=1;j { if(Edge[k][j] < shortEdge[j].lowcost) { shortEdge[j].lowcost=Edge[k][j]; shortEdge[j].adjvex=k; } } } cout<<"最小生成树为："< for(int i=1;i { cout< cost=cost+Edge[i][shortEdge[i].adjvex]; } cout<<"最小生成树代价为："< } Main.cpp #include typedef char DataType; const int MaxListSize=100; const int SeqQMaxSize=100; #include"SeqList.h" const int MaxVertices=100; const int MaxWeight=999; typedef char VerT; #include"AdjMatGraph.h" #include"AdjMatGraphLib.h" using namespace std; void main() { AdjMatGraph g; char a[]={'A','B','C','D','E','F','G','H','I','J'}; RowColWeight rcw[]={{0,4,1},{0,1,2},{4,5,3},{0,5,4},{1,5,5},{5,6,6},{1,2,7},{2,6,8}, {2,7,9},{2,3,10},{3,7,11},{3,9,12},{8,9,13},{7,8,14},{6,7,15}}; int n=10,e=15;//10个顶点，15条边 AdjMatCreateGraph(g,a,n,rcw,e); cout << "当前的顶点个数为：" << g.numOfVertices() << endl; cout << "当前的边的条数为：" << g.numOfEdge() << endl; g.printMGraph(); g.Prim(); } 数学与计算机学院 课程设计说明书 课程名称: 数据结构与算法课程设计 课程代码: 6014389 题目: 图的遍历和生成树求解实现 年级/专业/班: 学生姓名: 学号: 开始时间: 2012 年 12 月 09 日 完成时间: 2012 年 12 月 26 日 课程设计成绩： 指导教师签名：年月日 目录 摘要 (3) 引言 (4) 1 需求分析 (5) 1.1任务与分析 (5) 1.2测试数据 (5) 2 概要设计 (5) 2.1 ADT描述 (5) 2.2程序模块结构 (7) 软件结构设计： (7) 2.3各功能模块 (7) 3 详细设计 (8) 3.1结构体定义 (19) 3.2 初始化 (22) 3.3 插入操作（四号黑体） (22) 4 调试分析 (22) 5 用户使用说明 (23) 6 测试结果 (24) 结论 (26) 摘要 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： ?了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； ?初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； ?提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 这次课程设计我们主要是应用以前学习的数据结构与面向对象程序设计知识，结合起来才完成了这个程序。 因为图是一种较线形表和树更为复杂的数据结构。在线形表中，数据元素之间仅有线性关系，每个元素只有一个直接前驱和一个直接后继，并且在图形结构中，节点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。因此，本程序是采用邻接矩阵、邻接表、十字链表等多种结构存储来实现对图的存储。采用邻接矩阵即为数组表示法，邻接表和十字链表都是图的一种链式存储结构。对图的遍历分别采用了广度优先遍历和深度优先遍历。 关键词：计算机；图；算法。 图 1. 填空题 ⑴ 设无向图G中顶点数为n，则图G至少有（）条边，至多有（）条边；若G为有向图，则至少有（）条边，至多有（）条边。 【解答】0，n(n-1)/2，0，n(n-1) 【分析】图的顶点集合是有穷非空的，而边集可以是空集；边数达到最多的图称为完全图，在完全图中，任意两个顶点之间都存在边。 ⑵ 任何连通图的连通分量只有一个，即是（）。 【解答】其自身 ⑶ 图的存储结构主要有两种，分别是（）和（）。 【解答】邻接矩阵，邻接表 【分析】这是最常用的两种存储结构，此外，还有十字链表、邻接多重表、边集数组等。 ⑷ 已知无向图G的顶点数为n，边数为e，其邻接表表示的空间复杂度为（）。 【解答】Ｏ(n+e) 【分析】在无向图的邻接表中，顶点表有n个结点，边表有2e个结点，共有n+2e个结点，其空间复杂度为Ｏ(n+2e)=Ｏ(n+e)。 ⑸ 已知一个有向图的邻接矩阵表示，计算第j个顶点的入度的方法是（）。 【解答】求第j列的所有元素之和 ⑹ 有向图G用邻接矩阵A[n][n]存储，其第i行的所有元素之和等于顶点i的（）。 【解答】出度 ⑺ 图的深度优先遍历类似于树的（）遍历，它所用到的数据结构是（）；图的广度优先遍历类似于树的（）遍历，它所用到的数据结构是（）。 【解答】前序，栈，层序，队列 ⑻ 对于含有n个顶点e条边的连通图，利用Prim算法求最小生成树的时间复杂度为（），利用Kruskal 算法求最小生成树的时间复杂度为（）。 【解答】Ｏ(n2)，Ｏ(elog2e) 【分析】Prim算法采用邻接矩阵做存储结构，适合于求稠密图的最小生成树；Kruskal算法采用边集数组做存储结构，适合于求稀疏图的最小生成树。 ⑼ 如果一个有向图不存在（），则该图的全部顶点可以排列成一个拓扑序列。 【解答】回路 ⑽ 在一个有向图中，若存在弧、、，则在其拓扑序列中，顶点vi, vj, vk的相对次序为（）。 【解答】vi, vj, vk 【分析】对由顶点vi, vj, vk组成的图进行拓扑排序。 2. 选择题 ⑴ 在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。 A 1/2 B 1 C 2 D 4 【解答】C 【分析】设无向图中含有n个顶点e条边，则。 用Prim算法构造最小生成树 班级：2010级计算机1班学号：2010131116 姓名：杨才一、实验目的 了解最小生成树的概念，掌握生成最小生成树的方法。 二、实验内容 建立一个含任意结点的无向连通网，并用Prim算法构造其最小生成树 三、实验要点及说明 如果无向连通图是一个网，则其所有生成树中必有一棵树的边的权值总和最小，这棵生成树为最小生成树。 Prim算法：在图G=（V，E）（V为顶点集，E为边集）中任选一顶点v0,令集合U={v0}为初态，在一个顶点在U中，另一顶点在V-U 中的所有边中找权值最小的边（u,v）（U∈ u,v∈ V-U），并将v加入到U中，同时将边（u,v）加入集合T中（T的初态为空集），这样不断地扩大U，直至U=V，则集合T中的边为所求最小生成树的边 四、算法思想与算法描述 1、邻接矩阵的数据类型的定义如下： typedef struct { int no; /*顶点编号*/ string name; /*顶点其他信息*/ } VertexType; /*顶点类型*/ typedef struct/*图的定义*/ { int edges[MAXV][MAXV]; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数,弧数*/ VertexType vexs[MAXV]; /*存放顶点信息*/ }MGraph; 2、临时数组的存放的数据类型 struct { int closest; // U集中的顶点序号 int lowcost; // 边的权值 } closedge[MAXV]; int const INF=32767; /*INF表示∞*/ 3、prime算法实现：（原理见实验说明） void prime(MGraph g,int v) { int lowcost[MAXV]; int min; int closest[MAXV]; int i,j,k; for(i=0;i 榆林学院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的代价最小的边的 河北科技大学 课程设计报告 学生姓名：白云学号：Z110702301 专业班级：计算机113班 课程名称：数据结构课程设计 学年学期： 2 01 3—2 014学年第2学期指导教师：郑广 2014年6月 课程设计成绩评定表 目录 一、需求分析说明 (1) 1.1最小生成树总体功能要求 (1) 1.2基本功能 (1) 1.3 模块分析 (1) 二、概要设计说明 (1) 2.1设计思路 (1) 2.2模块调用图 (2) 2.3数据结构设计 (2) 2.3.1.抽象数据类型 (2) 2.3.2方法描述 (2) 三、详细设计说明 (3) 3.1主函数模块 (3) 3.2邻接表输出子模块 (3) 3.3邻接矩阵输出子模块 (3) 3.4创建邻接矩阵子模块 (3) 3.5创建邻接表子模块 (3) 3.6 Prim子模块 (3) 3.7 Kruscal子模块 (4) 四、调试分析 (4) 4.1实际完成情况说明 (4) 4.2 出现的问题及解决方案 (4) 4.3程序中可以改进的地方 (4) 六、课程设计总结 (7) 七、测试数据 (7) 八、参考书目 (7) 一、需求分析说明 1.1最小生成树总体功能要求 在n个城市之间建设网络，只需保证连通即可，求最经济的架设方法。存储结构采用多种。求解算法多种。 1.2基本功能 在n个城市之间建设网络，只需要架设n-1条线路，建立最小生成树即可实现最经济的架设方法。 程序可利用克鲁斯卡尔算法或prim算法生成最小生成树。 1.3 模块分析 主模块：用于生成界面和调用各个子模块。 Kruscal模块：以kruscal算法实现最小生成树。 Prim模块：以prim算法实现最小生成树。 邻接表模块：用邻接表方式存储图。 邻接表输出模块：输出邻接表。 邻接矩阵模块：用邻接矩阵方式存储图。 邻接矩阵模块：输出邻接矩阵。 二、概要设计说明 2.1设计思路 问题的解决分别采用普利姆算法以及克鲁斯卡尔算法。 1) 普利姆算法就是先选择根，把它放入一个集合U中，剩余的顶点放在集合V中。然后选择该顶点与V中顶点之间权值最小的一条边，以此类推，如果达到最后一个则返回上一个顶点。 2) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。 软件综合课程设计 最小生成树问题 学生成绩管理 二〇一四年六月 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在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)取代后者作为候选边。 数据结构课程设计报告题目：最小生成树问题 院（系）：计算机工程学院 学生姓名: 班级：学号: 起迄日期: 指导教师: 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 ) 数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (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、功能模块图 最小生成树模型与实验 第六章 最小生成树模型与实验 树是图论中的一个重要概念，由于树的模型简单而实用，它在企业管理、线路设计等方面都有很重要的应用。 §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 的连通的。 数学物理文科 理校教学校长 以邻接矩阵存储的图类型构造n个城市连接的最小生成树代码： #include scanf("%d" ,&(G->vexs[i])) ; /* 输入顶点信息，建立顶点表*/ } for (i=0 ;i 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次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） 《数据结构课程设计》题目二：最小生成树的构建 学院：XXXXXXXXXXX 班级：XXXXXXXXXXX 学号：XXXXXXXXXXX 姓名：XXXXXXXXXXX 设计时间：XXXXXXXXXXX 目录： 1.需求分析--------------------------------------------- 1 2.课题设计内容--------------------------------------- 1 (1)课程设计基本流程------------------------------------------ 1 (2)详细设计说明------------------------------------------------1 (3)界面操作流程图：----------------------------------------- 2 (4)主要程序------------------------------------------------------3 (5)运行结果截图----------------------------------------------- 5 3.得意之处--------------------------------------------- 6 4.设计实践过程中的收获与体会------------------ 6 5.设计目前存在的问题------------------------------ 7 6.主要参考文献-------------------------------------- 7 一、需求分析 本课程主要是完成一个最小生成树的构建，要求用克鲁斯卡尔算法或者普利姆算法求网的最小生成树（此程序我用的是 普利姆算法），并输出各条边及他们的权值。要求用户在使用 时可以准确输入顶点及每个顶点的关系，运算出可以建立的关 系网，最后利用普利姆算法准确输出最短路径。 二、课程设计内容 1、课程设计基本流程： 关于此课程的设计，是从设计要求入手的。根据对知识的掌握程度，我选择了用普利姆算法进行设计。 根据实验要求，我定义了一个prims类，在类中定义一个私有成员函数和一个公有成员函数。定义相关变 量和相关函数，并完善程序。 2、详细设计说明： 首先在私有成员private中定义节点个数n、图中边的个数g，树的边的个数t，源节点s。定义二维数组 graph_edge[99][4]和tree_edge[99][4]，分别为图的边 和树的边。因为普利姆算法是把图分为两部分进行运算， 所以我定义了T1[50],t1为第一部分， T2[50],t2为第 二部分。在公有成员public中定义输入函数input()、 算法函数algorithm()、输出函数output()。 1 武 夷 学 院 课程设计报告 课程名称： 数据结构 设计题目： 最小生成树的应用 学生班级： 09计科2班 学生姓名： 蒋家权，陈相财，吴继伟，梁丽春 指导教师： 林丽惠 完成日期： 2011-1-19 课程设计项目研究报告 目录 一、问题分析和任务定义....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................... - 1 - 三、测试数据........................................................................................................... - 2 - 四、算法思想........................................................................................................... - 3 - 五、模块划分........................................................................................................... - 4 - 六、算法设计与分析............................................................................................... - 7 - 七、源程序............................................................................................................. - 11 - 八、测试数据......................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 - 十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 - 构造可以使N个城市连接的最小生成树 专业：_________ 班级：_________ 姓名：_________ 学号：_________ 完成日期：_________ 【问题描述】 给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并计算得到的最小生成树的代价。 【设计需求及分析】 1、城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义， 若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。 2、要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。 3、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）。 【设计功能的实现】（用C或C++语言描述） #include int main(int argc, char * argv[]);//主函数 Status LocateVex(MGraph G, VertexType v);//判断城市v 在网G 中的位置Status CreateUDN(MGraph &G);//创建网G 的邻接矩阵 void DisplayNet(MGraph G);//以邻接矩阵的形式显示网G void MiniSpanTree_KRUSKAL(MGraph G);//最小生成树的Kruskal 算法void MiniSpanTree_PRIM(MGraph G, VertexType u);//最小生成树的Prim 算法Status Minimum(closedge closeEdge, int n);//Prim 算法中求下一个城市的函数void DeleteInfo(MGraph &G);//释放堆内存上动态申请的空间 int main(int argc, char * argv[]) { CreateGraph(G); DisplayNet(G); MiniSpanTree_KRUSKAL(G); MiniSpanTree_PRIM(G, G.vexs[0]); DeleteInfo(G); cout< 最小生成树的算法 王洁 引言： 求连通图的最小生成树是数据结构中讨论的一个重要问题．在现实生活中，经常遇到如何得到连通图的最小生成树，求最小生成树不仅是图论的基本问题之一 ,在实际工作中也有很重要的意义，,人们总想寻找最经济的方法将一个终端集合通过某种方式将其连接起来 ,比如将多个城市连为公路网络 ,要设计最短的公路路线;为了解决若干居民点供水问题 ,要设计最短的自来水管路线等.而避开这些问题的实际意义 ,抓住它们的数学本质 ,就表现为最小生成树的构造。下面将介绍几种最小生成树的算法。 一，用“破圈法”求全部最小生成树的算法 1 理论根据 1.1 约化原则 给定一无向连通图 G =（V ,E ）（ V 表示顶点，E 表示边），其中 V={ 1v , 2v ,3v …… n v },E= { 1e , 2e , 3e …… n e }对于 G 中的每条边 e ∈ E 都赋予权ω（i e ）>0，求生成树 T = （V ,H ），H ? E ，使生成树所有边权最小，此生成树称为最小生成树． （1） 基本回路 将属于生成树 T 中的边称为树枝，树枝数为n -1，不属于生成树的边称为连枝．将任一连枝加到生成树上后都会形成一条回路．把这种回路称为基本回路，记为()cf e 。 基本回路是由 T 中的树枝和一条连枝构成的回路． （2） 基本割集 设无向图 G 的割集 S （割集是把连通图分成两个分离部分的最少支路集合） ，若 S 中仅包含有T 中的一条树枝，则称此割集为基本割集，记为()S e 。 基本割集是集合中的元素只有一条是树枝，其他的为连枝． （3） 等长变换 设T=(V,H),为一棵生成树，e ∈ H, 'e ∈ E, 'e ? H,当且仅当'e ∈()cf e ，也就是说 e ∈()S e ，则'T =T ⊕{e, ' e }也是一棵生成树。当()e ω='()e ω时，这棵生成树叫做等长变换。 等长变换就是从基本回路中选取与树枝等权边，并与此树枝对换后形成的生成树． 根据以上定理得出2个结论：①若在某个回路C 中有一条唯一的最长边，则任何一棵最小生成树都不含这条边；②若在某个边 e 的割集中有一条唯一最短边，则每棵生成树中都必须含这条边．由上面结论可以得到唯一性：若图 G 中的生成树T = （V ,H ）是唯一的一棵最小生成树，当且仅当任意一连枝e ∈ H, ' e ∈ E 都是其基本回路中唯一最长边，任意一条树边 e 都是其基本割集()S e 中的唯一最短边． 电子科技大学 实验报告 学生姓名：XXX 学号：2013220501018指导教师：刘峤 实验地点：信软楼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）假定每对顶点表示图的一条边，每条边对应一个权值； 数据结构课程设计 系别电子信息系 专业计算机科学与技术 班级学号 姓名 指导教师 成绩 2012年7 月12日 目录 1 需求分析 (2) 2 概要设计 (2) 2. 1抽象数据类型定义 (2) 2 . 2模块划分 (3) 3 详细设计 (4) 3. 1数据类型的定义 (4) 3. 2主要模块的算法描述 (6) 4 调试分析 (10) 5 用户手册 (10) 6 测试结果 (11) 7 附录(源程序清单） (13) 参考文献 (20) 一、需求分析 1.要在n个城市之间建设通信网络，只需要架设n-1条线路即可，而要以最低的经济代价建设这个通信网，就需要在这个网中求最小生成树。 (1)利用克鲁斯卡尔算法求网的最小生成树。 (2)实现教科书 6.5 节中定义的抽象数据类型 MFSet 。以此表示构造生成树过程中的连通分量。 (3)输入顶点个数，输入顶点序号（用整型数据[0，1，2，……，100]表示），输入定点之间的边的权值（整型数据）。系统构造无向图，并求解最小生成树。 (4)以图形和文本两种形式输出最小生成树。 2.程序执行的命令包括： (1)随机生成一个图； (2)输入图坐标信息； (3)以文本形式输出最小生成树； (4)以图形形式输出最小生成树； (5)以图形形式输出构造的图； (6)结束。 3.测试数据 (1)用户输入需要构造的图形顶点个数，假设顶点个数为4； (2)C语言函数随机生成的图形，顶点分别为a,b,c,d,权值分别为： ab=75,ac=99,ad=80,bc=33,bd=93,cd=19； (3)最小生成树边的权值分别为:ab=75,bc=33,cd=19; (4)结束。 二、概要设计 1. 图的抽象数据类型定义 ADT Gragh{ 数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R＝{VR} VR＝{数据结构课程设计图的遍历和生成树求解
数据结构-第六章-图-练习题及答案详细解析(精华版)
用Prim算法构造最小生成树
最小生成树问题
最小生成树数据结构课程设计报告
最小生成树问题
最小生成树实验报告
最小生成树问题课程设计报告
最小生成树模型与实验
以邻接矩阵存储的图类型构造n个城市连接的最小生成树
最小生成树算法分析
数据结构课程设计最小生成树的构建实验报告
数据结构课程设计报告(最小生成树完整版)
构造可以使N个城市连接的最小生成树
最小生成树的算法
数据结构实验报告-最小生成树
最小生成树问题,图形输出最小生成树