I am working on an assignment where one of the problems asks to derive an algorithm to check if a directed graph G=(V,E) is singly connected (there is at most one simple path from u to v for all distinct vertices u,v of V.
Of course you can brute force check it, which is what I'm doing right now, but I want to know if there's a more efficient way. Could anyone point me in the right direction?
Have you tried DFS.
Run DFS for every vertex in the graph as source
If a visited vertex is encountered again, the graph is not singly connected
repeat for every vertex.
The graph is singly connected.
Complexity O(v^2), o(v) dfs as no repetition.
There is a better answer for this question. you can do that in O(|V|^2). and with more effort you can do it in linear time.
First you find strongly connected components of G. in each strong component, you search to find this cases: 1) if there is a forward edge in this component, it is not singly connected, 2) if there is a cross edge in this component, it is not singly connected, 3) if there are two backedges in tree rooted at vertex u, to proper ancestors of u, then it is not singly connected.
this can be done in O(E). ( I think except for case 3. I couldn't implement it well!! ).
If none of cases above occurred, you should check whether there is a cross edge or a forward edge on G^SCC ( graph G, with strong components replaced with single nodes), since we don't have backedges, it can be done by repeating dfs on each vertex of this graph in O(|V|^2).