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

城市1-n的最少转机数

样例输入：

第一行：五个城市，7条通路（无向），起点，终点

第二行：哪两个城市连通

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

样例输出：

2

完整代码：

#include<iostream>
using namespace std;
struct node {
	int x;//城市编号
	int s;//转机次数
};
int main() {
	int i, j, a, b, n, m,tail, head,start,flag=0,end,cur;
	int book[101] = { 0 }, e[101][101];
	struct node que[10001];
	//输入n个城市，m个航班，起始地点，终点
	cin >> n >> m>>start>>end;
	for(i=1;i<=n;i++)
		for (j = 1;j <= n;j++) {
			if (i == j)
				e[i][j] = 0;
			else
				e[i][j] = -1;
		}
	//无向图赋值
	for (i = 1;i <= m;i++) {
		cin >> a >> b;
		e[a][b] = 1;
		e[b][a] = 1;
	}
	//队列初始化
	head = 1;
	tail = 1;
	//从start号称是出发，将start号城市加入队列
	que[tail].x = start;
	que[tail].s = 0;
	tail++;
	book[1] = start;//标记
	//当队列不为空时循环
	while (head < tail) {
		cur = que[head].x;//当前队列中首城市的编号
		for (i = 1;i <= n;i++) {
			//从城市cur到城市i有航班并且未标记
			if (e[cur][i] !=-1 && book[i] == 0) {
				que[tail].x= i;
				que[tail].s = que[head].s + 1;
				tail++;
				book[i] = 1;
			}
			//如果到达目标城市，停止扩展，任务结束，退出循环
			if (que[tail].x ==end) {
				flag = 1;
				break;
			}
		}
		if (flag == 1)
			break;
		head++;

	}

	cout << que[tail - 1].s;
	return 0;
}