基于邻接表的无向图的广度优先遍历c++代码

以下是基于邻接表的无向图的广度优先遍历的C代码：

#include <stdio.h>
#include <stdlib.h>
#define MAXV 1000 // 顶点数的最大值

typedef struct node *node_pointer;
struct node{
    int vertex; // 邻接点在顶点表中的下标
    node_pointer next; // 下一个邻接点
};
typedef struct graph *graph_pointer;
struct graph{
    node_pointer adj_list[MAXV];
    int nvertices; // 图中顶点数
};

int visited[MAXV];

void bfs(graph_pointer G, int start){
    int queue[MAXV], front = -1, rear = -1;
    node_pointer ptr;
    int v;

    queue[++rear] = start;
    visited[start] = 1;

    while(front != rear){
        v = queue[++front];
        printf("%d ", v); // 访问顶点v
        // 将顶点v的邻接点加入队列中
        for (ptr = G->adj_list[v]; ptr != NULL; ptr = ptr->next){
            if(!visited[ptr->vertex]){
                queue[++rear] = ptr->vertex;
                visited[ptr->vertex] = 1;
            }
        }
    }
}

int main(){
    graph_pointer G;
    int i, j, n, m, v1, v2;

    printf("输入顶点数和边数：");
    scanf("%d%d", &n, &m);

    G = (graph_pointer)malloc(sizeof(struct graph));
    G->nvertices = n;

    // 初始化邻接表
    for (i = 1; i <= n; i++){
        G->adj_list[i] = NULL;
    }

    // 建立邻接表
    for (i = 1; i <= m; i++){
        printf("输入一条边的两个顶点：");
        scanf("%d%d", &v1, &v2);

        node_pointer new_node1 = (node_pointer)malloc(sizeof(struct node));
        node_pointer new_node2 = (node_pointer)malloc(sizeof(struct node));
        new_node1->vertex = v2;
        new_node1->next = G->adj_list[v1];
        G->adj_list[v1] = new_node1;
        new_node2->vertex = v1;
        new_node2->next = G->adj_list[v2];
        G->adj_list[v2] = new_node2;
    }

    // 广度优先遍历图
    printf("广度优先遍历的结果：");
    for (i = 1; i <= n; i++){
        visited[i] = 0;
    }
    bfs(G, 1);

    return 0;
}

代码中，我们定义了一个结构体 `graph` 来存储邻接表，其中 `adj_list` 数组存储每个顶点的邻接点链表，`nvertices` 存储图中的顶点数。`node` 结构体用于定义邻接点，其中 `vertex` 存储邻接点在顶点表中的下标，`next` 存储下一个邻接点的指针。我们还定义了一个 `visited` 数组，用于标记每个顶点是否已经遍历过。

在 `main()` 函数中，我们首先从用户输入中读入图的顶点数和边数，然后利用 `malloc()` 动态分配 `graph` 结构体的存储空间。接着，我们初始化邻接表，将每个顶点的邻接点指针初始化为 `NULL`。然后，我们读入每一条边，并且根据边的两个顶点建立邻接表。最后，我们调用 `bfs()` 函数进行广度优先遍历，从顶点 `1` 开始遍历整个图。

`bfs()` 函数中，我们使用 `queue` 数组来存储待遍历的顶点，`front` 和 `rear` 分别指向队列的头和尾。我们首先将起始顶点 `start` 加入队列中，并标记为已访问。然后，我们不断从队列中取出一个顶点 `v`，访问该顶点，并将其邻接点加入队列中（如果邻接点尚未访问过）。这一过程一直持续到队列为空。