First-time and second-time seen edges in DFS on undirected graphs

Question

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?

John L. · Answer

Here is the simplest example.
Let the graph contain two vertices, $x$ and $y$ with one edge ${x,y}$. Here is a run of the algorithm.

$x$ and $y$ are marked as "undiscovered".
$y$ is marked as "discovered" and enqueued.
$y$ is dequeued.

Since $x$ is adjacent to $y$ and $x$ is "undiscovered", $x$ is marked as "discovered" and enqueued.
All vertices adjacent to $y$ have been "discovered", so $y$ is marked as
"processed".

$x$ is dequeued.

$y$ is adjacent to $x$ but $y$ is not "undiscovered", do nothing.
All vertices adjacent to $x$ have been "discovered", so $x$ is marked as "processed".

The queue is empty. Done.

You can note that, at step 4.1 when $y$ has been marked as "processed", we are seeing y again by the same edge ${x, y}$.

Here is an exercise that characterizes such occasions.
Exercise. Suppose we are given a BFS or DFS of a connected undirected graph with more than one vertices.  Let $y$ be a vertex. Show the following two propositions are equivalent.

There is a time that $y$ was seen again when $y$ had been marked as "processed".
$y$ is not a leaf of the search tree.

First-time and second-time seen edges in DFS on undirected graphs

One Answer

Add your own answers!

Ask a Question