邻接表表示法的深度优先遍历（C语言）

下面是邻接表表示法的深度优先遍历的C语言实现：

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

#define MAX_VERTEX_NUM 20

typedef struct ArcNode { // 存储边的结构体
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode *next; // 指向下一条边的指针
}ArcNode;

typedef struct VNode { // 存储顶点的结构体
    int data; // 顶点的数据信息
    ArcNode *firstarc; // 指向第一条依附于该顶点的边的指针
}VNode, AdjList[MAX_VERTEX_NUM];

typedef struct { // 存储图的结构体
    AdjList vertices; // 存储顶点的数组
    int vexnum, arcnum; // 记录顶点数和边数
}ALGraph;

void CreateGraph(ALGraph *G) { // 创建邻接表表示的图
    printf("请输入顶点数和边数：");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));

    printf("请输入%d个顶点的数据信息：", G->vexnum);
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL; // 初始化每个顶点的边表为空
    }

    printf("请输入%d条边（形如 x y）：", G->arcnum);
    int v1, v2;
    for (int i = 0; i < G->arcnum; i++) {
        scanf("%d%d", &v1, &v2);
        ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = v2;
        p->next = G->vertices[v1].firstarc;
        G->vertices[v1].firstarc = p; // 将这条边插入到 v1 的边表头部
    }
}

void DFS(ALGraph *G, int v, int *visited) { // 深度优先遍历
    visited[v] = 1; // 标记该顶点已被访问
    printf("%d ", G->vertices[v].data); // 输出该顶点的数据信息

    ArcNode *p = G->vertices[v].firstarc;
    while (p != NULL) { // 遍历 v 的所有邻接点
        if (!visited[p->adjvex]) { // 如果该邻接点未被访问过，则以该邻接点为起点递归进行遍历
            DFS(G, p->adjvex, visited);
        }
        p = p->next;
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);

    int visited[MAX_VERTEX_NUM] = { 0 }; // 标记数组初始化为0，表示所有顶点均未被访问过

    printf("深度优先遍历结果：");
    for (int i = 0; i < G.vexnum; i++) { // 遍历所有顶点，确保连通图中所有顶点都被访问到
        if (!visited[i]) { // 如果该顶点未被访问，则以该顶点为起点进行深度优先遍历
            DFS(&G, i, visited);
        }
    }

    return 0;
}

注意：上述代码中的 `CreateGraph` 函数只是一个简单的创建图的函数，仅适用于无向图。对于有向图或其他更复杂的情况，需要根据具体情况进行修改。