DFS in an undirected graph - can it have cross edges?

4
votes

Is it possible in an undirected graph for an edge that is leasing to an already visited node to lead towards a vertice that is not an ascendant of the current node?

To be more clear, I want to implement a depth-first search on an undirected graph. If I come across an edge that connects my current vertice with an already-visited one, am I guaranteed to have a path from one to another by iterating through the parent array?

The most natural answer seems to be affirmative. I have yet to find a counter-example. What do you think?

In DFS terminology:
Can an edge be a cross-edge in DFS - an edge that leads to an already discovered node, which is not an ancestor of the origin, in an undirected graph?

1
algorithmgraphdepth-first-search
Update: I am only taking into consideration the edges which connect a node with a greater depth with one with a smaller one. – lbicsi
I took the liberty to add a formal DFS terminology to your question, feel free to roll back if you find it unsatisfying – amit
by parent you mean immediate parent or ancestor ? – sashas

1 Answers

5
votes

An edge discovered by DFS cannot be a cross edge, if its destination is an already discovered node, it must be a back-edge - so it is leading to an ancestor (in the DFS tree) of the source node.

Proof:

Assume it was not the case, and while in some node vyou encounter an already discovered node (u) that is not one of your 'parents' (in the DFS tree).
Since you discovered the node, there is an edge (v,u).
But the graph is undirected, so the edge is symetrical.

Since u was already discovered, you have these options:

  1. u was discovered and not "closed" yet, in this case, you are basically traversing a subtree which has u as a root, and u is indeed a parent of v.
  2. u was discovered and closed already. But that's impossible considering you just discovered v, and there is an edge (u,v).

Thus an edge that leads to an already discovered edge in an undirected graph, must be a back edge, and cannot be a cross-edge.