《数据结构(C语言版)第二版》第六章-图(6.6 图的应用——6.6.2 最短路径)

2024-08-23 10:52

本文主要是介绍《数据结构(C语言版)第二版》第六章-图(6.6 图的应用——6.6.2 最短路径),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

6.6.2.1 从某个源点到其余各顶点的最短路径

迪杰斯特拉算法

C语言常见问题——数组初始化的四种方法 —— 易水卷长空

#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100typedef char VerTexType;
typedef int ArcType;bool S[MVNum]; //记录从源点v0到终点vi是否已被确定最短路径长度,true表示确定,false表示尚未确定。
ArcType D[MVNum]; //记录从源点v0到终点vi的当前最短路径长度。
int Path[MVNum]; //记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号(下标)。
//这三个数组中的每个下标,与G.vexs中各顶点的下标是一致的int reverse[MVNum];  //未对reverse数组进行初始化时,需将其定义为全局变量typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath(AMGraph G, int v0);
void printPath(AMGraph G, int v0);int main()
{AMGraph G = { {0},{0},0,0 };int i = 0;CreateAMGraph(G);printAMGraph(G);printf("\n");ShortestPath(G, 0);printPath(G, 0);return 0;
}//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; i++){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &G.vexs[i]);for (j = 0; j < G.vexnum; j++){G.arcs[i][j] = MaxInt;}}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边的两个顶点:", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));printf("请输入第%d条边的权值:", k + 1);scanf_s(" %d", &w);i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w;}
}int LocateVex(AMGraph G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++){;}return i;
}void printAMGraph(AMGraph G)
{int i = 0;int j = 0;printf("各顶点值为:");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为:\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == MaxInt){printf("%d   ", G.arcs[i][j]);}else if (G.arcs[i][j] > 9){printf("%d      ", G.arcs[i][j]);}else{printf("%d       ", G.arcs[i][j]);}}printf("\n");}
}//用Dijkstra算法求有向网G的下标为vO的顶点到其余顶点的最短路径
void ShortestPath(AMGraph G, int v0)
{int n = G.vexnum;int v = 0;int i = 0;int min = 0;int w = 0;for (v = 0; v < n; ++v){if (v != v0){S[v] = false;D[v] = G.arcs[v0][v];if (D[v] < MaxInt){Path[v] = v0;}else{Path[v] = -1;}}else{S[v] = true;D[v] = 0;Path[v] = -1;}}for (i = 1; i < n; i++){//在未被确定最短路径长度的顶点中(S[w]为false),寻找各顶点最短路径长度D[w]的最小值minmin = MaxInt;for (w = 0; w < n; ++w){if (!S[w] && D[w] < min){v = w;min = D[w];}}S[v] = true;for (w = 0; w < n && v < n; ++w)  //这里必须限制v < n,因为当以G.vexs中最后一个顶点为源点时,v会在自增后跳出初始化的for循环,即会等于G.vexnum{if (!S[w] && (D[v] + G.arcs[v][w] < D[w])){D[w] = D[v] + G.arcs[v][w];Path[w] = v;}}}/* 在最后的for循环if条件中,一定不要加D[v]!=MaxInt这个条件,因为当从下标为v0的源点到下标为w的顶点之间不存在弧时,D[w]的值为MaxInt.此时以下标为v的顶点为中转点的路径(Vv0,Vv,Vw)就是从下标为v0的源点到下标为w的顶点之间的最短路径,需要对D[w]及Path[w]的值都进行更新。而且此if中加上条件 G.arcs[v][w] != MaxInt 也不会起作用,因为当G.arcs[v][w]为MaxInt时,D[w]的最大值为MaxInt,而D[v]也一定为非负值,因此后面的 D[v] + G.arcs[v][w] < D[w] 一定不会成立。  */printf("\n\n打印S数组:");for (i = 0; i < G.vexnum; i++){printf("%d ", S[i]);}printf("\n打印D数组:");for (i = 0; i < G.vexnum; i++){printf("%d ", D[i]);}printf("\n打印Path数组:");for (i = 0; i < G.vexnum; i++){printf("%d ", Path[i]);}
}//最好用栈或递归
void printPath(AMGraph G, int v0)
{int i = 0;int j = 0;int k = 0;//int reverse[MVNum] = {0}; 或者把reverse数组定义为全局变量,或者如此对reverse数组进行初始化(不同于数组作为函数形参,当不列出数组中的所有元素时,必须要指明数组大小)//如果初始化列表包含数组a的所有元素,才可以省略数组的长度for (i = 0; i < G.vexnum; i++){if (i != v0){if (Path[i] == -1){printf("\n以第%d个顶点%c为源点,到终点%c无最短路径。", v0 + 1, G.vexs[v0], G.vexs[i]);}else{reverse[0] = i;for (j = 1, k = Path[i]; j < G.vexnum && k != v0; j++, k = Path[k]){reverse[j] = k;}reverse[j] = v0;printf("\n以第%d个顶点%c为源点,到终点%c的最短路径为:", v0 + 1, G.vexs[v0], G.vexs[i]);for (k = j; k >= 0; k--){if (k > 0){printf("%c -> ", G.vexs[reverse[k]]);}else{printf("%c ", G.vexs[reverse[k]]);}}printf(",权值为:%d", D[i]);}}}
}

在这里插入图片描述
在这里插入图片描述

使用递归输出到其余各顶点的最短路径

//使用递归输出到其余各顶点的最短路径
void find(AMGraph G, int v0, int i)
{//printf("\nv0 = %d , i = %d\n", v0, i);if (i == v0){printf("%c", G.vexs[v0]); // 到达源点,直接输出 return;}else{//printf("\nv0 = %d , Path[i] = Path[%d] = %d\n",v0,i, Path[i]);find(G, v0, Path[i]); // 递归地打印前驱顶点,v0 = 0, i = 3,Path[3] = 4,Path[4] = 0//printf("\nG.vexs[i] =  G.vexs[%d] = %c\n", i, G.vexs[i]);printf(" -> %c", G.vexs[i]); // 打印当前顶点}
}void printPath(AMGraph G, int v0)
{int i = 0;for (i = 0; i < G.vexnum; i++){if (i != v0){if (Path[i] == -1){printf("\n以第%d个顶点%c为源点,到终点%c无最短路径。", v0 + 1, G.vexs[v0], G.vexs[i]);}else{printf("\n以第%d个顶点%c为源点,到终点%c的最短路径为:", v0 + 1, G.vexs[v0], G.vexs[i]);find(G, v0, i);  //v0 = 0, i = 3printf(",权值为:%d", D[i]);}}}
}

在这里插入图片描述

6.6.2.2 每一对顶点之间的最短路径

6.6.2.2.1 调用n次迪杰斯特拉算法

#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100typedef char VerTexType;
typedef int ArcType;bool S[MVNum]; //记录从源点v0到终点vi是否已被确定最短路径长度,true表示确定,false表示尚未确定。
ArcType D[MVNum]; //记录从源点v0到终点vi的当前最短路径长度。
int Path[MVNum]; //记录从源点v0到终点vi的当前最短路径上vi的直接前驱顶点序号(下标)。
//这三个数组中的每个下标,与G.vexs中各顶点的下标是一致的int reverse[MVNum];  //未对reverse数组进行初始化时,需将其定义为全局变量typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath(AMGraph G, int v0);
void printPath(AMGraph G, int v0);int main()
{AMGraph G = { {0},{0},0,0 };int i = 0;CreateAMGraph(G);printAMGraph(G);for (i = 0; i < G.vexnum; i++){printf("\n");ShortestPath(G, i);printPath(G, i);}return 0;
}//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; i++){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &G.vexs[i]);for (j = 0; j < G.vexnum; j++){G.arcs[i][j] = MaxInt;}}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边的两个顶点:", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));printf("请输入第%d条边的权值:", k + 1);scanf_s(" %d", &w);i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w;}
}int LocateVex(AMGraph G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++){;}return i;
}void printAMGraph(AMGraph G)
{int i = 0;int j = 0;printf("各顶点值为:");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为:\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == MaxInt){printf("%d   ", G.arcs[i][j]);}else if(G.arcs[i][j] > 9){printf("%d      ", G.arcs[i][j]);}else{printf("%d       ", G.arcs[i][j]);}}printf("\n");}
}//用Dijkstra算法求有向网G的下标为vO的顶点到其余顶点的最短路径
void ShortestPath(AMGraph G, int v0)
{int n = G.vexnum;int v = 0;int i = 0;int min = 0;int w = 0;for (v = 0; v < n; ++v){if (v != v0){S[v] = false;D[v] = G.arcs[v0][v];if (D[v] < MaxInt){Path[v] = v0;}else{Path[v] = -1;}}else{S[v] = true;D[v] = 0;Path[v] = -1;}}for (i = 1; i < n; i++){//在未被确定最短路径长度的顶点中(S[w]为false),寻找各顶点最短路径长度D[w]的最小值minmin = MaxInt;for (w = 0; w < n; ++w){if (!S[w] && D[w] < min){v = w;min = D[w];}}S[v] = true;for (w = 0; w < n && v < n; ++w)  //这里必须限制v < n,因为当以G.vexs中最后一个顶点为源点时,v会在自增后跳出初始化的for循环,即会等于G.vexnum{if (!S[w] && (D[v] + G.arcs[v][w] < D[w])){D[w] = D[v] + G.arcs[v][w];Path[w] = v;}}}/* 在最后的for循环if条件中,一定不要加D[v]!=MaxInt这个条件,因为当从下标为v0的源点到下标为w的顶点之间不存在弧时,D[w]的值为MaxInt.此时以下标为v的顶点为中转点的路径(Vv0,Vv,Vw)就是从下标为v0的源点到下标为w的顶点之间的最短路径,需要对D[w]及Path[w]的值都进行更新。而且此if中加上条件 G.arcs[v][w] != MaxInt 也不会起作用,因为当G.arcs[v][w]为MaxInt时,D[w]的最大值为MaxInt,而D[v]也一定为非负值,因此后面的 D[v] + G.arcs[v][w] < D[w] 一定不会成立。  */printf("\n\n打印S数组:");for (i = 0; i < G.vexnum; i++){printf("%d ", S[i]);}printf("\n打印D数组:");for (i = 0; i < G.vexnum; i++){printf("%d ", D[i]);}printf("\n打印Path数组:");for (i = 0; i < G.vexnum; i++){printf("%d ", Path[i]);}
}//最好用栈或递归
void printPath(AMGraph G, int v0)
{int i = 0;int j = 0;int k = 0;//int reverse[MVNum] = {0}; 或者把reverse数组定义为全局变量,或者如此对reverse数组进行初始化(不同于数组作为函数形参,当不列出数组中的所有元素时,必须要指明数组大小)//如果初始化列表包含数组a的所有元素,才可以省略数组的长度for (i = 0; i < G.vexnum; i++){if (i != v0){if (Path[i] == -1){printf("\n以第%d个顶点%c为源点,到终点%c无最短路径。", v0 + 1, G.vexs[v0], G.vexs[i]);}else {reverse[0] = i;for (j = 1, k = Path[i];j <G.vexnum && k != v0; j++, k = Path[k]){					reverse[j] = k;}reverse[j] = v0;printf("\n以第%d个顶点%c为源点,到终点%c的最短路径为:", v0 + 1, G.vexs[v0], G.vexs[i]);for (k = j; k >= 0; k--){if (k > 0){printf("%c -> ", G.vexs[reverse[k]]);}else{printf("%c ", G.vexs[reverse[k]]);}}printf(",权值为:%d", D[i]);}}}
}

在这里插入图片描述
在这里插入图片描述

6.6.2.2.2 弗洛伊德算法

#include <stdio.h>
#include <stdlib.h>#define MaxInt 32767
#define MVNum 100typedef char VerTexType;
typedef int ArcType;ArcType D[MVNum][MVNum]; //记录顶点Vi和Vj之间的最短路径长度。
int Path[MVNum][MVNum]; //最短路径上顶点Vj的前一顶点的序号(下标)。
//这两个数组中的关于顶点的每个下标,与G.vexs中各顶点的下标是一致的typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum;int arcnum;
}AMGraph;void CreateAMGraph(AMGraph& G);
int LocateVex(AMGraph G, VerTexType v);
void printAMGraph(AMGraph G);
void ShortestPath_Floyd(AMGraph G);
void find(AMGraph G, int i, int j);
void printPath(AMGraph G);int main()
{AMGraph G = { {0},{0},0,0 };int i = 0;CreateAMGraph(G);printAMGraph(G);printf("\n");ShortestPath_Floyd(G);printPath(G);return 0;
}//创建带权有向网的邻接矩阵
void CreateAMGraph(AMGraph& G)
{int i = 0;int j = 0;int k = 0;VerTexType v1 = '\0';VerTexType v2 = '\0';ArcType w = 0;printf("请输入总顶点数:");scanf_s(" %d", &G.vexnum);printf("请输入总边数:");scanf_s(" %d", &G.arcnum);for (i = 0; i < G.vexnum; i++){printf("请输入第%d个顶点的值:", i + 1);scanf_s(" %c", &G.vexs[i]);for (j = 0; j < G.vexnum; j++){if (i != j){G.arcs[i][j] = MaxInt;}else{G.arcs[i][j] = 0;  /* 在弗洛伊德算法中,每个顶点到其自身,(中间不存在弧),就已经是最短路径了。即使可以通过其它顶点中转再到达其本身,也是比其直接到其自身长的,所以把每个顶点与自身之间的权值均设为0.  */}}}for (k = 0; k < G.arcnum; k++){printf("请输入第%d条边的两个顶点:", k + 1);scanf_s(" %c %c", &v1, sizeof(VerTexType), &v2, sizeof(VerTexType));printf("请输入第%d条边的权值:", k + 1);scanf_s(" %d", &w);i = LocateVex(G, v1);j = LocateVex(G, v2);G.arcs[i][j] = w;}
}int LocateVex(AMGraph G, VerTexType v)
{int i = 0;for (i = 0; i < G.vexnum && (G.vexs[i] != v); i++){;}return i;
}void printAMGraph(AMGraph G)
{int i = 0;int j = 0;printf("各顶点值为:");for (i = 0; i < G.vexnum; i++){printf("%c ", G.vexs[i]);}printf("\n邻接矩阵为:\n");for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (G.arcs[i][j] == MaxInt){printf("%d   ", G.arcs[i][j]);}else if (G.arcs[i][j] > 9){printf("%d      ", G.arcs[i][j]);}else{printf("%d       ", G.arcs[i][j]);}}printf("\n");}
}//用Floyd算法求有向网G中各对顶点i和j之间的最短路径
void ShortestPath_Floyd(AMGraph G)
{int i = 0;int j = 0;int k = 0;for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){D[i][j] = G.arcs[i][j];if (D[i][j] < MaxInt && D[i][j] != 0  ){Path[i][j] = i;}else{Path[i][j] = -1;}}}for (k = 0; k < G.vexnum; k++){for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (D[i][k] + D[k][j] < D[i][j]){D[i][j] = D[i][k] + D[k][j];Path[i][j] = Path[k][j];}}}}
}//递归打印G中从下标为i的顶点,到下标为j的顶点的最短路径
void find(AMGraph G, int i, int	j)
{if (i == j){printf("%c ", G.vexs[i]);return;}else{find(G, i, Path[i][j]);  //不断取从序号为i的顶点到序号为j的顶点最短路径上,序号为j的顶点的直接前驱顶点的序号printf(" -> %c", G.vexs[j]); //并且打印该序号对应的顶点值}
}void printPath(AMGraph G)
{int i = 0;int j = 0;for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (j != i){if (Path[i][j] == -1){printf("\n从第%d个顶点%c到第%d个顶点%c不存在最短路径。", i + 1, G.vexs[i], j + 1, G.vexs[j]);}else{printf("\n从第%d个顶点%c到第%d个顶点%c的最短路径为:", i + 1, G.vexs[i], j + 1, G.vexs[j]);find(G, i, j);printf(" ,其长度为:%d", D[i][j]);}}}}
}

