C语言数据结构图的遍历

Question

求解，进行有向带权图（邻接矩阵）深度优先遍历代码运行时遇到报错无法解决，求大家帮忙😭

Answer 1

引自免费微信小程序：皆我百晓生

在您提供的C语言代码片段中，确实存在一个变量“visited”重定义的错误。根据您的描述，您正在尝试实现基于邻接矩阵表示的有向带权图的深度优先遍历（DFS）。首先，我们需要修复变量重定义问题，并整理代码结构。

以下是修改后的完整代码：

#define MAX_VERTEX_NUM 20

typedef struct {
    char vexs[MAX_VERTEX_NUM]; // 顶点数组
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵表示的边
    int vexnum; // 顶点数量
} MGraph;

// 初始化访问标志数组
void initVisited(int visited[MAX_VERTEX_NUM]) {
    for (int i = 0; i < MAX_VERTEX_NUM; i++) {
        visited[i] = 0;
    }
}

// 深度优先遍历递归函数
void DFS(MGraph G, int i, int visited[MAX_VERTEX_NUM]) {
    visited[i] = 1;
    printf(" %c ", G.vexs[i]);

    for (int j = 0; j < G.vexnum; j++) {
        if (G.arcs[i][j] == 1 && !visited[j]) {
            DFS(G, j, visited);
        }
    }
}

// 深度优先遍历主函数
void DFSTraverse(MGraph G) {
    int visited[MAX_VERTEX_NUM];
    initVisited(visited);

    // 从任意一个未访问过的顶点开始遍历
    for (int i = 0; i < G.vexnum; i++) {
        if (!visited[i]) {
            DFS(G, i, visited);
            printf("\n"); // 在每个连通分量遍历结束后换行
        }
    }
}

请注意，在实际项目中，请确保MAX_VERTEX_NUM与您图的实际顶点数相匹配。此外，由于是邻接矩阵表示的有向图，所以当(i, j)位置的值为1时，表示从顶点i到顶点j有一条边。在遍历时要特别注意处理非连通图的情况，即从一个未访问过的顶点开始，对整个图进行多次DFS调用，直到所有连通分量都被访问过。