基于邻接表的广度优先遍历算法c语言

以下是基于邻接表的广度优先遍历算法的C语言实现：

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

#define MAX 100

// 邻接表结构体
typedef struct node {
    int vertex; // 顶点编号
    struct node* next; // 指向下一个邻接点的指针
} Node;

// 图结构体
typedef struct graph {
    Node* adjList[MAX]; // 邻接表数组
    int visited[MAX]; // 记录顶点是否被访问过的数组
} Graph;

// 初始化图
void initGraph(Graph* g, int n) {
    for (int i = 0; i < n; i++) {
        g->adjList[i] = NULL;
        g->visited[i] = 0;
    }
}

// 添加边
void addEdge(Graph* g, int u, int v) {
    // 添加u->v的边
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = g->adjList[u];
    g->adjList[u] = newNode;

    // 添加v->u的边
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = u;
    newNode->next = g->adjList[v];
    g->adjList[v] = newNode;
}

// 广度优先遍历
void bfs(Graph* g, int start) {
    int queue[MAX], front = 0, rear = 0;
    Node* temp;

    // 将起始顶点加入队列并标记为已访问
    queue[rear++] = start;
    g->visited[start] = 1;

    printf("BFS遍历结果：");

    while (front < rear) {
        // 出队列并访问
        int current = queue[front++];
        printf("%d ", current);

        // 将当前顶点的所有邻接点加入队列
        temp = g->adjList[current];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            if (g->visited[adjVertex] == 0) {
                queue[rear++] = adjVertex;
                g->visited[adjVertex] = 1;
            }
            temp = temp->next;
        }
    }
}

int main() {
    Graph g;
    int n, m, u, v;

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

    initGraph(&g, n);

    printf("请输入每条边的起点和终点：\n");
    for (int i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        addEdge(&g, u, v);
    }

    bfs(&g, 0);

    return 0;
}