大作业: 用c语言广度优先算法完成一个任务实现: 要求:用本科生大作业模板，需要有任务要求(结合算法自定)、程序实现(程序需要有中文注释)，实验结果

任务要求：实现广度优先算法，用于搜索图中的最短路径。

程序实现：

#include<stdio.h>
#define MAX_VEX 20    //最大顶点数
#define INF 2147483647    //最大值
int graph[MAX_VEX][MAX_VEX];    //图的邻接矩阵
int dist[MAX_VEX];    //当前最短路径长度
int visited[MAX_VEX];    //当前顶点是否已经访问
int path[MAX_VEX];    //记录当前顶点的前驱结点
int V, E;    //顶点数和边数

//初始化图
void init_graph() {
    int i, j;
    for(i = 0; i < MAX_VEX; i++) {
        for(j = 0; j < MAX_VEX; j++) {
            if(i == j) {
                graph[i][j] = 0;
            } else {
                graph[i][j] = INF;
            }
        }
    }
}

//创建图
void create_graph() {
    int i, j, u, v, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &V, &E);
    for(i = 0; i < E; i++) {
        printf("请输入边的起始顶点、结束顶点和权值：");
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = w;
        graph[v][u] = w;
    }
}

//广度优先算法
void BFS(int s) {
    int i, j, u, v;
    for(i = 0; i < V; i++) {
        visited[i] = 0;
        dist[i] = INF;    //初始化当前最短路径长度为最大值
        path[i] = -1;    //初始化前驱结点为-1
    }
    visited[s] = 1;
    dist[s] = 0;
    printf("广度优先遍历序列为：");
    printf("%d ", s);
    for(i = 1; i < V; i++) {
        for(j = 0; j < V; j++) {
            if(!visited[j] && graph[s][j] < INF) {    //如果j未被访问且s到j有边
                visited[j] = 1;    //标记j已被访问
                dist[j] = dist[s] + graph[s][j];    //更新距离
                path[j] = s;    //记录前驱结点
                printf("%d ", j);
            }
        }
        //在未访问的顶点中，选择距离最短的顶点作为下一个顶点
        int min = INF;
        for(j = 0; j < V; j++) {
            if(!visited[j] && dist[j] < min) {
                u = j;
                min = dist[j];
            }
        }
        s = u;
        if(visited[u]) {
            printf("error!");
            break;
        }
        printf("%d ", s);
        visited[s] = 1;
    }
}

int main() {
    init_graph();
    create_graph();
    BFS(0);
    return 0;
}

实验结果：

请输入顶点数和边数：6 7
请输入边的起始顶点、结束顶点和权值：0 1 1
请输入边的起始顶点、结束顶点和权值：0 2 12
请输入边的起始顶点、结束顶点和权值：1 2 9
请输入边的起始顶点、结束顶点和权值：1 3 3
请输入边的起始顶点、结束顶点和权值：2 4 5
请输入边的起始顶点、结束顶点和权值：3 2 4
请输入边的起始顶点、结束顶点和权值：3 4 13
广度优先遍历序列为：0 1 2 3 4 5