c语言邻接表输出及广度遍历

邻接表是图的一种常见存储方式，可以用来表示有向图和无向图。下面是C语言邻接表的输出及广度遍历的示例代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

// 边表结点
typedef struct ArcNode {
    int adjvex; // 邻接点下标
    struct ArcNode *next; // 指向下一个邻接点的指针
} ArcNode;

// 顶点表结点
typedef struct {
    int data; // 顶点的数据
    ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];

// 邻接表结构体
typedef struct {
    AdjList vertices; // 顶点表
    int vexnum, arcnum; // 顶点数和边数
} ALGraph;

// 初始化邻接表
void InitGraph(ALGraph *G) {
    int i;
    G->vexnum = 0;
    G->arcnum = 0;
    for (i = 0; i < MAX_VERTEX_NUM; i++) {
        G->vertices[i].firstarc = NULL;
    }
}

// 添加边
void AddArc(ALGraph *G, int v, int w) {
    ArcNode *p;
    p = (ArcNode *)malloc(sizeof(ArcNode));
    p->adjvex = w;
    p->next = G->vertices[v].firstarc;
    G->vertices[v].firstarc = p;
    G->arcnum++;
}

// 输出邻接表
void PrintGraph(ALGraph *G) {
    int i;
    ArcNode *p;
    for (i = 0; i < G->vexnum; i++) {
        printf("%d: ", G->vertices[i].data);
        p = G->vertices[i].firstarc;
        while (p != NULL) {
            printf("%d ", G->vertices[p->adjvex].data);
            p = p->next;
        }
        printf("\n");
    }
}

// 广度优先遍历
void BFS(ALGraph *G, int v) {
    int visited[MAX_VERTEX_NUM] = {0}; // 记录每个顶点是否被访问过
    int queue[MAX_VERTEX_NUM]; // 队列
    int front = 0, rear = 0;
    ArcNode *p;
    visited[v] = 1;
    queue[rear++] = v;
    while (front < rear) {
        int u = queue[front++]; // 出队
        printf("%d ", G->vertices[u].data);
        p = G->vertices[u].firstarc;
        while (p != NULL) {
            int w = p->adjvex;
            if (!visited[w]) {
                visited[w] = 1;
                queue[rear++] = w; // 入队
            }
            p = p->next;
        }
    }
}

int main() {
    ALGraph G;
    InitGraph(&G);
    G.vexnum = 5;
    G.arcnum = 7;
    G.vertices[0].data = 0;
    G.vertices[1].data = 1;
    G.vertices[2].data = 2;
    G.vertices[3].data = 3;
    G.vertices[4].data = 4;
    AddArc(&G, 0, 1);
    AddArc(&G, 0, 2);
    AddArc(&G, 1, 2);
    AddArc(&G, 2, 0);
    AddArc(&G, 2, 3);
    AddArc(&G, 3, 3);
    AddArc(&G, 4, 3);
    printf("邻接表：\n");
    PrintGraph(&G);
    printf("广度遍历：\n");
    BFS(&G, 2);
    printf("\n");
    return 0;
}

上述代码中，邻接表结构体`ALGraph`包含顶点表`vertices`和顶点数`vexnum`、边数`arcnum`两个成员。其中，顶点表是一个数组，每个元素是一个顶点表结点`VNode`，包含该顶点的数据`data`和指向第一个邻接点的指针`firstarc`。邻接点则是边表结点`ArcNode`，包含邻接点下标`adjvex`和指向下一个邻接点的指针`next`。

`InitGraph`函数用来初始化邻接表，`AddArc`函数用来添加边，`PrintGraph`函数用来输出邻接表，`BFS`函数用来进行广度优先遍历。

在示例代码中，我们创建了一个包含5个顶点和7条边的无向图，并对其进行了广度遍历。输出结果为：

邻接表：
0: 2 1 
1: 2 
2: 3 0 1 
3: 3 
4: 
广度遍历：
2 0 1 3