c语言基于邻接表存储有向图的广度优先遍历

首先，我们需要定义邻接表和队列的结构体。

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

// 定义队列结构体
typedef struct queue {
    int front;  // 队首指针
    int rear;  // 队尾指针
    int size;  // 队列长度
    int capacity;  // 队列容量
    int* data;  // 存储队列元素的指针
} Queue;

然后，我们需要实现广度优先遍历算法的函数。该函数以邻接表和起始顶点作为参数，返回遍历结果。

// 广度优先遍历算法
void bfs(Node** graph, int start, int* visited, int n) {
    Queue* q = createQueue(n);  // 创建队列
    visited[start] = 1;  // 标记起始顶点已被访问
    enqueue(q, start);  // 将起始顶点入队

    while (!isEmpty(q)) {
        int v = dequeue(q);  // 出队一个顶点
        printf("%d ", v);  // 输出该顶点
        Node* p = graph[v];  // 获取该顶点的邻接表头结点
        while (p != NULL) {
            int w = p->vertex;  // 获取该顶点的邻接点
            if (!visited[w]) {  // 如果该邻接点未被访问
                visited[w] = 1;  // 标记该邻接点已被访问
                enqueue(q, w);  // 将该邻接点入队
            }
            p = p->next;  // 继续遍历该顶点的邻接表
        }
    }
}

其中，`graph`表示邻接表，`start`表示起始顶点，`visited`表示顶点是否被访问的数组，`n`表示顶点数量。函数中使用了队列来实现广度优先遍历。