图的深度优先遍历 - 城市地图

╰+攻爆jí腚メ 2023-02-12 05:42 15阅读 0赞

#  图的深度优先遍历 - 城市地图 #

## 1. 有向图 ##

根据城市的地图计算出最短行车方案。

![在这里插入图片描述][20200524174921767.png_pic_center]

数据如下：

5 8
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 1 4
    3 4 4
    4 5 5
    5 3 3

第一行的 `5` 表示有 `5` 个城市 (城市编号为 `1~5`)，`8` 表示有 `8` 条公路。接下来 `8` 行每行是一条类似 `a b c` 这样的数据，表示有一条路可以从城市 `a` 到城市 `b`，并且路程为 `c` 公里。需要注意的是这里的公路都是单行的，即`a b c` 仅仅表示一条路可以从城市 `a` 到城市 `b`，并不表示城市 `b` 也有一条路可以到城市 `a`。现在请求出 `1` 号城市到 `5` 号城市的最短路程 (也叫做最短路径)。  
已知有 `5` 个城市和 `8` 条公路，我们可以用一个 `5*5` 的矩阵 (二维数组 `e`) 来存储这些信息，如下。

![在这里插入图片描述][20200524174937491.png_pic_center]

上面这个二维矩阵表示了任意两个城市之间的路程。比如 `e[1][2]` 的值为 `2` 就表示从 `1` 号城市到 `2` 号城市的路程为 `2` 公里。 ∞ \\infty ∞ 表示无法到达，比如 `e[1][3]` 的值为 `8`，表示目前从 `1` 号城市不能到达 `3` 号城市。此处我们约定一个城市自己到自己的距离是 `0`。

接下来我们就要寻找从 `1` 号城市到 `5` 号城市的最短路程 (最短路径) 了。首先从 `1` 号城市出发，那么 `1` 号城市可以到哪些城市呢？从二维数组 `e` 的第一行可以看出 `1` 号城市可以到 `2` 号城市和 `5` 号城市。那此时是先到 `2` 号城市，还是先到 `5` 号城市？**这里需要规定一个顺序，按照从 `1` 到 `n` 的顺序。**现在先选择到 `2` 号城市，到达 `2` 号城市后接下来又该怎么办呢？依旧参照刚才对 `1` 号城市的处理办法，再来看 `2` 号城市可以到哪些城市。从二维数组 `e` 的第二行可以看出从 `2` 号城市可以到 `3` 号城市和 `5` 号城市。按照刚才规定好的顺序，我们先到 `3` 号城市。同理，`3` 号城市又可以到 `4` 号城市，`4` 号城市可以到 `5` 号城市 (`5` 号城市为最终目标城市)，此时我们就己经找出了一条从 `1` 号城市到 `5` 号城市的路径，这条路径是 `1 -> 2 -> 3 -> 4 -> 5`，路径的长度是 `14`。

因为 `1 -> 2 -> 3 -> 4 -> 5` 这条路径的长度并不一定是最短的。因此我们还需要再返回到 `4` 号城市看看还有没有别的路可以让路径更短一点。但是我们发现 `4` 号城市除了可以到 `5` 号城市，便没有别的路可以走了。此时需要返回到 `3` 号城市，我们发现 `3` 号城市除了一条路通往 `4` 号城市也没有其他的路了。此时又继续回到 `2` 号城市，我们发现 `2` 号城市还有一条路可以到 `5` 号城市，于是就产生了 `1 -> 2 -> 5` 这条路径，路径长度为 `9`。在对 `2` 号城市的所有路都尝试过后，又返回到了 `1` 号城市。我们发现 `1` 号城市还有一条路是通向 `5` 号城市的，于是又产生了一条路径 `1 -> 5`，路径长度为 `10`。至此我们己经找出了所有从 `1` 号城市到 `5` 号城市的通路，一共有 `3` 条，分别是：  
`1 -> 2 -> 3 -> 4 -> 5`：路径长度为 `14`  
`1 -> 2 -> 5`：路径长度为 `9`  
`1 -> 5`：路径长度为 `10`