在这里插入图片描述
在这里插入图片描述

上例中带权有向网的输出结果(两种算法输出一致。)

在这里插入图片描述
在这里插入图片描述

使用递归读取两个顶点之间的最短路径

//递归打印G中从下标为i的顶点,到下标为j的顶点的最短路径
void find(AMGraph G, int i, int	j)
{printf("\ni = %d , j = %d\n\n",i,j);if (i == j){printf("%c ", G.vexs[i]);return;}else{printf("\ni = %d , Path[i][j] = Path[%d][%d] = %d\n\n",i, i,j,Path[i][j]);find(G, i, Path[i][j]);  //不断取从序号为i的顶点到序号为j的顶点最短路径上,序号为j的顶点的直接前驱顶点的序号printf("\n\nG.vexs[i] =  G.vexs[%d] = %c", i, G.vexs[i]);printf("\nG.vexs[j] =  G.vexs[%d] = %c", j, G.vexs[j]);printf("\nG.vexs[Path[i][j]] = G.vexs[Path[%d][%d]] = G.vexs[%d] = %c\n\n",i,j,Path[i][j], G.vexs[Path[i][j]]);printf(" -> %c", G.vexs[j]); //并且打印该序号对应的顶点值}
}

在这里插入图片描述

这篇关于《数据结构(C语言版)第二版》第六章-图(6.6 图的应用——6.6.2 最短路径)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099179

相关文章

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据:本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组(Array)2. 切片(Slice)3. 映射(Map)对比总结注意事项基本概念在 Go 语言中,有三种主要

5分钟获取deepseek api并搭建简易问答应用

《5分钟获取deepseekapi并搭建简易问答应用》本文主要介绍了5分钟获取deepseekapi并搭建简易问答应用,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需... 目录1、获取api2、获取base_url和chat_model3、配置模型参数方法一:终端中临时将加

JavaScript中的isTrusted属性及其应用场景详解

《JavaScript中的isTrusted属性及其应用场景详解》在现代Web开发中,JavaScript是构建交互式应用的核心语言,随着前端技术的不断发展,开发者需要处理越来越多的复杂场景,例如事件... 目录引言一、问题背景二、isTrusted 属性的来源与作用1. isTrusted 的定义2. 为

Python调用另一个py文件并传递参数常见的方法及其应用场景

《Python调用另一个py文件并传递参数常见的方法及其应用场景》:本文主要介绍在Python中调用另一个py文件并传递参数的几种常见方法,包括使用import语句、exec函数、subproce... 目录前言1. 使用import语句1.1 基本用法1.2 导入特定函数1.3 处理文件路径2. 使用ex

将Python应用部署到生产环境的小技巧分享

《将Python应用部署到生产环境的小技巧分享》文章主要讲述了在将Python应用程序部署到生产环境之前,需要进行的准备工作和最佳实践,包括心态调整、代码审查、测试覆盖率提升、配置文件优化、日志记录完... 目录部署前夜:从开发到生产的心理准备与检查清单环境搭建:打造稳固的应用运行平台自动化流水线:让部署像

Linux中Curl参数详解实践应用

《Linux中Curl参数详解实践应用》在现代网络开发和运维工作中,curl命令是一个不可或缺的工具,它是一个利用URL语法在命令行下工作的文件传输工具,支持多种协议,如HTTP、HTTPS、FTP等... 目录引言一、基础请求参数1. -X 或 --request2. -d 或 --data3. -H 或

在Ubuntu上部署SpringBoot应用的操作步骤

《在Ubuntu上部署SpringBoot应用的操作步骤》随着云计算和容器化技术的普及,Linux服务器已成为部署Web应用程序的主流平台之一,Java作为一种跨平台的编程语言,具有广泛的应用场景,本... 目录一、部署准备二、安装 Java 环境1. 安装 JDK2. 验证 Java 安装三、安装 mys

Python中构建终端应用界面利器Blessed模块的使用

《Python中构建终端应用界面利器Blessed模块的使用》Blessed库作为一个轻量级且功能强大的解决方案,开始在开发者中赢得口碑,今天,我们就一起来探索一下它是如何让终端UI开发变得轻松而高... 目录一、安装与配置:简单、快速、无障碍二、基本功能:从彩色文本到动态交互1. 显示基本内容2. 创建链

Node.js 中 http 模块的深度剖析与实战应用小结

《Node.js中http模块的深度剖析与实战应用小结》本文详细介绍了Node.js中的http模块,从创建HTTP服务器、处理请求与响应,到获取请求参数,每个环节都通过代码示例进行解析,旨在帮... 目录Node.js 中 http 模块的深度剖析与实战应用一、引言二、创建 HTTP 服务器:基石搭建(一

java中VO PO DTO POJO BO DO对象的应用场景及使用方式

《java中VOPODTOPOJOBODO对象的应用场景及使用方式》文章介绍了Java开发中常用的几种对象类型及其应用场景,包括VO、PO、DTO、POJO、BO和DO等,并通过示例说明了它... 目录Java中VO PO DTO POJO BO DO对象的应用VO (View Object) - 视图对象