算法与数据结构课程设计--图的最短路径

《算法与数据结构课程设计--图的最短路径》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图的最短路径一、问题描述最小生成树是一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有个结点，并且有保持图连通的最小的边，最小生成树在实际问题中具有一定的应用价值，如在城市之间建设网络，要保证网络的连通性，求最经济的设计方法。求解最小生成树时，可以采用普里母算法和克鲁斯卡尔算法。二、基本要求1、选择合适的储存结构，完成网的建立；2、利用普里母算法求网的最少生成树，并输出结果；3、利用克鲁斯卡尔求网的最少生成树，并输出结果；4、采用邻接矩阵和邻接表两种储存结构；三、测试数据对右图进行测试右图是6个顶点的10个边的

2、连通图六个顶点分别是v1v2v3v4v5v6边和边上的权植分别是v1v26v1v31v1v45v2v35v2v53v3v45v3v56v3v64v4v62v5v66wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802四、算法思想克鲁斯卡尔算法思想是：假设连通图N=（V，{E}），则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去

3、此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。普里母算法思想是：假设N=（Ｖ，｛Ｅ｝）是连通图，ＴＥ是Ｎ上最小生成树中边的集合。算法从Ｕ＝｛u0｝（u0∈V），TE={}开始，重复执行下述操作：在所有u∈U，v∈V—U的边（u，v）∈E中找一条代价最小的边（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有ｎ－１条边，则Ｔ＝（Ｖ，｛ＴＥ｝）为Ｎ的最小生成树。为实现这个算法需附设辅助数组closedge,以记录从U到V-U具有最小代价的边。对每个顶点vi∈V-U，在辅助数组中存

4、在一个相应分量closedge[i-1]，它包括两个域，其中lowcost储存该边的权。显然，closedge[i-1].lowcost=Min{cost(u,vi)

5、u∈U},vex∈U},vex域存储该边依附的在U中的顶点。五、模块克鲁斯卡尔算法和普里母算法都要用到以下的算法intLocateVex(MgraphG,Vertexu)，矩阵求点u所在位置；voidCreateGraph(Mgraph/ALGraph&G)，建立带权邻接矩阵/邻接表的结构；voidkruskal2(ALGraphG)，邻接链表的克鲁斯卡尔算法；vo

6、idkruskal(MGraphG)，邻接矩阵的克鲁斯卡尔算法；intminimum(ALGraph/MGraphG,structarrywq[])，邻接表/邻接矩阵求最小的权值；voidMiniSpanTree_PRIM1(ALGraphG,VertexTypeu)，邻接表的普里姆算法；voidMiniSpanTree_PRIM2(MGraphG,VertexTypeu)，邻接矩阵的普里姆算法。六、数据结构//(ADT)1、邻接表的储存结构如下邻接表的结点结构信息typedefstructArcNode{/*定义边结点*/int

7、adjvex;/*该弧指向的顶点的位置*/intweight;/*该弧的权重*/structArcNode*nextarc;/*指向下一条弧的指针*/}ArcNode;邻接表的表头向量的结点结构信息typedefstructVNode{VertexTypedata;/*顶点信息*/wilyes11收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802ArcNode*firstarc;/*指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];//定义

8、图结点邻接表的表头带权图的结构信息typedefstruct{AdjListvertices;/*表头向量*/intvexnum,arcnum;//顶点数和弧数}ALGraph;//定义图2、邻接矩阵的储存结构如下typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];/*邻接距阵*/邻接矩阵带权图的结构信息structMGraph{Vertexvexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*

9、顶点数和弧数*/};七、源程序#include#include#include#defineMAX_NAME5/*顶点值最大字符数*/#defineMAX_VERTEX_NUM20/*最大顶