图的最短路径(算法与数据结构课程设计).pdf资源-CSDN文库

版权申诉

197 浏览量 2023-03-13 20:57:51 上传评论收藏 523KB PDF 举报

资源推荐

资源详情

资源评论

图的最短路径

一、问题描述

最小生成树是一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中

的所有个结点，并且有保持图连通的最小的边，最小生成树在实际问题中具有一定的应用价

值，如在城市之间建设网络，要保证网络的连通性，求最经济的设计方法。求解最小生成树

时，可以采用普里母算法和克鲁斯卡尔算法。

二、基本要求

1、选择合适的储存结构，完成网的建立；

2、利用普里母算法求网的最少生成树，并输出结果；

3、利用克鲁斯卡尔求网的最少生成树，并输出结果；

4、采用邻接矩阵和邻接表两种储存结构；

三、测试数据

对右图进行测试

右图是 6 个顶点的 10 个边的连通图

六个顶点分别是

v1 v2 v3 v4 v5 v6

边和边上的权植分别是

v1 v2 6

v1 v3 1

v1 v4 5

v2 v3 5

v2 v5 3

v3 v4 5

v3 v5 6

v3 v6 4

v4 v6 2

v5 v6 6

wilyes11 收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

四、算法思想

克鲁斯卡尔算法思想是：假设连通图 N=（V，{E}），则令最小生成树的初始状态为只

有 n 个顶点而无边的非连通图 T=（V，{ }），图中每个顶点自成一个连通分量。在 E 中选

择代价最小的边，若该边依附的顶点落在 T 中不同的连通分量上，则将此边加入到 T 中，否

则舍去此边而选择下一条代价最小的边。以此类推，直至 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，在辅助数组中存在一个相应分量 closedge[i-1]，它包括两个域，其中 lowcost 储

存该边的权。显然，closedge[i-1].lowcost=Min{cost(u,vi)|u∈U},vex∈U}, vex 域存储

该边依附的在 U 中的顶点。

五、模块

克鲁斯卡尔算法和普里母算法都要用到以下的算法

int LocateVex(Mgraph G,Vertex u)，矩阵求点 u 所在位置；

void CreateGraph(Mgraph/ ALGraph &G)，建立带权邻接矩阵/邻接表的结构；

void kruskal2(ALGraph G)，邻接链表的克鲁斯卡尔算法；

void kruskal(MGraph G)，邻接矩阵的克鲁斯卡尔算法；

int minimum(ALGraph/ MGraph G,struct arry wq[])，邻接表/邻接矩阵求最小的权值；

void MiniSpanTree_PRIM1(ALGraph G,VertexType u)，邻接表的普里姆算法；

void MiniSpanTree_PRIM2(MGraph G,VertexType u)，邻接矩阵的普里姆算法。

六、数据结构//(ADT)

1、邻接表的储存结构如下

邻接表的结点结构信息

typedef struct ArcNode{/*定义边结点*/

int adjvex;/*该弧指向的顶点的位置*/

int weight;/*该弧的权重*/

struct ArcNode *nextarc;/*指向下一条弧的指针*/

}ArcNode;

邻接表的表头向量的结点结构信息

typedef struct VNode{

VertexType data; /*顶点信息*/

wilyes11 收集博客(与学习无关)：http://blog.sina.com.cn/u/1810231802

剩余13页未读，继续阅读

评论收藏

内容反馈

版权申诉

คิดถึง643

粉丝: 3909
资源: 1万+

图的最短路径(算法与数据结构课程设计).pdf

单源点最短路径算法的实现 数据结构 课程设计.pdf

基于数据结构的最短路径算法的研究.pdf

最短路径算法分析及其在公交查询的应用.pdf

基于改进遗传算法的最短路径问题的研究.pdf

论文研究-A*最短路径算法的一种高效实现及其优化 .pdf

最短路径查找—Dijkstra算法.pdf

论文研究-一种面向城市复杂路网最短路径提取的定向收敛算法.pdf

曲面最短路径的粒子群优化算法研究.pdf

论文研究-基于中轴线约束的最短路径的血管提取算法.pdf

基于半边数据结构的最短路径算法及其实现.pdf

数据结构中最短路径算法的实现.pdf

【数据结构算法】实验8图的最短路径问题(附源代码)[收集].pdf

数据结构和算法基础.zip

数据结构公园导游.pdf

数据结构总结（自学、期末复习或考研备用）.pdf

论文研究-基于迭代变邻域下降算法求解TTRP问题.pdf

相关实用应用程序（Windows可用）

免费可用的ChatGPT网页版.zip

ChatGPT使用总结：150个ChatGPT提示词模板（完整版）

chromedriver-win64.zip

全国计算机二级WPSoffice精选350道选择题题库（含答案）.pdf

农村公交与异构无人机协同配送优化

李飞飞自传 我看见的世界 The World I see

哈尔滨工业大学-ChatGPT调研报告-2023.3.6-94页.pdf

4个亲测好用的ChatGPT4渠道

基于小波与卷积神经网络的多尺度时间序列分类.zip

学术海报模板+论文科研+研究生

北森能力测评题库.zip

2023泛娱乐社交出海手册-ZEGO即构科技

最新资源

单源点最短路径算法的实现数据结构课程设计.pdf

李飞飞自传我看见的世界 The World I see