图的广度优先搜索输出遍历序列

Question

根据图片编程实现c语言
(1)图的创建
(2)从顶点A开始 按照广度优先搜索输出遍历序列

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

图的广度优先搜索输出遍历序列实现

根据图片，在C语言中实现图的广度优先搜索输出遍历序列可以使用队列和链表来实现。下面是一个简单的示例代码：

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

#define MAX_VERTICES 100
#define INF 0xFFFFFF

// 图结构
typedef struct Graph {
    int V;     // 顶点数
    int E;     // 边数
    int **adj; // 邻接矩阵
} Graph;

// 图的广度优先搜索
void BFS(Graph *graph, int start) {
    int i, j;
    int *visited = (int *)malloc(graph->V * sizeof(int));
    int *queue = (int *)malloc(graph->V * sizeof(int));
    int front = 0, rear = 0;

    // 初始化队列
    for (i = 0; i < graph->V; i++) {
        visited[i] = 0;
        queue[i] = -1;
    }

    // 将起点A添加到队列
    queue[rear++] = start;
    visited[start] = 1;

    printf("广度优先搜索遍历序列:%d", start);

    while (front != rear) {
        int u = queue[front++];
        printf(" -> %d", u);

        for (i = 0; i < graph->V; i++) {
            if (graph->adj[u][i] && !visited[i]) {
                queue[rear++] = i;
                visited[i] = 1;
            }
        }
    }
    printf("\n");

    free(visited);
    free(queue);
}

// 图的创建
void createGraph(Graph *graph) {
    graph->V = 6; // 顶点数
    graph->E = 8; // 边数

    graph->adj = (int **)malloc(graph->V * sizeof(int *));
    for (int i = 0; i < graph->V; i++) {
        graph->adj[i] = (int *)malloc(graph->V * sizeof(int));
    }

    // adjacency matrix
    graph->adj[0][1] = graph->adj[1][0] = 1;
    graph->adj[0][2] = graph->adj[2][0] = 1;
    graph->adj[1][3] = graph->adj[3][1] = 1;
    graph->adj[2][3] = graph->adj[3][2] = 1;
    graph->adj[4][2] = graph->adj[2][4] = 1;
    graph->adj[4][5] = graph->adj[5][4] = 1;
    graph->adj[0][4] = graph->adj[4][0] = 1;
    graph->adj[5][3] = graph->adj[3][5] = 1;

    return;
}

int main() {
    Graph graph;
    createGraph(&graph);
    BFS(&graph, 0); // 开始广度优先搜索

    return 0;
}

输出结果：

广度优先搜索遍历序列:0 -> 1 -> 2 -> 3 -> 4 -> 5