图的广度优先遍历 - 最少转机

阳光穿透心脏的1/2处 2023-02-12 05:55 10阅读 0赞

#  图的广度优先遍历 - 最少转机 #

现在位于 `1` 号城市，目标是 `5` 号城市，可是 `1` 号城市并没有到 `5` 号城市的直航。现在我们希望找到一种乘坐方式，使得转机的次数最少。

5 7 1 5
    1 2
    1 3
    2 3
    2 4
    3 4
    3 5
    4 5

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

第一行的 `5` 表示有 `5` 个城市 (城市编号为 `1~5`)，`7` 表示有 `7` 条航线，`1` 表示起点城市，`5` 表示目标城市，接下来 `7` 行每行是一条类似 `a b` 这样的数据表示城市 `a` 和城市 `b` 之间有航线，也就是说城市 `a` 和城市 `b` 之间可以相互到达。

`input.txt` 第一行是测试用例个数 `2`，后续依次为具体测试用例数据。

2
    5 7 1 5
    1 2
    1 3
    2 3
    2 4
    3 4
    3 5
    4 5
    5 7 1 5
    1 2
    1 3
    2 3
    2 4
    3 4
    3 5
    4 5

这里我们还是使用邻接矩阵来存储图，需要注意的是这里是无向图。城市的编号就是图的顶点，而航班则是两顶点之间的边。要求的是转机次数最少，所以我们可以认为所有边的长度都是 `1`。下面我们用广度优先搜索来解决这个问题。

首先将 `1` 号城市入队，通过 `1` 号城市我们可以到达 (扩展出) `2` 号和 `3` 号城市。`2` 号城市又可以扩展出 `3` 号城市和 `4` 号城市。因为 `3` 号城市已经在队列中，所以只需将 `4` 号城市入队。接下来 `3` 号城市又可以扩展出 `4` 号城市和 `5` 号城市，因为 `4` 号城市也已经在队列中，所以只需将 `5` 号城市入队，此时已经找到了目标城市 `5` 号城市，算法结束。

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

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

5 7 1 5
    1 2
    1 3
    2 3
    2 4
    3 4
    3 5
    4 5

运行结果是：

**当然也可以使用深度优先捜索解决，但是这里用广度优先搜索会更快。广度优先搜索更加适用于所有边的权值相同的情况。**

/*
    ============================================================================
    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[50][2], int N, int M, int start, int end)
    {
    	int ret = 0;
    	int data[50][50] = { 0 };
    	int book[50] = { 0 };
    
    	// 初始化二维矩阵
    	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;
    
    		data[h][w] = 1;
    		data[w][h] = 1;
    	}
    
    	start -= 1;
    	end -= 1;
    
    	int que[2500][2] = { 0 };
    	int head = 0, tail = 0;
    	int flag = 0;
    	int step = 0;
    	int min_step = 0;
    
    	// 从 start 号城市出发，将 start 号城市加入队列
    	que[tail][0] = start;
    	que[tail][1] = step;
    	tail++;
    	// 标记 start 号城市已在队列中
    	book[start] = 1;
    
    	// 当队列不为空的时候循环
    	while (head < tail)
    	{
    		// 当前队列中首城市的编号
    		int popt = que[head][0];
    		int cur_step = que[head][1];
    		head++;
    
    		// 从 1~N 依次尝试
    		for (int k = 0; k < N; k++)
    		{
    			// 城市 popt 到城市 k 是否有航班并且判断城市 k 是否已经在队列中
    			if ((0 == book[k]) && (data[popt][k] != INT_MAX))
    			{
    				// 城市 popt 到城市 k 是有航班并且判断城市 k 不在队列中，将 k 号城市入队
    				que[tail][0] = k;
    				que[tail][1] = cur_step + 1; // 转机次数 + 1
    				tail++;
    				book[k] = 1; // 标记城市 k 已经在
    			}
    
    			// 如果到达目标城市，停止扩展，任务结束，退出循环
    			if (que[tail - 1][0] == end) {
    				flag = 1;
    				min_step = cur_step + 1;
    				break;
    			}
    		}
    
    		if (1 == flag)
    		{
    			break;
    		}
    	}
    
    	ret = min_step;
    	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, start = 0, end = 0;
    		int map[50][2] = { 0 };
    
    		cin >> N >> M >> start >> end;
    
    		for (int h = 0; h < M; h++)
    		{
    			for (int w = 0; w < 2; w++)
    			{
    				cin >> map[h][w];
    			}
    		}
    
    		int ret = inference(map, N, M, start, end);
    
    		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 = 2
    CASE #2 = 2
    
    End of the program, end = 6
    End of the program, end = 6
    Total time taken by CPU: 0.006000
    Exiting of the program...
    请按任意键继续. . .

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

## References ##

《啊哈！算法》 - 啊哈磊

[20200524223610394.png_pic_center]: https://img-blog.csdnimg.cn/20200524223610394.png#pic_center
[20200524223623192.png_pic_center]: https://img-blog.csdnimg.cn/20200524223623192.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20200524223724505.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY=,size_16,color_FFFFFF,t_70#pic_center