图的邻接表的深度优先遍历具体代码 c语言

以下是图的邻接表的深度优先遍历的具体代码，使用C语言实现：

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

#define MAX_VERTEX_NUM 100

typedef struct ArcNode { // 定义存储边的结构体
    int adjvex; // 指向邻接点的位置
    struct ArcNode* nextarc; // 指向下一条边的指针
} ArcNode;

typedef struct VertexNode { // 定义存储顶点的结构体
    int data; // 存储顶点的数据
    ArcNode* firstarc; // 指向第一条边的指针
} VertexNode;

typedef struct { // 定义图的结构体
    VertexNode vexs[MAX_VERTEX_NUM]; // 存储顶点的数组
    int vexnum, arcnum; // 存储顶点数和边数
} Graph;

void DFS(Graph* G, int v, int* visited) { // 深度优先遍历函数
    visited[v] = 1; // 标记当前顶点已访问
    printf("%d ", G->vexs[v].data); // 输出当前顶点的数据
    ArcNode* p = G->vexs[v].firstarc; // 指向当前顶点的第一条边
    while (p != NULL) { // 遍历当前顶点的所有邻接点
        if (!visited[p->adjvex]) { // 如果邻接点未被访问
            DFS(G, p->adjvex, visited); // 递归访问邻接点
        }
        p = p->nextarc; // 指向下一条边
    }
}

void DFSTraverse(Graph* G) { // 深度优先遍历图函数
    int visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点未被访问
    for (int i = 0; i < G->vexnum; i++) { // 遍历所有顶点
        if (!visited[i]) { // 如果顶点未被访问
            DFS(G, i, visited); // 深度优先遍历该连通分量
        }
    }
}

int main() {
    Graph G;
    G.vexnum = 5; // 顶点数为5
    G.arcnum = 7; // 边数为7
    G.vexs[0].data = 1;
    G.vexs[1].data = 2;
    G.vexs[2].data = 3;
    G.vexs[3].data = 4;
    G.vexs[4].data = 5;
    // 初始化边
    ArcNode* arc1 = (ArcNode*)malloc(sizeof(ArcNode));
    arc1->adjvex = 1;
    arc1->nextarc = NULL;
    G.vexs[0].firstarc = arc1;
    ArcNode* arc2 = (ArcNode*)malloc(sizeof(ArcNode));
    arc2->adjvex = 2;
    arc2->nextarc = NULL;
    arc1->nextarc = arc2;
    ArcNode* arc3 = (ArcNode*)malloc(sizeof(ArcNode));
    arc3->adjvex = 3;
    arc3->nextarc = NULL;
    G.vexs[1].firstarc = arc3;
    ArcNode* arc4 = (ArcNode*)malloc(sizeof(ArcNode));
    arc4->adjvex = 4;
    arc4->nextarc = NULL;
    G.vexs[2].firstarc = arc4;
    ArcNode* arc5 = (ArcNode*)malloc(sizeof(ArcNode));
    arc5->adjvex = 4;
    arc5->nextarc = NULL;
    arc3->nextarc = arc5;
    ArcNode* arc6 = (ArcNode*)malloc(sizeof(ArcNode));
    arc6->adjvex = 5;
    arc6->nextarc = NULL;
    G.vexs[3].firstarc = arc6;
    ArcNode* arc7 = (ArcNode*)malloc(sizeof(ArcNode));
    arc7->adjvex = 2;
    arc7->nextarc = NULL;
    arc4->nextarc = arc7;
    DFSTraverse(&G); // 深度优先遍历图
    return 0;
}

上述代码中，首先定义了存储边和顶点的结构体，然后定义了存储图的结构体。`DFS`函数实现了深度优先遍历的递归过程，`DFSTraverse`函数实现了深度优先遍历整个图的过程。在`main`函数中，我们首先创建了一个包含5个顶点和7条边的图，然后调用`DFSTraverse`函数进行深度优先遍历。