图的深度优先搜索c语言

以下是使用C语言实现图的深度优先搜索的示例代码：

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

#define MAX_VERTEX_NUM 100 // 最大顶点数

typedef struct ArcNode {
    int adjvex; // 该弧所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;

typedef struct VNode {
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices; // 图中顶点及其邻接表
    int vexnum, arcnum; // 顶点数和弧数
} ALGraph;

int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过

void CreateGraph(ALGraph *G) {
    printf("请输入顶点数和弧数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入每个顶点的信息：");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    printf("请输入每条弧的起点和终点：");
    for (int i = 0; i < G->arcnum; i++) {
        int start, end;
        scanf("%d%d", &start, &end);
        ArcNode *arc = (ArcNode *)malloc(sizeof(ArcNode));
        arc->adjvex = end;
        arc->nextarc = G->vertices[start].firstarc;
        G->vertices[start].firstarc = arc;
    }
}

void DFS(ALGraph *G, int v) {
    visited[v] = 1; // 标记该顶点已被访问
    printf("%d ", G->vertices[v].data); // 输出该顶点的信息
    ArcNode *arc = G->vertices[v].firstarc;
    while (arc != NULL) {
        int w = arc->adjvex;
        if (!visited[w]) { // 如果该顶点未被访问，则递归访问它
            DFS(G, w);
        }
        arc = arc->nextarc;
    }
}

void DFSTraverse(ALGraph *G) {
    for (int i = 0; i < G->vexnum; i++) {
        visited[i] = 0; // 初始化visited数组
    }
    for (int i = 0; i < G->vexnum; i++) {
        if (!visited[i]) { // 如果该顶点未被访问，则从该顶点开始深度优先搜索
            DFS(G, i);
        }
    }
}

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("深度优先搜索结果为：");
    DFSTraverse(&G);
    return 0;
}