1
\$\begingroup\$

I'm attempting the Graph Algorithms section in CLRS right now. Here's an iterative DFS using a stack called nodes.

T is a vector of pair(s) of ints which store timestamps for each node.

T[node].first = discovery time

T[node].second = finishing time

P is a vector recording Parents for each node in the DFS-Tree.

N is number of nodes in a given Directed Graph, which is represented using the Adjacency List representation as G. So G[node] represents the Adjacency List (as a vector of ints) for node in G.

cycleFound is a boolean for detecting a cycle in G.

void stackDFS(vector<vector<int>>& G, vector<pair<int, int>>& T,
    vector<int>& P, int N, bool* cycleFound)
{
    stack<int> nodes;
    int Time = 0;

    int u, v;
    for (u = 1; u <= N; u++)
    {
        if (T[u].first == 0)
        {
            nodes.push(u);

            while (!nodes.empty())
            {
                v = nodes.top();
                nodes.pop();

                if (T[v].first == 0)
                {
                    T[v].first = ++Time;

                    // we push it back before expanding it's children
                    // so it can be popped again and it's
                    // finishing time can be added in "else if".
                    // if it's popped from stack and it's already been
                    // discovered, then by OUR stack's logic, it's children
                    // have already been expanded, so it's fin-time can
                    // now be added.
                    nodes.push(v);

                    for (auto w = G[v].begin(); w != G[v].end(); w++)
                    {
                        if (T[*w].first == 0)
                        {
                            // cout << "Tree Edge encountered...(" << v << ", " << *w << ")" << endl;

                            P[*w] = v;
                            nodes.push(*w);
                        }

                        // this is different from the else-if condition below
                        // here, edges are being examined, and if a back-edge
                        // is found, we say there's a cycle.

                        // Back-Edge: v.d < u.d < u.f < v.f
                        //            for an edge u --> v
                        else if (T[*w].second == 0)
                        {
                            // cout << "Back Edge encountered...(" << v << ", " << *w << ")" << endl;  
                            *cycleFound = true;
                        }
                    }
                }

                // don't wanna re-update finish-times again and again
                // cuz that would be wrong computations.
                // A node can be pushed multiple times on stack if 
                // current DFS-path has edges to it from multiple nodes
                // and our node is still marked undiscovered.
                // Eg- node s in graph from CLRS pg 611, fig22.6, ex22.3-2
                // Thus, only update fin-time once, when node finishes
                // for the first time.
                else if (T[v].second == 0)
                    T[v].second = ++Time;
            }
        }
    }
}

I tested this on two different digraphs, one cyclic and the other acyclic.

Input 1: 1->2->3->4->5->6; acyclic

Input 2: graph from CLRS pg 611, fig22.6; has three cyclic

It correctly detects cycles and the timestamps computed make sense. So I think this implementation is correct, but I'm not sure. I wrote some comments in the code to explain my logic, but it's mostly intuition. Is this a correct implementation of DFS? Will it always compute timestamps correctly?

Also, how could I classify edges in this code? I'm having trouble classifying Forward and Cross Edges. In recursive DFS it's simpler cuz of the nested recursive structure:

void DFSVisit(vector<vector<int>>& G, vector<pair<int, int>>& T, 
    vector<int>& P, int curNode, int* Time, bool* cycleFound)
{
    (*Time)++;
    T[curNode].first = *Time;

    for (auto i = G[curNode].begin(); i != G[curNode].end(); i++)
    {
        if (T[*i].first == 0)
        {
            cout << "Tree Edge encountered...(" << curNode << ", " << *i << ")" << endl; 
            P[*i] = curNode;
            DFSVisit(G, T, P, *i, Time, cycleFound);
        }

        // cycle is present if node (*i) if encountered from curNode
        // such that (*i) hasn't yet finished, meaning (*i) has been
        // encountered again in the current DFS traversal, thus
        // edge (curNode, *i) is a back edge which completes the cycle
        else if (T[*i].second == 0)
        {
            cout << "Back Edge encountered...(" << curNode << ", " << *i << ")" << endl;  
            *cycleFound = true;
        }
        else
        {
            // only specifying condition for discovery times
            // is enough here because T&B edges have already
            // classified above, and for C-edges, *i needs to
            // be discovered first.
            if (T[curNode].first < T[*i].first)
                cout << "Forward Edge encountered...(" << curNode << ", " << *i << ")" << endl;
            else
                cout << "Cross Edge encountered...(" << curNode << ", " << *i << ")" << endl; 
        }
    }

    (*Time)++;
    T[curNode].second = *Time;
}

If I try these same conditions in the Iterative DFS, it doesn't work because there's no recursive structure, in other words, all outgoing edges from current node are classified as Tree Edges, since all outgoing edges are examined together in the for-loop in Iterative-DFS, even though some of them might be forward edges.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.