c语言邻接表及广度遍历

邻接表是图的一种表示方法，其基本思想是将每个顶点作为一个结点，对于每个结点，用一个单链表来存储所有与之相邻的结点。下面是一个简单的C语言实现：

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

#define MAX_VERTICES 100

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

typedef struct graph {
    int num_vertices;       // 图中顶点的个数
    Node *adj_list[MAX_VERTICES];    // 存储邻接表的数组
} Graph;

// 初始化图
void init_graph(Graph *g, int num_vertices) {
    g->num_vertices = num_vertices;
    for (int i = 0; i < num_vertices; ++i) {
        g->adj_list[i] = NULL;
    }
}

// 添加边
void add_edge(Graph *g, int src, int dest) {
    Node *new_node = (Node *)malloc(sizeof(Node));
    new_node->vertex = dest;
    new_node->next = g->adj_list[src];
    g->adj_list[src] = new_node;
}

// 广度优先遍历
void bfs(Graph *g, int start) {
    int visited[MAX_VERTICES] = {0};    // 标记每个结点是否被访问过
    int queue[MAX_VERTICES];            // 存储待访问结点的队列
    int front = 0, rear = 0;            // 队列的前后指针
    queue[rear++] = start;
    visited[start] = 1;
    printf("%d ", start);
    while (front != rear) {
        int curr = queue[front++];
        Node *adj_node = g->adj_list[curr];
        while (adj_node != NULL) {
            int v = adj_node->vertex;
            if (!visited[v]) {
                visited[v] = 1;
                queue[rear++] = v;
                printf("%d ", v);
            }
            adj_node = adj_node->next;
        }
    }
}

int main() {
    Graph g;
    init_graph(&g, 4);
    add_edge(&g, 0, 1);
    add_edge(&g, 0, 2);
    add_edge(&g, 1, 2);
    add_edge(&g, 2, 0);
    add_edge(&g, 2, 3);
    add_edge(&g, 3, 3);
    bfs(&g, 2);
    return 0;
}

上面的代码实现了创建一个包含4个顶点的图，并添加了6条边。最后使用广度优先遍历算法从结点2开始遍历整个图，并输出访问顺序。