Why does DFS detect an extra cycle in my graph?

Question

I am trying to learn graph theory and have been playing around with DFS. I want my code to search each node and detect any cycles in the graph.

#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);
}

This is the graph I am trying to search: graph

However, when I run the code from the start node I get this output (the first number is the adjacent node that it sees and the second number is the current parent node):

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

For some reason, it detects one final cycle right before finishing the search. I haven't found any bugs or issues with my code and everyone I ask cannot find the problem. It would be great if someone could figure it out. Thanks for all the help!

"#include " this is likely to cause problems. Just use a vector of bools - it is much safer — ravenspoint, Oct 13 '22 at 14:50
[Why should I not #include ?](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h) - *NEVER* include that header. — Jesper Juhl, Oct 13 '22 at 14:52
"map visited;" This is horribly inefficient. Use a vector of bools. — ravenspoint, Oct 13 '22 at 14:53
[Why is "using namespace std;" considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Jesper Juhl, Oct 13 '22 at 14:53
Firs time cycle was fund using path `0 1 2 3 1` (before first successful path was found `0 1 2 3 4 6`). Second time it found same cycle on path `0 1 3 2 1` (after second successful path found `0 1 3 4 6`). — Marek R, Oct 13 '22 at 15:43

ravenspoint · Answer 1 · 2022-10-13T17:45:24.260

Your code detects the cycle twice.

Things become a lot clearer if you print out the back edge

   if (visited[i] && i != par)
    {
        cout << "Back edge " << cur <<" " << i << "\n";
        cout << "Cycle detected! | ";
        cout << "Adjacent node: " << i << " | ";
        cout << "Parent node: " << par << "\n";
    }

outputs

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

The reason this happens is because you are modelling an undirected graph by storing two directed edges going in opposite directions between every connected pair of vertices. Although this doubles the amount of edge storage reuired, it is a design choice often made because it simplifies code that may be applied to both directed and undirected graphs. The snag is that a DFS will look at ever undirected edge twice.

To fix, prevent the back edges from being detected twice by only checking each edge once - this can be done by looking at the index numbers of the vertices and ignoring the edge when they are in one of the two possible magnitude orders

    // check for back edges just once
    if (i < cur)
    {
        //  if it has been visited and it is not the parent node (detects a cycle)
        if (visited[i] && i != par)
        {
            cout << "Back edge " << cur << " " << i << "\n";
            cout << "Cycle detected! | ";
            cout << "Adjacent node: " << i << " | ";
            cout << "Parent node: " << par << "\n";
        }
    }

Complete code at https://gist.github.com/JamesBremner/e6e3fde8bec0bbc7c22df2ce995c29f5

Note that I have removed the un-needed ( and dangerous ) inclusion of <bits/stdc++.h> and replaced the visited map with a vector of bools for a performance improvement.

i is the index of one of the nodes in the edge being checked for a back edge. It is quite special:-) We want to check this edge just once, so arbitrarily decide to do it when I < cur rather than i > cur. — ravenspoint, Oct 13 '22 at 16:44
I think forward edge is not cycle. (or should not selected as cycle here) — apple apple, Oct 13 '22 at 16:50
Don't know what you mean by forward edge. The graph is undirected. It doesn not matter which of the two possibilities is reported, just so long as only one is reported. — ravenspoint, Oct 13 '22 at 16:55

Why does DFS detect an extra cycle in my graph?

1 Answers1