图深度优先遍历c语言

图的深度优先遍历是一种遍历图的算法，它从图的某个顶点开始遍历，访问该顶点，然后依次访问该顶点的每个未被访问过的邻接点，直到所有与该顶点相邻的顶点都被访问过为止。然后回溯到前一个顶点，继续访问它的其他未被访问过的邻接点，直到所有顶点都被访问过为止。在C语言中，可以使用递归的方式实现图的深度优先遍历。具体实现方法可以参考引用中的代码示例。

相关问题

图的深度优先遍历C语言

在C语言中实现图的深度优先遍历可以使用邻接矩阵来表示图的结构，并使用递归的方式进行遍历。下面是一个示例代码：

#include <stdio.h>

#define MAX_SIZE 100

int visited[MAX_SIZE]; // 记录节点是否被访问过

// 邻接矩阵表示的图
int graph[MAX_SIZE][MAX_SIZE] = {
    {0, 1, 1, 0, 0},
    {1, 0, 0, 1, 1},
    {1, 0, 0, 0, 1},
    {0, 1, 0, 0, 0},
    {0, 1, 1, 0, 0}
};

// 深度优先遍历函数
void dfs(int vertex) {
    printf("%d ", vertex); // 输出当前节点
    visited[vertex] = 1; // 标记当前节点为已访问

    // 遍历当前节点的邻接节点
    for (int i = 0; i < MAX_SIZE; i++) {
        if (graph[vertex][i] == 1 && visited[i] == 0) {
            dfs(i); // 递归遍历邻接节点
        }
    }
}

int main() {
    // 初始化visited数组
    for (int i = 0; i < MAX_SIZE; i++) {
        visited[i] = 0;
    }

    printf("深度优先遍历结果：");
    dfs(0); // 从节点0开始深度优先遍历

    return 0;
}

运行以上代码，将输出图的深度优先遍历结果：0 1 3 4 2。

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

以下是C语言实现图的深度优先遍历的示例代码：

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

typedef struct ArcNode { // 边结点
    int adjvex; // 邻接点在数组中的位置下标
    struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;

typedef struct VNode { // 顶点结点
    char 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);
    getchar(); // 读取回车符
    printf("请输入顶点信息：\n");
    for (int i = 0; i < G->vexnum; i++) {
        scanf("%c", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;        visited[i] = 0; // 初始化访问标记数组
    }
    getchar(); // 读取回车符
    printf("请输入边信息：\n");
    for (int k = 0; k < G->arcnum; k++) {
        char v1, v2;
        printf("请输入第%d条边的两个顶点：", k + 1);
        scanf("%c%c", &v1, &v2);
        getchar(); // 读取回车符
        int i, j;
        for (i = 0; i < G->vexnum; i++) {
            if (G->vertices[i].data == v1) {
                break;
            }
        }
        for (j = 0; j < G->vexnum; j++) {
            if (G->vertices[j].data == v2) {
                break;
            }
        }
        ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        p = (ArcNode *)malloc(sizeof(ArcNode));
        p->adjvex = i;
        p->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = p;
    }
}

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

int main() {
    ALGraph G;
    CreateGraph(&G);
    printf("深度优先遍历结果为：");
    for (int i = 0; i < G.vexnum; i++) {
        if (visited[i] == 0) { // 如果该顶点未被访问，则从该顶点开始深度优先遍历
            DFS(G, i);
        }
    }
    printf("\n");
    return 0;
}