Simply connected directed graphs
According to the definition available in the third edition of the CLRS, a simply connected directed graph is one where for each pair of vertices (u, v) there is at most 1 unique path from u-> v. Now, most of the answers I have read indicate that we are running DFS from every vertex in the graph, and if we find a Cross edge or Forward edge anyway , then the graph is not simply connected. I understand the concept of front ribs, but running this algorithm on this graph
1 → 2 <3 will give us the result that it is NOT simply connected, whereas this graph is simply connected. We have a cross edge from 3 → 2 or 1 → 2, depending on which vertex started this whole procedure (1 or 3). If we run DFS from vertex 2, then we have 2 transverse edges 1 → 2 and 3 → 2. Can anyone please clarify?
source to share
The answer, which assumes starting DFS from each node, means that you should stop DFS as soon as you cannot continue (no outgoing edges on the left), and not start from another node.
In this case, in your example, you will start (wlo) at 1, open 2 and you are done. No trailing edges
Further, this is a brand new DFS starting at 3, opening 2 and ending, with no trailing edges.
The idea is basically checking the attribute by definition. You do DFS from each node u
until you find that v
there is at most one path from u
to for each v
(DFS is exhausted) or you find at some point a 2nd path from u
to v
and then you are done.
source to share