Construct the transitive closure of the graph. You can use Warshall's algorithm, which is O(v^3) in run time. If any row of the adjacency matrix is all 1's, the corresponding vertex can reach all others. You can ignore the diagonal element if you don't care whether vertices are reachable from themselves (i.e. whether they are contained in a cycle).
On Jul 12, 1:06 pm, Love-143 <[email protected]> wrote: > 1.Give an efficient algorithm which takes as input a directed graph G = > (V,E), and determines whether or not there is a vertex s is in V from which > all other vertices are reachable.? -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
