C语言实现图的深度优先遍历

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

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

#define MAX_VERTEX_NUM 100

// 邻接表中的链表结构体
typedef struct ArcNode {
    int adjvex;  // 相邻节点的下标
    struct ArcNode *next;
} ArcNode;

// 邻接表中的顶点结构体
typedef struct VNode {
    char data;  // 顶点数据
    ArcNode *firstarc;  // 指向第一个相邻节点的指针
} VNode;

// 图结构体
typedef struct {
    VNode adjlist[MAX_VERTEX_NUM];  // 邻接表
    int vexnum, arcnum;  // 顶点数和边数
} Graph;

// 创建图
void create_graph(Graph *G) {
    printf("请输入顶点数和边数：");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));

    // 输入顶点信息
    printf("请输入顶点信息：");
    for (int i = 0; i < G->vexnum; i++) {
        getchar();  // 吃掉上一个回车符
        scanf("%c", &(G->adjlist[i].data));
        G->adjlist[i].firstarc = NULL;
    }

    // 输入边信息
    printf("请输入边信息（格式为：vi vj）：\n");
    for (int k = 0; k < G->arcnum; k++) {
        int i, j;
        scanf("%d%d", &i, &j);

        // 创建一个新的相邻节点
        ArcNode *new_node = (ArcNode *) malloc(sizeof(ArcNode));
        new_node->adjvex = j;
        new_node->next = G->adjlist[i].firstarc;
        G->adjlist[i].firstarc = new_node;

        // 无向图需要添加反向边
        new_node = (ArcNode *) malloc(sizeof(ArcNode));
        new_node->adjvex = i;
        new_node->next = G->adjlist[j].firstarc;
        G->adjlist[j].firstarc = new_node;
    }
}

// 深度优先遍历
void DFS(Graph G, int v, int *visited) {
    printf("%c ", G.adjlist[v].data);
    visited[v] = 1;  // 标记为已访问

    // 遍历当前节点的所有相邻节点
    ArcNode *p = G.adjlist[v].firstarc;
    while (p != NULL) {
        int w = p->adjvex;
        if (!visited[w]) {  // 如果相邻节点未被访问
            DFS(G, w, visited);  // 递归遍历相邻节点
        }
        p = p->next;
    }
}

// 遍历图
void traverse(Graph G) {
    int visited[MAX_VERTEX_NUM] = {0};  // 标记数组，用于记录每个节点是否被访问过

    printf("深度优先遍历结果：");
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {  // 如果节点未被访问
            DFS(G, i, visited);  // 从该节点开始进行深度优先遍历
        }
    }
}

int main() {
    Graph G;
    create_graph(&G);
    traverse(G);
    return 0;
}

该代码实现了一个使用邻接表存储的无向图的深度优先遍历。在遍历时，我们使用一个标记数组记录每个节点是否被访问过，以避免重复访问。具体实现时，我们首先遍历某个节点，并标记该节点为已访问。然后遍历该节点的所有相邻节点，如果某个相邻节点未被访问，则递归遍历该节点。这样可以保证整个图被遍历一遍，并输出每个节点的信息。

需要注意的是，在创建邻接表时，我们需要为每个相邻节点分别创建一个新的节点，并插入到对应节点的链表中。同时，由于是无向图，我们需要为每条边都添加反向边。