图的邻接表表示法及遍历C语言实现

邻接表是一种图的表示方法，它以每个节点为基础，对每个节点的相邻节点进行链式存储。邻接表由一个数组和一个链表组成，数组中每个元素对应一个节点，链表中则存储与该节点相邻的节点。以下是邻接表的C语言实现：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

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

// 顶点表结构体
typedef struct {
    int data;       // 顶点信息
    ArcNode *first; // 指向第一个邻接点的指针
} VNode;

// 图结构体
typedef struct {
    VNode vertex[MAX_VERTEX_NUM]; // 顶点表
    int vexnum;                   // 顶点数
    int arcnum;                   // 边数
} ALGraph;

// 遍历图
void DFS(ALGraph *G, int v, int *visited) {
    printf("%d ", G->vertex[v].data);
    visited[v] = 1;  // 标记当前节点已被访问
    ArcNode *p = G->vertex[v].first;
    while (p != NULL) {
        if (visited[p->adjvex] == 0) {
            DFS(G, p->adjvex, visited);
        }
        p = p->nextarc;
    }
}

// 创建图
void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for (int i = 0; i < G->vexnum; i++) {
        printf("请输入第 %d 个顶点信息：", i + 1);
        scanf("%d", &G->vertex[i].data);
        G->vertex[i].first = NULL;
    }
    for (int i = 0; i < G->arcnum; i++) {
        printf("请输入第 %d 条边的起点和终点：", i + 1);
        int start, end;
        scanf("%d %d", &start, &end);
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = end - 1;
        p->nextarc = G->vertex[start - 1].first;
        G->vertex[start - 1].first = p;
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    int visited[MAX_VERTEX_NUM] = {0};  // 记录节点是否被访问过的数组
    printf("DFS遍历结果为：");
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) {
            DFS(&G, i, visited);
        }
    }
    return 0;
}

在上面的代码中，我们定义了两个结构体，分别是顶点表结构体和边表结构体。创建图时，我们先输入顶点数和边数，然后依次输入每个顶点的信息，再输入每条边的起点和终点，将边加入到邻接表中。遍历图时，我们使用DFS算法进行遍历，从每个未被访问过的节点开始递归遍历其相邻节点。