最小转机——图的广度优先遍历

输入

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

运行结果

2

题解

#include<stdio.h>
struct note{
    int x; //城市编号
    int s; //转机次数
};
int main(){
    struct note que[2501];
    int e[51][51] = {0}, book[51] = {0};
    int head, tail;

    int i, j, n, m, a, b, cur, start, end, flag = 0;
    scanf("%d %d %d %d",&n, &m, &start, &end);

    //初始化二维矩阵
    for (i = 1 ; i <= n ; i ++){
        for (j = 1; j <= m ; j ++){
            if (i == j) e[i][j] = 0;
            else e[i][j] = 99999999;
        }
    }

    //读入城市之间的航班
    for (i = 1 ; i <= m ; i ++){
        scanf("%d %d", &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[start] =1; //标记start号城市已在队列中

    //当前队列不对空的时候循环
    while (head < tail){
        cur = que[head].x;//当前队列中首城市的编号
        for (j = 1; j <= n ; j ++){
            if (e[cur][j] != 99999999 && book[j] == 0){
                que[tail].x = j;
                que[tail].s = que[head].s + 1; // 转机次数+1
                tail++;
                //标记城市j已经在队列中
                book[j] = 1;
            }

            //如果到达目标城市，停止扩展，任务结束，退出循环
            if (que[tail].x == end){
                flag = 1;
                break;
            }
        }
        if (flag == 1) break;
        head ++;
    }

    //打印队列中末尾最后一个（目标城市）的转机次数
    //注意tail是指向队列队尾（最后一位）的下一个位置，所以这需要-1
    printf("%d\n",que[tail-1].s);
    return 0;
}

运行结果：

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