logic for method to detect cycle in an undirected graph

Question

I was trying to detect a cycle in a directed graph.
While coming up with the logic to solve it, I figured out that a simple graph traversal eq. dfs is sufficient because while doing dfs we can just have a condition to see if any node is already visited. If so, there must be a cycle.

While, looking up the solution to cross check my logic I came across this solution which says that while doing dfs along with keeping track of the visited nodes you also need to keep track of the nodes in the recursion stack and is a node is already in the recursion stack then there is a cycle- which I do not understand.
Why do we need to keep track of the nodes in the recursion stack when we can simply just check if a node is visited again and conclude there is a cycle?

Answer 1

For an undirected graph, detecting a cycle is easy using DFS. Back-edge is nothing but the edge between current node and it's ancestor which is not it's direct parent. So, for a cycle in a graph, a node that is part of the cycle must connected to it's ancestor. This way the problem reduces to finding back-edge in the graph. While applying DFS on undirected graph, we need to keep track of the parent of current node. There is no parent of starting node, so we pass it's parent = -1 in DFS. We call DFS again on child with it's parent as current node. Now we check if the visited child of current node is it's parent or not. If the visited child is it's parent then no problem as it is not it's ancestor and we move to it's next child. But if the visited child is not it's parent then this visited child has to be it's ancestor and hence we got a back-edge. Once we found back-edge we stop further DFS and return informing 'a cycle is present'. If we don't find a back-edge even if all nodes are visited, then cycle is not present in the graph.

bool dfs(int node,int parent,vector<vector<int>>&graph,vector<bool>&visited){
        visited[node]=true;
        for(int child: graph[node]){
                if(visited[child]==true){
                        if(child!=parent){ //backedge
                                return true;
                        }
                }
                else
                        return dfs(child,node,graph,visited);

        }
        return false;
}