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

现在由若干航班信息，要求找出从起点到目的地的最少转机次数。数据给出格式如下：

1
2
3
4
5
6
7
8
5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

第一行的5表示1，2，3，4，5，5个城市，7表示7条航线，1表示起点城市，5表示目标城市。

下面七行数据a b，表示从a到b有航线

现在求出最少转机次数

解题代码

整体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//图的广度优先遍历——最少转机
#include<iostream>
using namespace std;

int city, road, startPonit, target;
//城市数量，路线数量，起点城市，终点城市
int minTime = 9999;//记录最小值

struct node
{
	int cityNum;//城市编号
	int usedTime = 0;//次数
};
//记录城市及转机次数

void wfs(int** cityMap,bool* book,int startPoint,int target )
{
	int timeNeed = 0;
	node queuer[2501];//城市及转机次数队列
	int head = 0;
	int tail = 0;

	queuer[tail].cityNum=startPoint;
	queuer[tail].usedTime = 0;
	book[startPoint] = true;
	tail++;//起点入队

	bool findit = false;//标记是否找到目的地

	while (head < tail)//开始广度优先搜索
	{
		for (int i = 0; i < city + 1; i++)//从队头出发，遍历队头所能到达的城市并入队
		{
			if (cityMap[queuer[head].cityNum][i] == 1 && book[i] == false)
			{
				queuer[tail].cityNum = i;
				queuer[tail].usedTime = queuer[head].usedTime + 1;
				tail++;
				book[i] = true;//记得标记一下已入队的城市，避免死循环
			}//入队操作
			if (queuer[tail - 1].cityNum == target)
			{
				if (minTime > queuer[tail - 1].usedTime) minTime = queuer[tail - 1].usedTime;
				findit = true;
				break;
			}//如果已经找到目标城市，则break
		}
		if (findit == true) break;//如果已经找到目标城市，则break
		head++;//没有找到的话则head++，继续下一层的遍历
	}
}

int main()
{
	cin >> city >> road >> startPonit >> target;

	//城市地图
	int** cityMap = new int*[city + 1];
	for (int i = 0; i < city + 1; i++)
	{
		cityMap[i] = new int[city + 1];
		for (int j = 0; j < city + 1; j++)
		{
			cityMap[i][j] = -1;
		}//初始化一下
	}

	//标记数组
	bool* book = new bool[city + 1];
	for (int i = 0; i < city + 1; i++) book[i] = false;

	//路线信息
	int a, b;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b;
		cityMap[a][b] = 1;
		cityMap[b][a] = 1;
	}
    
	wfs(cityMap, book, startPonit, target);
	cout << minTime;
	return 0;
}

录入数据代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
cin >> city >> road >> startPonit >> target;

    //城市地图
	int** cityMap = new int*[city + 1];
	for (int i = 0; i < city + 1; i++)
	{
		cityMap[i] = new int[city + 1];
		for (int j = 0; j < city + 1; j++)
		{
			cityMap[i][j] = -1;
		}//初始化一下
	}

	//标记数组
	bool* book = new bool[city + 1];
	for (int i = 0; i < city + 1; i++) book[i] = false;

	//路线信息
	int a, b;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b;
		cityMap[a][b] = 1;
		cityMap[b][a] = 1;
	}

WFS代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void wfs(int** cityMap,bool* book,int startPoint,int target )
{
	int timeNeed = 0;
	node queuer[2501];//城市及转机次数队列
	int head = 0;
	int tail = 0;

	queuer[tail].cityNum=startPoint;
	queuer[tail].usedTime = 0;
	book[startPoint] = true;
	tail++;//起点入队

	bool findit = false;//标记是否找到目的地

	while (head < tail)//开始广度优先搜索
	{
		for (int i = 0; i < city + 1; i++)//从队头出发，遍历队头所能到达的城市并入队
		{
			if (cityMap[queuer[head].cityNum][i] == 1 && book[i] == false)
			{
				queuer[tail].cityNum = i;
				queuer[tail].usedTime = queuer[head].usedTime + 1;
				tail++;
				book[i] = true;//记得标记一下已入队的城市，避免死循环
			}//入队操作
			if (queuer[tail - 1].cityNum == target)
			{
				if (minTime > queuer[tail - 1].usedTime) minTime = queuer[tail - 1].usedTime;
				findit = true;
				break;
			}//如果已经找到目标城市，则break
		}
		if (findit == true) break;//如果已经找到目标城市，则break
		head++;//没有找到的话则head++，继续下一层的遍历
	}
}

最终结果：2