BFS算法之地铁路线问题C语言代码

以下是地铁路线问题的BFS算法C语言代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_STATION 100 // 最大站点数
#define MAX_LINE 10 // 最大地铁线路数
#define INF 0x3f3f3f3f // 无穷大

int graph[MAX_STATION][MAX_STATION]; // 存储地铁线路图
int line[MAX_STATION][MAX_STATION]; // 存储站点所属地铁线路
int dis[MAX_STATION]; // 存储起点到各个站点的最短距离
int pre[MAX_STATION]; // 存储最短路径上各个站点的前驱节点
bool vis[MAX_STATION]; // 存储各个站点是否已访问
int n, m; // 站点数，地铁线路数

void bfs(int s, int t) {
    for (int i = 1; i <= n; i++) {
        dis[i] = INF;
        pre[i] = -1;
        vis[i] = false;
    }
    dis[s] = 0;
    vis[s] = true;
    int queue[MAX_STATION], front = 0, rear = 0;
    queue[rear++] = s;
    while (front < rear) {
        int u = queue[front++];
        for (int v = 1; v <= n; v++) {
            if (graph[u][v] && !vis[v]) {
                dis[v] = dis[u] + 1;
                pre[v] = u;
                vis[v] = true;
                queue[rear++] = v;
                if (v == t) {
                    return;
                }
            }
        }
    }
}

void print_path(int s, int t) {
    if (pre[t] == -1) {
        printf("不存在路径\n");
        return;
    }
    int path[MAX_STATION], top = 0;
    for (int u = t; u != s; u = pre[u]) {
        path[top++] = u;
    }
    path[top++] = s;
    printf("最短路径为：");
    for (int i = top - 1; i >= 0; i--) {
        printf("%d", path[i]);
        if (i > 0) {
            printf(" -> ");
        }
    }
    printf("\n");
}

int main() {
    printf("请输入站点数和地铁线路数：");
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        printf("请输入第%d条地铁线路的站点数：", i + 1);
        int k;
        scanf("%d", &k);
        int last, cur;
        scanf("%d", &last);
        for (int j = 1; j < k; j++) {
            scanf("%d", &cur);
            graph[last][cur] = graph[cur][last] = 1;
            line[last][cur] = line[cur][last] = i + 1;
            last = cur;
        }
    }
    printf("请输入起点和终点：");
    int s, t;
    scanf("%d%d", &s, &t);
    bfs(s, t);
    printf("起点到各个站点的最短距离：\n");
    for (int i = 1; i <= n; i++) {
        printf("%d ", dis[i]);
    }
    printf("\n");
    print_path(s, t);
    return 0;
}

注意，该代码中的地铁线路图是无向图，每个站点之间距离为1，即任意两个站点之间的距离都为1，因为这里只考虑了站点之间的直接连接，而没有考虑地铁线路的运行方向和经过时间等因素。如果需要考虑这些因素，需要对代码进行相应的修改。