C语言实现图的深度优先遍历（邻接矩阵）

本文将介绍如何使用 C 语言，通过输入创建邻接矩阵表示的图，并使用深度优先遍历算法对该图进行遍历。

代码实现

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

#define MAX_VERTEX_NUM 20 // 最大顶点数

ty typedef struct {
    char vertex[MAX_VERTEX_NUM]; // 顶点数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num; // 顶点数
    int edge_num; // 边数
} Graph;

void createGraph(Graph* g) {
    printf("请输入图的顶点数和边数（用空格隔开）：");
    scanf("%d %d", &g->vertex_num, &g->edge_num);

    // 初始化邻接矩阵
    for (int i = 0; i < g->vertex_num; i++) {
        for (int j = 0; j < g->vertex_num; j++) {
            g->edge[i][j] = 0;
        }
    }

    // 输入顶点
    printf("请输入每个顶点的名称（用空格隔开）：");
    for (int i = 0; i < g->vertex_num; i++) {
        scanf(" %c", &g->vertex[i]);
    }

    // 输入边
    printf("请输入每条边的起点和终点（用空格隔开）：\n");
    for (int i = 0; i < g->edge_num; i++) {
        char start, end;
        scanf(" %c %c", &start, &end);
        int start_index, end_index;
        for (int j = 0; j < g->vertex_num; j++) {
            if (g->vertex[j] == start) {
                start_index = j;
            }
            if (g->vertex[j] == end) {
                end_index = j;
            }
        }
        g->edge[start_index][end_index] = 1;
        g->edge[end_index][start_index] = 1;
    }
}

void dfs(Graph* g, int v, int* visited) {
    visited[v] = 1;
    printf("%c ", g->vertex[v]);
    for (int i = 0; i < g->vertex_num; i++) {
        if (g->edge[v][i] == 1 && visited[i] == 0) {
            dfs(g, i, visited);
        }
    }
}

void dfsTraversal(Graph* g) {
    int visited[MAX_VERTEX_NUM] = { 0 };
    printf("深度优先遍历结果为：");
    for (int i = 0; i < g->vertex_num; i++) {
        if (visited[i] == 0) {
            dfs(g, i, visited);
        }
    }
}

int main() {
    Graph g;
    createGraph(&g);
    dfsTraversal(&g);
    return 0;
}

使用示例

输入：

请输入图的顶点数和边数（用空格隔开）：5 7
请输入每个顶点的名称（用空格隔开）：A B C D E
请输入每条边的起点和终点（用空格隔开）：
A B
A C
A E
B C
B D
C D
D E

输出：

深度优先遍历结果为：A B C D E

代码解释

1. 创建图
   • createGraph 函数用于创建图。它首先从用户输入获取顶点数和边数，然后初始化邻接矩阵，并将每个顶点和边信息存储在图结构中。
2. 深度优先遍历
   • dfs 函数实现深度优先遍历算法。它递归地访问与当前顶点相连的所有未访问顶点。
   • dfsTraversal 函数从图的第一个顶点开始，对每个未访问过的顶点调用 dfs 函数，从而实现对整个图的深度优先遍历。

总结

本文提供了一个使用 C 语言实现图的深度优先遍历的完整代码示例。通过使用邻接矩阵，我们可以方便地表示图结构并进行深度优先遍历。你可以根据自己的需求修改代码，例如添加其他图算法或修改图的表示方式。