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.