数据结构课程设计（最小生成树）
获取源码在文末
本来是给一个同学做的课设作业
现在分享给大家
希望大家多加支持
1、设计目的和要求
（1）、实验题目：给定一个地区的n个城市间的距离网，用Prim算法或Kruskal算法建立最小生成树，并得到的最小生成树的代价。
（2）、实验要求：
1、城市间的距离网采用的邻接矩阵表示，邻接矩阵的存储结构定义采用课本中给出的定义，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值。要求在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树的代价。
2、表示城市间距离网的邻接矩阵（要求至少6个城市，10条边）
3、最小生成树中包括的边及其权值，并显示得到的最小生成树的代价。
2、设计内容及步骤
（1）、问题分析及采用数据结构：
1、根据题目要求，首先要建立城市间的距离网，并且采用邻接矩阵表示，则使用到的数据结构是图的形式。图的作用是实现城市的距离网，采用顺序存储结构。数据结构可以用如下表示：
typedefstruct{SeqListVertices;//存放图中各结点intedge[MaxVertices][MaxVertices];//存放权值的二维数组intnum_edge;//图的边数}Graph;
2、完成距离网的存储后，就要用Prim算法和Kruskal算法来实验最小生成树。
Prim算法是以结点为最小生成树的开始，再找其相应的最小边来实现。可以设计为两个参数，一个参数为图G，另一个参数是通过函数得到的最小生成树结点数据和相应结点的边的权值数据closeVertex.所以其数据结构可以定义如下：
typedefstruct{DataTypevertex;intweight;}TreeNode;
Kruskal算法是以图中最小边开始慢慢寻找最小生成树的代价。所以它的结构包含最小边及边的两结点的下标，标置位是判断结点是否已经参加比较。其结构可以定义如下：
typedefstruct{introw;//行下标intcol;//列下标intweight;//边权值intflag;//标志位}TreeEdge;//边信息
（2）算法设计
1、首先设计的是顺序表，用来存放图中的各个结点的信息。这样可以看到结点的多少，又可以知道每个结点对应的下标，便于操作。
2、图的操作：图的操作主要体现在要实现城市的距离网的信息，所以其操作有：初始化，插入结点、插入边。
A、初始化GraphInitiate(G,n);初始化图G，n个结点个数。
B、插入结点InsertVertex(G,vertex)；在图中插入结点vertex.
C、插入结点InsertEdge(G,v1,v2,weight)；在图中插入边v1,v2,边v1,v2的权值为weight.
3、prim算法的设计:Prim算法的函数设计为voidPrim(GraphG);
A、函数中首先定义一个数组lowCost，数组过犹不及lowCost[v]中保存了集合U中结点u(i)与集合VU中结点v(j)的所有边中当前具有最小权值的边u,v.
B、集合U的初值为U={序号为0的结点}。lowCost的初始值为邻接矩阵数组中第0行的值，这样初始时lowCost中就存放了从集合U中结点0到集合VU中各个结点的权值。
C、每次从lowCost中寻找具有最小权值的边，根据lowCost的定义，这样的边其弧头结点必然为集合U中的结点，其弧尾结点必然为集合VU中的结点为。当选到一条这样的边(u,v)时，就保存其结点数据和权值的数据到参数closeVertex中，并将lowCost[v]置-1。
D、当结点v从集合VU加入到集合U后，若存在一条边u,v，u是集合U的结点，v是集合VU的结点，且边u,v较原先lowCost[v]的权值更小，则用这样的权值修改原先lowCost[v]中的相应权值。
3、Kruskal算法的设计:Kruskal算法函数设计为voidKruskal(GraphG).
A、首先将所有有权值（MaxSizeweight0）的边存放到lowCost数组里。并且标置位flag置0。
B、根据lowCost存放所有的结点来寻找最小的权值。若找到刚先保存起来，标置位为1。并要判断是否符合。
C、将B中找到的边的两个结点的下表与顺序表中的数据比较，如果没有则进表保存，如果两个都有则说明此边会与前面找到的最小边构成了回路，不符合。
D、重复B，C操作。
下载