建立n个城市间的最小生成树
目录
设计要求........................................................ - 1 - 问题重述........................................................ - 1 - 基本要求........................................................ - 2 - 概要设计........................................................ - 2 - 2.1 主界面的设计............................................... - 2 - 2.2 存储结构的设计本系统...................................... - 3 - 2.2.1 顺序表的基本概念......................................... - 3 - 2.2.2 图的邻接矩阵的基本概念................................... - 4 - 2.2.3 最小生成树的基本概念..................................... - 5 - 模块设计........................................................ - 6 - 3.1 n个城市连接的最小生成树................................... - 6 - 3.2 模块作用用途中的顶点表示................................... - 6 - 3.3 模块及模块调用关系......................................... - 6 - 3.2.1 “SeqList.h”顺序存储结构存放结点信息..................... - 7 - 3.2.2“AdjMGraph.h”邻接矩阵存储结构存放边的信息................ - 7 - 3.2.3 最小生成树的生成过程..................................... - 8 - 3.3 系统子程序及功能设计........................................ - 9 - 3.3.1 定义数组................................................. - 9 - 3.3.2 定义集合................................................ - 10 - 3.3.3 定义lowcost ............................................ - 10 - 3.3.4 修改权值................................................ - 10 - 3.3.5 带权图.................................................. - 10 - 3.4 算法描述.................................................. - 12 - 3.4.1 流程图.................................................. - 12 - 测试结果及分析................................................. - 14 - 测试结果....................................................... - 14 - 4.2 结果分析.................................................. - 16 - 4.3 错误分析.................................................. - 16 - 源程序......................................................... - 17 -
1 设计要求
1.1 问题重述
选择6-10个城市模拟在城市之间建立通信网络，只需要架设通信路线就可以，以最低的经济花费建设通信网，即用Prim算法或Kreskas算法生成一个网的最小生成树，并计算得到的最小生成树的代价。
1.2 基本要求
◆城市间的距离网采用邻接矩阵表示，邻接矩阵的存储结构定义采用课本上的
定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括那些城市间的道路，并显示得到的最小生成树的代价。
◆表示城市间距离网的邻接矩阵
◆最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
2 概要设计
为了实现以上功能，可以从以下主界面构造、存储结构采用、系统功能设置等三个方面进行分析设计。将图的结点信息存放在一个顺序表中，图的边信息存储在一个二维数组edge[MaxVertices][MaxVertices]中，这样就实现了用邻接矩阵存放城市间的距离网。在Prim算法的函数用两个参数，一个是图G为邻接矩阵存储结构的图；另一个是通过函数得到的最小生成树的结点数据和相应结点的边的权值数据closeVertex.
2.1 主界面的设计
为了首先需要设计一个主界面子程序，以链接系统的各项子功能运行界面如图1所示
图1
2.2 存储结构的设计本系统
采用图结构类型，存储抽象n个城市模拟在城市之间建立通信网络，其中各城市用邻接矩阵类型存储。
2.2.1 顺序表的基本概念
当采用C语言描述数据结构时问题时，实现顺序存储结构的方法是使用数组。数组把线性表的数据元素存储在一块连续地址空间的内存单元内，这样，线性表中逻辑上相邻的数据元素在物理存储地址上也相邻，数据元素间的逻辑上的前驱，后继逻辑关系就表现在数据元素的存储单元的物理前后位置关系上。
数组有静态数组和动态数组两种。静态数组存储空间的申请和释放有系统自
动完成，动态数组存储空间的申请和释放由用户调用系统函数完成。无论是静态数组还是动态数组，其功能都是向系统申请一块地址连续的有限空间，只是申请的方法不同，顺序表一般采用静态数组方法实现数据元素的存储。
顺序表定义结构体如下：
Typedef struct
{
DataType list[Maxsize];
Int size;
}SeqList;
其中，DataType为数组（即数据元素）的数据类型，Maxsize表示数组的最大元素个数，list表示顺序表的数组名，size表示顺序表中当前存储的数据元素个数，它必须满足size<= Maxsize，SeqList是该结构体的名称。
2.2.2 图的邻接矩阵的基本概念
由图的定义可知，图的信息包括两部分，图中结点的信息和描述之间关系的边的信息。结点信息的描述问题，是一个简单的表存储结构问题。对于一个有n 个节点的图，由于每个结点都可能与其他n-1个结点成为邻接结点，所以边之间关系的描述问题，实际上是一个n*n矩阵的计算机存储表示问题。
在图的邻接矩阵存储结构中，节点信息使用一维数组存储，边的邻接矩阵使用二维数组存储，无向图的邻接矩阵一定是对称矩阵。
当图中结点数目较小且边较多时，采用图的邻接矩阵存储结构效率较高；当图中结点数目较大且边的数目远小于相同结点的完全图的边数时，采用图的邻接表存储结构效率较高。
图的结构体定义如下：
typedef struct
{
SeqList Vertices;
int edge[MaxVertices][ MaxVertices];
int numOfEdges;
}AdjMGraph;
2.2.3 最小生成树的基本概念
一个有n个结点的连通图的生成树是原图的极小连通子图，他包含原图中的所有n个结点，并且保持图连通的最少的边。
由生成树的定义可知：（1）若再生成树中删除一条边就会使该生成树因变成非连通图而不再满足生成树的定义；（2）若在生成树中增加一条边就会使生成树中存在回路而不再满足生成树的定义；（3）一个连通图的生成树可能得到不同的生成树。使用不同的寻找方法可以得到不同的生成树。另外，从不同的初始结点出发也可以得到不同的生成树。
从生成树的定义显然可以证明，对于有n个结点的无向连通图，无论他的生成树的形状如何，一定有且只有n-1条边。
如果无向连通图是一条带权图，那么他的所有生成树中必有一颗边的权值总和为最小的生成树，称这棵生成树为最小代价生成树，简称最小生成树。
从最小生成树的定义可知，构造有n个结点的无向连通带权图的最小生成树必须满足以下三点：
（1）构造的最小生成树必须包括n个结点
（2）构造的最小生成树中有且只有n-1条边
（3）构造的最小生成树中不存在回路
假设G=(V,E)为一个带权图，其中V为带权图中结点的集合，E为带权图中的边的权值集合。设置两个信新的集合U和T，其中U用于存放带权图G的最小生成树的结点的集合，T用于存放带权图G的最小生成树边的权值的集合。
普利姆算法思想是：令集合U的初值为U{u0}（即假设构造最小生成树时从结点u0开始），集合T 的初值为T={}。从所有结点u属于U和结点v属于V
但不属于U的带权边中选出具有最小权值的边（u，v），将结点v加入集合U中，将边（u，v）加入集合T中。如此不断重复，当U=V时，最小生成树便构造完毕。此时集合U中存在着最小生成树的结点，集合T中存放着最小生成树边的权值集合。
3 模块设计
3.1 n个城市连接的最小生成树
选择6-10个城市模拟在城市之间建立通信网络，只需要架设通信路线就可以，以最低的经济花费建设通信网，即生成一个网的最小生成树，各城市分别用字母A—G表示。
3.2 模块作用用途中的顶点表示
头文件用来存放邻接矩阵存储结构定义以及相应的图的操作函数与图的创建及普里姆函数的设计。主函数“prim.cpp”来测试程序。
3.3 模块及模块调用关系
3.2.1 “SeqList.h”顺序存储结构存放结点信息
a.初始化ListInitiate(L)：初始化线性表L。
b.求当前数据元素个数ListLength（L）：函数返回线性表L的当前数据元素的个数
c.插入数据元素ListInsert(L,i,x)：在现象表L的第i个数据前插入数据元素x，如果插入成功返回1，插入失败返回0。其约束条件为0≤i≤ListLength（L），即若i=0，表示在第一个元素之前插入数据元素x，若i= ListLength（L）-1，表示在最后一个元素前插入数据元素x，若i= ListLength（L），表示在最后一个元素之后插入数据元素x。
d.删除数据元素ListDelete(L,i,x)：删除线性表L的第i个元素，所删除的数据元素由输出参数x带回。如果删除成功返回1，删除失败返回0，其约束条件为0≤i≤ListLength（L）-1，若i=0，表示删除第一个数据元素，若i= ListLength （L）-1，表示删除最后一个数据元素。
e.取数据元素ListGet(L,i,x)：取线性表L的第i个数据元素，所取得数据元素由输出参数x带回，取元素成功返回1，取元素失败返回0。其约束条件为0≤i≤ListLength（L）-1，若i=0，表示取第一个数据元素，若i= ListLength（L）-1，表示取最后一个数据元素。
3.2.2“AdjMGraph.h”邻接矩阵存储结构存放边的信息
a.初始化图G，n为结点个数。
Initiate(AdjMGraph *G, int n)
b.在图G中插入结点vertex
InsertVertex(AdjMGraph *G, DataType vertex)
c.在图G中插入边
InsertEdge(AdjMGraph *G, int v1,int v2,int weight)
d.在图G中删除边
DeleteEdge(AdjMGraph *G,int v1,int v2)
e.删除图G中的结点v以及与该节点相关的所有边
DeleteVerten(AdjMGraph *G,int v)
f.在图G中寻找序号为v的结点的第一个邻接结点
GetFirstVex(AdjMGraph G,int v)
g.在图G中寻找v1结点的邻接结点v2的下一个邻接结点.
GetNextVex(AdjMGraph G,int v1,int v2)
3.2.3 最小生成树的生成过程
下图中给出了用普利姆算法构造最小生成树的过程。(a)为一个有7个结点10条边的无向边的带权图。初始集合U={A}，集合V\U={B，C，D，E，F，G}，T={}，如图（b）所示，此时，存在两条一个结点在U、另一个结点在集合V\U 中的边，具有最小权值的边（A，B），权值为50，把结点B从V\U加入到集合U中，把边（A，B）加入到T中，如图（c）所示，在所有以u为集合U中结点、v为集合V\U中结点的边（u，v）中寻找具有最小权值的边（u，v），寻找到的是（B,E），权值为40，把结点E从集合V\U中加入到集合U中，把边（B,E）加入到T中，如图（d）所示，随后依次从集合V\U加入到集合U中的结点为D，F，G，C，依次加入到T中的边为（E，D），权值为50，（D,F）权值为30，（D,G），权值为42，（G，C），权值为45，分别如图（e）（f）（g）（h）所示，最后得到的图（h）就是从A结点出发构造的最小生成树。
(a) (b) (c)
(d) (e) (f)
(g) (h)
3.3 系统子程序及功能设计
3.3.1 定义数组
函数中定义一个临时数组lowcost，数组元素lowcost[v]中保存了集合中结点ui与集合V\U中结点uj的所有边中当前具有最小权值的边（u，v）。
3.3.2 定义集合
集合U的初值为U={序号为j的结点}。Lowcost的初始值为邻接矩阵数组中第j行的值，这样初始时lowcost中就存放了从集合U中的结点j到V\U中各节点的权值。
3.3.3 定义lowcost
每次从lowcost中寻找具有最小权值的边，根据lowcost的定义，这样的边其弧头结点必然为集合U中的结点，其弧尾结点必然为集合V\U中的结点，当选到这样的边（u，v）时，就保存其结点数据和权值数据到参数closevertex中，并将lowcost[v]置为-1，表示点v加入到了集合U中。
3.3.4 修改权值
当节点v从集合V\U加入到集合U后，若存在一条边（u，v），u是集合U 的结点，v是集合V\U的节点，且边（u，v）较原先lowcost[v]的权值更小，则用这样的权值修改原先lowcost[v]中相应权值。
3.3.5 带权图
以图（a）所示的带权图为例，调用普利姆函数时数组lowcost的动态变化过程如下所示。其中第一图表示初始结点0在集合U中，结点0到其他结点有两条边，权值分别为50和60。
第二图表示结点1加入到集合U中，结点1加入集合U后，因结点1到结点3存在一条权值为65的边，该权值小于原先的无穷大，所以需要把，lowcost[3]
改为65，因结点1到结点4存在一条权值为40的边，该权值小于原先的无穷大，所以需要把lowcost[4]改为40，第三图表示结点4加入到集合U后的状态，第四图表示结点3加入集合u后的状态，第五图表示结点5加入到集合U后的状态，第六图表示结点6加入到集合U后的状态，最后一图表示结点3加入到集合U 后的状态。
lowcost lowcost lowcost lowcost lowcost
lowcost lowcost
3.4 算法描述
3.4.1 流程图
图2 创建邻接矩阵流程图
Prim算法流程图
4 测试结果及分析4.1测试结果
4.2 结果分析
当从一个第一个顶点开始以此作为生成树的初始状态，然后找出与其之间权值最小的顶点2并把顶点2添加到该生成树中，以此类推找出与顶点2之间权值最小的顶点。再把找出的顶点添加到生成树中直到最后一个顶点添加到生成树上是得到所求的生成数即为最小生成树。
4.3 错误分析
在本次课程设计的过程中，出现诸多错误，比如分号没有打以及一些错打和少打的情况，在此不做一一的介绍，只介绍一些较大的错误。
1、本应从任一节点接入均可以构造最小生成树，所以在运行普利姆算法时需要在创建数组之前输入一个城市的结点序号，在开始时，只是将数组中的j写入，并没有赋初始值，所以在程序运行时出现了错误。
2、在成功运行从任意结点构造生成树后，由于需要关闭运行框后才能进行
下一次的构造，这是在实际运行中是不允许的，所以要求在程序开始时加一个判断语句，只要在执行完后进行是否继续的判断就可以直接再次运行普利姆算法而不需要关闭运行框后再重新运行程序。
5 源程序
头文件：AdjMGraph.h
typedef int DataType;
typedef struct
{
DataType list[MaxSize];
int size;
}SeqList;
void ListInitiate(SeqList *L)
{
L->size=0;
}
int ListLength(SeqList L)
{
return L.size;
}
int ListInsert(SeqList *L,int i,DataType x)
{
int j;
if(L->size>=MaxSize)
{
printf("顺序表已满无法插入！\n");
return 0;
}
else if(i<0||i>L->size)
{
printf("参数i不合法！\n");
return 0;
}
else
{
for(j=L->size;j>i;j--)
L->list[j]=L->list[j-1];
L->list[i]=x;
L->size++;
return 1;
}
}
int ListDelete(SeqList *L,int i,DataType*x) {
int j;
if(L->size<=0)
{
printf("顺序表已空无数据可删！\n");
return 0;
}
else if(i<0||i>L->size-1)
{
printf("参数i不合法！\n");
return 0;
}
else
{
*x=L->list[i];
for(j=i;j
L->list[j]=L->list[j+1];
L->size--;
return 1;
}
}
int ListGet(SeqList L,int i,char*x)
{
if(i<0||i>L.size-1)
{
printf("参数i不合法！\n");
return 0;
}
else
{
*x=L.list[i];
return 1;
}
}
typedef struct
{
SeqList Vertices; /* 存放结点的顺序表 */
int edge[MaxVertices][MaxVertices]; /* 存放边的邻结矩阵地 */
int numOfEdges; /* 边的条数 */
}AdjMGraph; /* 图的结构体定义 */
void Initiate(AdjMGraph *G, int n) /* 初始化*/
{
int i,j;
for(i=0;i for(j=0;j { if(i==j) G->edge[i][j]=0; else G->edge[i][j]=MaxWeight; } G->numOfEdges=0; /* 边的条数置为0 */ ListInitiate(&G->Vertices); /*顺序表初始化 */ } void InsertVertex(AdjMGraph *G, DataType vertex) /* v在图G 中插入结点vertex */ { ListInsert(&G->Vertices, G->Vertices.size,vertex); /* 顺序表尾插入 */ } void InsertEdge(AdjMGraph *G, int v1,int v2,int weight) /*在图G中插入边 { if(v1<0 || v1>G->Vertices.size || v2>G->Vertices.size||v2<0) { printf("参数v1或v2越界出错! \n"); exit(1); } G->edge[v1][v2]=weight; G->numOfEdges++; } void DeleteEdge(AdjMGraph *G,int v1,int v2) /*在图G中删除边 { if(v1<0 || v1>G->Vertices.size || v2<0 || v2>G->Vertices.size || v1==v2) { printf("掺数v1或v2越界出错! \n"); exit(1); } if(G->edge[v1][v2]==MaxWeight || v1==v2) { printf("该边不存在!\n"); exit(0); } G->edge[v1][v2]=MaxWeight; G->numOfEdges--; } void DeleteVertex(AdjMGraph *G,int v) /*删除结点V*/ { int n=ListLength(G->Vertices),i,j; DataType x; for(i=0;i if((i==v||j==v) && G->edge[i][j]>0 && G->edge[i][j] G->numOfEdges--; /*计算被删除边*/ for(i=v;i for(j=0;j G->edge[i][j]=G->edge[i+1][j]; for(i=0;i for(j=v;j G->edge[i][j]=G->edge[i][j+1]; ListDelete(&G->Vertices,v,&x); } int GetFirstVex(AdjMGraph G,int v) /*在图G中寻找序号为v的结点的第一个邻接结点*/ /*如果这样的邻接结点存在，返回该邻接结点的序号；否则，返回-1*/ 图 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条边，则。 榆林学院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) 克鲁斯卡尔算法就是写出所有的顶点，选择权最小的边，然后写出第二小的，以此类推，最终要有一个判断是否生成环，不生成则得到克鲁斯卡尔的最小生成树。 数据结构课程设计 目录 一. 设计目的.................................................................................................. 错误！未定义书签。 二. 设计内容 (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、功能模块图 软件综合课程设计 最小生成树问题 学生成绩管理 二〇一四年六月 最小生成树问题 一、问题陈述 最小生成树问题 设计要求：在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 ) /*分别利用prim算法和kruskal算法实现求图的最小生成树*/ #include if(i==j) GA[i][j]=0; else GA[i][j]=MaxValue; printf("输入%d条无向带权边",e); for(k=0;k 最小生成树算法分析 一、生成树的概念 若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次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） 以邻接矩阵存储的图类型构造n个城市连接的最小生成树代码： #include scanf("%d" ,&(G->vexs[i])) ; /* 输入顶点信息，建立顶点表*/ } for (i=0 ;i 《数据结构课程设计》题目二：最小生成树的构建 学院：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 算法设计与分析课程设计报告 学院计算机科学与技术 专业计算机科学与技术 年级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个顶点的连通网可以建立许多不同的生成树，每一个生成树都可以是一个通信网。现在要选择这样一棵生成树，也就是使总的代价最小。这个问题便是构造连通网的最小代价生成树（简称最小生成树）的问题。最小生成树是指在所有生成树中，边上权值之和最小的生成树，另外最小生成树也可能是多个，他们之间的权值之和相等。一棵生成树的代价就是树上各边的代价之和。而实现这个运算的经典算法就是普利姆算法。 构造可以使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< 编号： 审定成绩： 重庆邮电大学研究生堂下考试答卷 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 算法和破圈法，本文分别用这三种算法来实现最小生成树的构造。 求出下图的最小生成树 解：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 武 夷 学 院 课程设计报告 课程名称： 数据结构 设计题目： 最小生成树的应用 学生班级： 09计科2班 学生姓名： 蒋家权，陈相财，吴继伟，梁丽春 指导教师： 林丽惠 完成日期： 2011-1-19 课程设计项目研究报告 目录 一、问题分析和任务定义....................................................................................... - 1 - 二、实现本程序需要解决的问题如下................................................................... - 1 - 三、测试数据........................................................................................................... - 2 - 四、算法思想........................................................................................................... - 3 - 五、模块划分........................................................................................................... - 4 - 六、算法设计与分析............................................................................................... - 7 - 七、源程序............................................................................................................. - 11 - 八、测试数据......................................................................................................... - 14 - 九、课程设计项目进度表及任务分配表及任务分配表..................................... - 16 - 十、设计心得......................................................................................................... - 17 -十、参考书目......................................................................................................... - 18 - 一、实验目的：掌握图的存储表示和以及图的最小生成树算法。 二、实验内容： 1.实现图的存储，并且读入图的内容。 2.利用克鲁斯卡尔算法求网络的最小生成树。 3.实现构造生成树过程中的连通分量抽象数据类型。 4.以文本形式输出对应图的最小生成树各条边及权值。 三、实验要求： 1．在上机前写出全部源程序； 2．能在机器上正确运行程序； 3．用户界面友好。 需求分析： 1、利用克鲁斯卡尔算法求网的最小生成树； 2、以用户指定的结点为起点,分别输出每种遍历下的结点访问序列； 3、输入为存在边的顶点对，以及它们之间的权值；输出为所得到的邻接矩 阵以及按权排序后的边和最后得到的最小生成树； 克鲁斯卡尔算法：假设WN=(V,{E}) 是一个含有n 个顶点的连通网，按照构造最小生成树的过程为：先构造一个只含n 个顶点，而边集为空的子图，之后，从网的边集 E 中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至只有一棵树，也即子图中含有n-1条边为止。 测试数据： 自行指定图进行运算 四、详细设计 源程序 #include数据结构-第六章-图-练习题及答案详细解析(精华版)
最小生成树问题
最小生成树数据结构课程设计报告
最小生成树问题课程设计报告
最小生成树问题
最小生成树实验报告
分别利用prim算法和kruskal算法实现求图的最小生成树
最小生成树算法分析
以邻接矩阵存储的图类型构造n个城市连接的最小生成树
数据结构课程设计最小生成树的构建实验报告
最小生成树问题的算法实现及复杂度分析—天津大学计算机科学与技术学院(算法设计与分析)
构造可以使N个城市连接的最小生成树
最小生成树在旅游路线选择中的应用概况
求出下图的最小生成树
数据结构课程设计报告(最小生成树完整版)
离散数学--最小生成树实验报告
- 构造可以使n个城市连接的最小生成树课案
- 构造可以使n个城市连接的最小生成树
- 最小生成树问题课程设计报告
- n个城市最小生成树实验报告
- 图论论文：最小生成树算法城市高速公路问题中的应用
- 最小生成树
- 建立n个城市间的最小生成树
- 构造可以使N个城市连接的最小生成树
- 数据结构,N个城市连接费用最小
- Prim算法最小生成树(C语言)
- 构造n个城市连接的最小生成树
- 最小生成树问题
- n个城市最小生成树实验报告材料
- 最小生成树数据结构实验报告
- 构造可以使N个城市连接的最小生成树
- 最小生成树
- 以邻接矩阵存储的图类型构造n个城市连接的最小生成树
- 构造可以使n个城市连接最小生成树
- 构成可以使n个城市连接的最小生成树
- 最小生成树问题