Assume an undirected graph and a DFS traversal on it. I am interested in the DFS tree which encodes the discoverer/discovered (parent/child) relationships of the traversal. Just to make sure we are on the same page, define a discovered vertex x as one that has been visited but descendants of it are still being processed, i.e., we have not yet returned back to x. Define, a processed vertex x as one that we have returned to after we have recursed into all of its descendants and we mark it as such upon return.
Let us define the following edge types on that tree
- Tree edges: direct parent/child edges: the parent is the one to first discover the child.
- Back edges: edge from a descendant to an ancestor at least 2 levels up on the tree: the descendant sees an already discovered vertex.
Those are the only two types of edges one can have on undirected graph DFS. Now, I have been reading The Algorithm Design Manual (page 173) which discusses the following:
- Given an undirected graph DFS and an edge (x,y) as seen from x how can we tell whether we have seen this edge before from the side of y?
I can understand the cases when y is undiscovered or discovered but not yet processed.
However, the book says that if y is processed then we can say that it’s the 2nd time (i.e., we have seen the edge (x,y) from y before); this is because we should have seen all edges coming out of y before marking it as processed. The part I don’t understand is when such a case can occur. How can we see y again after we have marked it processed? Can you give me an example of such a graph?