图的广度优先遍历

本文主要是介绍图的广度优先遍历 - 最少转机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

在这里插入图片描述

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

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

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

首先将 1 号城市入队，通过 1 号城市我们可以到达 (扩展出) 2 号和 3 号城市。2 号城市又可以扩展出 3 号城市和 4 号城市。因为 3 号城市已经在队列中，所以只需将 4 号城市入队。接下来 3 号城市又可以扩展出 4 号城市和 5 号城市，因为 4 号城市也已经在队列中，所以只需将 5 号城市入队，此时已经找到了目标城市 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; // 转机次数 + 1tail++;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 = 0CASE #1 = 2
CASE #2 = 2End of the program, end = 6
End of the program, end = 6
Total time taken by CPU: 0.006000
Exiting of the program...
请按任意键继续. . .

在这里插入图片描述