Given the following depth-first search, why does the check if(Parent[currVertex] != successorVertex) in ProcessEdge method detect a cycle? This code follows the algorithm given in the book Algortim Design Manual by S.Skiena. It is possible that the check is a typo and is meant to be if(Parent[successorVertex] != currVertex). Please ask for any clarification. I'm really stuck at this.
public void Search(int start)
{
/* NOTE: the differences from BFS are: this uses a stack instead of a queue AND this maintains 'time' variable */
Stack<int> s = new Stack<int>();
int currVertex;
int successorVertex;
int time = 0;
s.Push(start);
Discovered[start] = true;
while (s.Count != 0)
{
currVertex = s.Pop();
// time increments every time we enter a node (when discovered) and every time we exit a node (when processed_late, i.e. when all its neighbours have been processed)
time++;
EntryTime[currVertex] = time;
ProcessVertexEarly(currVertex);
Processed[currVertex] = true;
for (int i = 0; i < Graph.Vertices[currVertex].Count; i++)
{
successorVertex = Graph.Vertices[currVertex][i].Y;
if (!Processed[successorVertex] || Graph.IsDirected)
{
ProcessEdge(currVertex, successorVertex);
}
if (!Discovered[successorVertex])
{
s.Push(successorVertex);
Discovered[successorVertex] = true;
Parent[successorVertex] = currVertex;
}
}
// time increments every time we enter a node (when discovered) and every time we exit a node (when processed_late, i.e. when all its neighbours have been processed)
time++;
ExitTime[currVertex] = time;
ProcessVertexLate(currVertex);
}
}
private void ProcessEdge(int currVertex, int successorVertex)
{
if(Parent[currVertex] != successorVertex) // then we've found a cycle
{
/* Found cycle*/
}
}
UPDATE
Found correction for this code in errata http://www.cs.sunysb.edu/~skiena/algorist/book/errata. See (*) Page 173, process_edge procedure -- the correct test should be
if (discovered[y] && (parent[x] != y)) { /* found back edge */
But will that detect cycles?? The if check will never pass because in DFS method, process_edge is only called when discovered[y] == false.
dfscallsprocess_edgeifyis not discovered or not processed. Vertices are not marked processed until every edge leaving them are explored.