邻接矩阵存储的无向图环查找与打印问题求助

我最近做了大量调研，发现现有图环查找示例几乎都采用邻接表存储图，这其实会改变环的查找逻辑。我自己是用邻接矩阵来存储图的，下面是我的图代码片段：

#pragma once 
#include"edge1.h" 
#include <string> 
#include <iostream> 
#include <fstream> 
#include <ass...

目前遇到的问题是：找到的isCyclic函数无法适配邻接矩阵，而且没办法打印出找到的环。针对这个问题，我整理了适配邻接矩阵的环检测与环打印实现方案：

核心思路 #

邻接矩阵的遍历逻辑和邻接表不同，我们需要逐个检查矩阵中每个节点的所有邻接位置（即值为1的位置）。这里基于DFS实现，同时通过路径记录来打印环：

• 用visited数组标记已访问节点
• 用recursionStack数组标记当前递归栈中的节点，用于检测环
• 用path数组记录当前递归路径，找到环时直接从中提取并打印

完整适配代码 #

#pragma once
#include "edge1.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Graph {
private:
    int numVertices;
    vector<vector<int>> adjMatrix;
    vector<string> vertexLabels; // 用于更直观的节点名称打印

    bool isCyclicUtil(int v, vector<bool>& visited, vector<bool>& recursionStack, vector<int>& path) {
        if (!visited[v]) {
            visited[v] = true;
            recursionStack[v] = true;
            path.push_back(v);

            // 遍历当前节点的所有邻接节点（邻接矩阵方式）
            for (int i = 0; i < numVertices; ++i) {
                if (adjMatrix[v][i] == 1) { // 存在边
                    if (!visited[i] && isCyclicUtil(i, visited, recursionStack, path)) {
                        return true;
                    } else if (recursionStack[i]) {
                        // 找到环，开始打印
                        cout << "检测到环：";
                        auto cycleStart = find(path.begin(), path.end(), i);
                        for (; cycleStart != path.end(); ++cycleStart) {
                            cout << vertexLabels[*cycleStart] << " -> ";
                        }
                        cout << vertexLabels[i] << endl;
                        return true;
                    }
                }
            }
        }
        // 回溯：移除当前节点递归栈和路径
        recursionStack[v] = false;
        path.pop_back();
        return false;
    }

public:
    Graph(int vertices) : numVertices(vertices), adjMatrix(vertices, vector<int>(vertices, 0)) {
        vertexLabels.resize(vertices);
    }

    // 添加有向边
    void addEdge(int src, int dest) {
        if (src >= 0 && src < numVertices && dest >=0 && dest < numVertices) {
            adjMatrix[src][dest] = 1;
        }
    }

    // 设置节点标签（可选，用于打印时更清晰）
    void setVertexLabel(int idx, const string& label) {
        if (idx >=0 && idx < numVertices) {
            vertexLabels[idx] = label;
        }
    }

    // 对外暴露的环检测接口
    bool isCyclic() {
        vector<bool> visited(numVertices, false);
        vector<bool> recursionStack(numVertices, false);
        vector<int> path;

        // 遍历所有未访问节点，处理非连通图情况
        for (int i = 0; i < numVertices; ++i) {
            if (isCyclicUtil(i, visited, recursionStack, path)) {
                return true;
            }
        }
        cout << "图中不存在环" << endl;
        return false;
    }
};

// 测试用例
int main() {
    Graph g(4);
    g.setVertexLabel(0, "节点A");
    g.setVertexLabel(1, "节点B");
    g.setVertexLabel(2, "节点C");
    g.setVertexLabel(3, "节点D");

    g.addEdge(0, 1);
    g.addEdge(1, 2);
    g.addEdge(2, 0); // 形成环：A->B->C->A
    g.addEdge(2, 3);

    g.isCyclic();
    return 0;
}

关键细节说明 #

1. 邻接矩阵遍历适配：通过for (int i = 0; i < numVertices; ++i)遍历所有节点，判断adjMatrix[v][i] == 1来确认边的存在，这是和邻接表遍历最核心的区别
2. 环的打印逻辑：当发现邻接节点在当前递归栈中时，从path数组中找到该节点的起始位置，依次打印到当前节点，再补回起始节点，形成完整环
3. 无向图适配：如果是无向图，需要在addEdge中同时设置adjMatrix[dest][src] = 1，并且在isCyclicUtil中添加父节点参数，避免将父节点误判为环的一部分

内容的提问来源于stack exchange，提问作者user8787374