C语言邻接表建立图并遍历

邻接表是图的一种常见存储方式，一般用链表实现。下面是C语言邻接表建立图并遍历的示例代码：

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

#define MAX_VERTEX_NUM 20 // 顶点数的最大值

// 邻接表结构体定义
typedef struct ArcNode {
    int adjvex; // 指向的顶点编号
    struct ArcNode *next; // 指向下一个边的指针
} ArcNode;

typedef struct VertexNode {
    int data; // 顶点的数据
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VertexNode, AdjList[MAX_VERTEX_NUM];

typedef struct Graph {
    AdjList vertices; // 邻接表数组
    int vexnum, arcnum; // 图的顶点数和边数
} Graph;

// 初始化图
void InitGraph(Graph *G, int n) {
    G->vexnum = n;
    G->arcnum = 0;
    for (int i = 0; i < n; ++i) {
        G->vertices[i].data = i; // 顶点的数据为编号
        G->vertices[i].firstarc = NULL; // 初始化边表为空
    }
}

// 插入边
void InsertArc(Graph *G, int v, int w) {
    ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
    p->adjvex = w;
    p->next = G->vertices[v].firstarc;
    G->vertices[v].firstarc = p;
    ++G->arcnum;
}

// 深度优先遍历
void DFS(Graph *G, int v, int *visited) {
    printf("%d ", v);
    visited[v] = 1;
    ArcNode *p = G->vertices[v].firstarc;
    while (p) {
        if (!visited[p->adjvex]) {
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

// 广度优先遍历
void BFS(Graph *G, int v, int *visited) {
    int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
    printf("%d ", v);
    visited[v] = 1;
    queue[rear++] = v;
    while (front < rear) {
        int w = queue[front++];
        ArcNode *p = G->vertices[w].firstarc;
        while (p) {
            if (!visited[p->adjvex]) {
                printf("%d ", p->adjvex);
                visited[p->adjvex] = 1;
                queue[rear++] = p->adjvex;
            }
            p = p->next;
        }
    }
}

int main() {
    Graph G;
    int n = 5; // 图的顶点数
    InitGraph(&G, n);
    InsertArc(&G, 0, 1);
    InsertArc(&G, 0, 2);
    InsertArc(&G, 1, 2);
    InsertArc(&G, 1, 3);
    InsertArc(&G, 2, 1);
    InsertArc(&G, 2, 3);
    InsertArc(&G, 2, 4);
    InsertArc(&G, 3, 4);
    printf("DFS: ");
    int visited[MAX_VERTEX_NUM] = {0};
    DFS(&G, 0, visited);
    printf("\n");
    printf("BFS: ");
    for (int i = 0; i < n; ++i) {
        visited[i] = 0;
    }
    BFS(&G, 0, visited);
    printf("\n");
    return 0;
}

上述代码中，`Graph` 结构体表示邻接表存储的图，其中 `AdjList` 数组是邻接表数组，每个元素都是 `VertexNode` 结构体，表示一个顶点。`ArcNode` 结构体表示一条边，每个顶点都有一个链表，其中存储了以该顶点为起点的所有边。`InitGraph` 函数用于初始化一个空图，`InsertArc` 函数用于插入一条边。`DFS` 和 `BFS` 分别表示深度优先遍历和广度优先遍历。在遍历时，需要使用一个 `visited` 数组来记录每个顶点是否已经被访问过。