Detecting cycle in an undirected graph using iterative DFS?

Question

So, I implemented the DFS in an iterative manner by the following method:

void dfsiter (graph * mygraph, int foo, bool arr[])
{
    stack <int> mystack;
    mystack.push(foo);
    while (mystack.empty() == false)
    {
        int k = mystack.top();
        mystack.pop();
        if (arr[k] == false)
        {
            cout<<k<<"\t";
            arr[k] = true;
            auto it = mygraph->edges[k].begin();
            while (it != mygraph->edges[k].end())
            {
                if (arr[*it] == false)
                {
                    mystack.push(*it);
                }
                it++;
            }

        }
    }
}

The above code works completely fine. Now, I want to detect cycles in an undirected graph using the above code (Iterative DFS). Now, I read that, If an unexplored edge leads to a node visited before, then the graph contains a cycle. Therefore, I just want to ask you, how do I exactly keep track of all this?

I have taken my graph to be like this:

class graph
{
    public:
    int vertices;
    vector < vector<int> > edges;
};

Should I change the above to:

class graph
{
    public:
    int vertices;
    vector < vector<pair<int,bool> > edges;
};

Where the bool for each edge will be marked true? And what changes will I need to do in the above code for DFS for detecting the cycle? I tried but I couldn't really think of a way of doing it. Thanks!

Answer 1

You can store a "father" node f in DFS tree for each vertex v, i.e. the vertex from which DFS came to the vertex v. It can be stored in the stack for example. In this case you store pairs in stack, first value is the vertex v and the second one is its father f.

An undirected graph has a cycle if and only if you meet an edge vw going to already visited vertex w, which is not the father of v.

You can see the modified and cleaned code below.

bool hascycle (graph * mygraph, int start, bool visited[])
{
    stack <pair<int, int> > mystack;
    mystack.push(make_pair(start, -1));
    visited[start] = true;

    while (!mystack.empty())
    {
        int v = mystack.top().first;
        int f = mystack.top().second;
        mystack.pop();

        const auto &edges = mygraph->edges[v];
        for (auto it = edges.begin(); it != edges.end(); it++)
        {
            int w = *it;
            if (!visited[w])
            {
                mystack.push(make_pair(w, v));
                visited[w] = true;
            }
            else if (w != f)
                return true;
        }
    }
    return false;
}

Note: if the graph is disconnected, then you must start DFS from several vertices, ensuring that the whole graph is visited. It can be done in O(V + E) total time.