为何我的DFS算法在无向图中检测出额外的环？

我正在学习图论，尝试用DFS算法遍历无向图的所有节点并检测环。以下是我的C++实现代码：

#include <bits/stdc++.h>
using namespace std;

class Graph
{
public:
    // each node has its own adjacency list
    map<int, list<int>> adj;
    // checking if each node has been visited or not
    map<int, bool> visited;

    void addEdge(int n1, int n2);

    void DFS(int v, int w);
};

void Graph::addEdge(int n1, int n2)
{
    // add each other to their own adjacency list
    adj[n1].push_back(n2);
    adj[n2].push_back(n1);
}

void Graph::DFS(int par, int cur)
{
    // mark current node as visited
    visited[cur] = true;

    cout << cur << "\n";

    // for each node adjacent
    for (auto &i : adj[cur])
    {
        // if it has been visited and it is not the parent node (detects a cycle)
        if (visited[i] && i != par)
        {
            cout << "Cycle detected! | ";
            cout << "Adjacent node: " << i << " | ";
            cout << "Parent node: " << par << "\n";
        }

        // run DFS from unvisited node
        if (!visited[i])
        {
            DFS(cur, i);
        }
    }
}

int main()
{
    // create graph
    Graph graph;
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(1, 3);
    graph.addEdge(2, 5);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(4, 6);

    // run DFS on the first node
    graph.DFS(0, 0);
}

对应的图结构如下：

运行代码后得到输出：

0
1
2
5
3
Cycle detected! | Adjacent node: 1 | Parent node: 2
4
6
Cycle detected! | Adjacent node: 3 | Parent node: 0

程序在搜索即将结束时额外检测出一个环，我找不到代码中的问题，恳请帮忙排查原因。

问题分析与修复 #

问题出在DFS初始调用的参数设置和环检测逻辑的冲突：

你调用DFS(0, 0)时，初始父节点par和当前节点cur都是0。当DFS回溯到根节点0时，遍历它的邻接节点1——此时1已被访问，且i != par（1≠0），触发了环检测条件，但这只是无向图中正常的双向边（0→1的反向边），并非真正的环。

修复方案：

调整环检测逻辑，先跳过父节点，再判断剩余邻接节点是否已访问——若已访问则判定为环。优化后的DFS函数：

void Graph::DFS(int par, int cur)
{
    visited[cur] = true;
    cout << cur << "\n";

    for (auto &i : adj[cur])
    {
        // 先跳过父节点，避免双向边误判
        if (i == par)
            continue;
            
        // 剩余已访问节点必然是环的一部分
        if (visited[i])
        {
            cout << "Cycle detected! | ";
            cout << "Adjacent node: " << i << " | ";
            cout << "Current node: " << cur << "\n";
        }
        else
        {
            DFS(cur, i);
        }
    }
}

修复原理：

无向图中，每个边都是双向的，因此遍历邻接节点时必须先跳过父节点，排除正常的反向边干扰。剩下的已访问节点，只能是通过环的其他路径到达的，此时判定为环才是正确的。

修改后运行代码，只会输出正确的环检测结果：

0
1
2
5
3
Cycle detected! | Adjacent node: 1 | Current node: 2
4
6

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