我们可以用一个全局变量 `min_dist` 来更新每次找到的路径的最小值，最终找到的最短路径为 `9`。**此外还需要一个 `book` 数组来记录哪些城市已经走过，以免出现 `1 -> 2 -> 3 -> 1` 这样的无限死循环。**

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    void dfs(int data[100][100], int N, int cur, int des, int book[100], int dist, int *min_dist)
    {
    	// cur 是当前所在城市的编号 - 1
    	// dist 是当前已经走过的路程
    	// 如果当前走过的路程己经大于之前找到的最短路程，则没有必要再往下尝试了，立即返回 
    	if (dist > *min_dist) {
    		return;
    	}
    
    	// 判断是否到达了目标城市
    	if (cur == des) {
    		if (dist < *min_dist) { *min_dist = dist; } // 更新最小值
    		return;
    	}
    
    	// 从 1 (1 - 1) 号城市到 N (N - 1) 号城市的尝试
    	for (int k = 0; k < N; k++)
    	{
    		// 判断当前城市 cur 到城市 k 是否有路，并判断城市 k 是否在已经走过的路径中
    		if ((0 == book[k]) && (data[cur][k] != INT_MAX))
    		{
    			book[k] = 1; // 标记城市 k 已经在路径中
    			dfs(data, N, k, des, book, dist + data[cur][k], min_dist); // 从城市 k 再出发，继续寻找目标城市
    			book[k] = 0; // 之前一步探索完毕之后，取消对城市 k 的标记
    		}
    	}
    
    	return;
    }
    
    int inference(int map[100][3], int N, int M)
    {
    	int ret = 0;
    	int data[100][100] = { 0 };
    	int cur = 0, des = 0;
    	int book[100] = { 0 };
    	int dist = 0;
    	int min_dist = INT_MAX;
    
    	// 初始化二维矩阵
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j < N; j++)
    		{
    			if (i == j) {
    				data[i][j] = 0;
    			}
    			else {
    				data[i][j] = INT_MAX;
    			}
    		}
    	}
    
    	// 读入城市之间的道路
    	for (int m = 0; m < M; m++)
    	{
    		int h = map[m][0] - 1;
    		int w = map[m][1] - 1;
    		int value = map[m][2];
    
    		data[h][w] = value;
    	}
    
    	// cur 是当前所在城市的编号 - 1
    	// dist 是当前已经走过的路程
    	// des 目标城市的编号 - 1
    	cur = 1 - 1;
    	des = 5 - 1;
    	min_dist = INT_MAX;
    	book[cur] = 1;
    
    	dfs(data, N, cur, des, book, dist, &min_dist);
    
    	ret = min_dist;
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int N = 0, M = 0;
    		int map[100][3] = { 0 };
    
    		cin >> N >> M;
    
    		for (int h = 0; h < M; h++)
    		{
    			for (int w = 0; w < 3; w++)
    			{
    				cin >> map[h][w];
    			}
    		}
    
    		int ret = inference(map, N, M);
    
    		cout << "CASE #" << i << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

可以输入以下数据进行验证。

2
    5 8
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 1 4
    3 4 4
    4 5 5
    5 3 3
    5 8
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 1 4
    3 4 4
    4 5 5
    5 3 3

运行结果是：

需要注意的是：如何表示正无穷。上面的代码中我们将正无穷定义为 `INT_MAX`。

图就是有 `N` 个顶点和 `M` 条边组成的集合。这里的城市地图其实就是一个图，图中每个城市就是一个顶点，而两个城市之间的公路则是两个顶点的边。

### 1.1 `D:\visual_studio_workspace\yongqiangcheng\yongqiangcheng\input.txt` ###

`input.txt` 第一行是测试用例个数 `2`，后续依次为具体测试用例数据。  
接下来 `M` 行每行是一条类似 `a b c` 这样的数据，表示有一条路可以从城市 `a` 到城市 `b`，并且路程为 `c` 公里。需要注意的是这里的公路都是单行的，即`a b c` 仅仅表示一条路可以从城市 `a` 到城市 `b`，并不表示城市 `b` 也有一条路可以到城市 `a`。

2
    5 8
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 1 4
    3 4 4
    4 5 5
    5 3 3
    5 8
    1 2 2
    1 5 10
    2 3 3
    2 5 7
    3 1 4
    3 4 4
    4 5 5
    5 3 3

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

Start of the program, start = 0
    Start of the program, start = 0
    
    CASE #1 = 9
    CASE #2 = 9
    
    End of the program, end = 2
    End of the program, end = 2
    Total time taken by CPU: 0.002000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]

## 2. 无向图 ##

图分为有向图和无向图。如果给图的每条边规定一个方向，那么得到的图称为有向图，其边也称为有向边。在有向图中，与一个点相关联的边有出边和入边之分，而与一个有向边关联的两个点也有始点和终点之分。相反，边没有方向的图称为无向图。城市地图改为无向图后如下，

![在这里插入图片描述][20200524180827819.png_pic_center]

处理无向图和处理有向图的代码几乎是一模一样的。只是在处理无向图初始化的时候有一点需要注意。`a b c` 表示城市 `a` 和城市 `b` 可以互相到达，路程为 `c` 公里。因此我们需要将 `e[1][2]` 和 `e[2][1]` 都初始化 `2`，因为这条路是双行道，初始化后的数组 `e` 如下，

![在这里插入图片描述][20200524180833719.png_pic_center]

这个表是对称的，这是无向图的一个特征，在这个无向图中，我们会发现从 `1` 号城市到 `5` 号城市的最短路径不再是 `1 -> 2 -> 5`，而是 `1 -> 3 -> 5`，路径长度为 `7`。

使用了二维数组来存储这个图 (顶点和边的关系)，这种存储方法叫做图的邻接矩阵表示法。存储图的方法还有很多种，比如邻接表等。

