can it have cross edges?

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?

---

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 v you 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:

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 .

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.

链接地址: http://www.djcxy.com/p/52382.html

上一篇: C ++高效地在邻接列表中存储大图？

下一篇: 它可以交叉边缘吗？