A directed graph G = (V,E) is singly connected if there is at most one
directed path from u to v for all vertices u, v in V . Give an efficient algorithm to determine whether or not a directed graph is singly connected.
Solution. For each vertex u in V , perform a DFS on the given graph G. Check if there are any foward edges or cross edges (in the same component) in any one of the searches. If no such edges exist, then the graph is singly connected, else not.
Time complexity: O(|V |(|V | + |E|)).
The graph is singly connected even with back edges existed. Since back edges implies there is a path u to v and v to u, which is consistent with the definition of single connectedness.
directed path from u to v for all vertices u, v in V . Give an efficient algorithm to determine whether or not a directed graph is singly connected.
Solution. For each vertex u in V , perform a DFS on the given graph G. Check if there are any foward edges or cross edges (in the same component) in any one of the searches. If no such edges exist, then the graph is singly connected, else not.
Time complexity: O(|V |(|V | + |E|)).
The graph is singly connected even with back edges existed. Since back edges implies there is a path u to v and v to u, which is consistent with the definition of single connectedness.
cool thanks
ReplyDelete