/*
    ============================================================================
    Name        : yongqiang.cpp
    Author      : Yongqiang Cheng
    Version     : Version 1.0.0
    Copyright   : Copyright (c) 2020 Yongqiang Cheng
    Description : Hello World in C++, Ansi-style
    ============================================================================
    */
    
    #define _CRT_SECURE_NO_WARNINGS
    #include <iostream>
    #include <time.h>
    
    using namespace std;
    
    void dfs(int data[100][100], int N, int cur, int des, int book[100], int dist, int *min_dist)
    {
    	// cur 是当前所在城市的编号 - 1
    	// dist 是当前已经走过的路程
    	// 如果当前走过的路程己经大于之前找到的最短路程，则没有必要再往下尝试了，立即返回 
    	if (dist > *min_dist) {
    		return;
    	}
    
    	// 判断是否到达了目标城市
    	if (cur == des) {
    		if (dist < *min_dist) { *min_dist = dist; } // 更新最小值
    		return;
    	}
    
    	// 从 1 (1 - 1) 号城市到 N (N - 1) 号城市的尝试
    	for (int k = 0; k < N; k++)
    	{
    		// 判断当前城市 cur 到城市 k 是否有路，并判断城市 k 是否在已经走过的路径中
    		if ((0 == book[k]) && (data[cur][k] != INT_MAX))
    		{
    			book[k] = 1; // 标记城市 k 已经在路径中
    			dfs(data, N, k, des, book, dist + data[cur][k], min_dist); // 从城市 k 再出发，继续寻找目标城市
    			book[k] = 0; // 之前一步探索完毕之后，取消对城市 k 的标记
    		}
    	}
    
    	return;
    }
    
    int inference(int map[100][3], int N, int M)
    {
    	int ret = 0;
    	int data[100][100] = { 0 };
    	int cur = 0, des = 0;
    	int book[100] = { 0 };
    	int dist = 0;
    	int min_dist = INT_MAX;
    
    	// 初始化二维矩阵
    	for (int i = 0; i < N; i++)
    	{
    		for (int j = 0; j < N; j++)
    		{
    			if (i == j) {
    				data[i][j] = 0;
    			}
    			else {
    				data[i][j] = INT_MAX;
    			}
    		}
    	}
    
    	// 读入城市之间的道路
    	for (int m = 0; m < M; m++)
    	{
    		int h = map[m][0] - 1;
    		int w = map[m][1] - 1;
    		int value = map[m][2];
    
    		data[h][w] = value;
    		data[w][h] = value;
    	}
    
    	// cur 是当前所在城市的编号 - 1
    	// dist 是当前已经走过的路程
    	// des 目标城市的编号 - 1
    	cur = 1 - 1;
    	des = 5 - 1;
    	min_dist = INT_MAX;
    	book[cur] = 1;
    
    	dfs(data, N, cur, des, book, dist, &min_dist);
    
    	ret = min_dist;
    	return ret;
    }
    
    int main()
    {
    	clock_t start = 0, end = 0;
    	double cpu_time_used = 0;
    
    	const char input_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\input.txt";
    	const char output_txt[] = "D:\\visual_studio_workspace\\yongqiangcheng\\yongqiangcheng\\output.txt";
    
    	freopen(input_txt, "r", stdin);
    	// freopen(output_txt, "w", stdout);
    
    	start = clock();
    	printf("Start of the program, start = %ld\n", start);
    	printf("Start of the program, start = %ld\n\n", start);
    
    	int case_num;
    	cin >> case_num;
    
    	for (int i = 1; i <= case_num; i++)
    	{
    		int N = 0, M = 0;
    		int map[100][3] = { 0 };
    
    		cin >> N >> M;
    
    		for (int h = 0; h < M; h++)
    		{
    			for (int w = 0; w < 3; w++)
    			{
    				cin >> map[h][w];
    			}
    		}
    
    		int ret = inference(map, N, M);
    
    		cout << "CASE #" << i << " = " << ret << endl;
    	}
    
    	end = clock();
    	printf("\nEnd of the program, end = %ld\n", end);
    	printf("End of the program, end = %ld\n", end);
    
    	cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC;
    	printf("Total time taken by CPU: %f\n", cpu_time_used);
    
    	printf("Exiting of the program...\n");
    
    	fclose(stdin);
    	// fclose(stdout);
    
    	return 0;
    }

Start of the program, start = 0
    Start of the program, start = 0
    
    CASE #1 = 7
    CASE #2 = 7
    
    End of the program, end = 3
    End of the program, end = 3
    Total time taken by CPU: 0.003000
    Exiting of the program...
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]

此外求图上两点之间的最短路径，除了使用深度优先搜索以外，还可以使用广度优先搜索、Floyd、Bellman-Ford、Dijkstra 等。

## References ##

《啊哈！算法》 - 啊哈磊

[20200524174921767.png_pic_center]: https://img-blog.csdnimg.cn/20200524174921767.png#pic_center
[20200524174937491.png_pic_center]: https://img-blog.csdnimg.cn/20200524174937491.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200524183813220.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20200524175324942.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center
[20200524180827819.png_pic_center]: https://img-blog.csdnimg.cn/20200524180827819.png#pic_center
[20200524180833719.png_pic_center]: https://img-blog.csdnimg.cn/20200524180833719.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20200524180951976.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center