CODEWITHSUNDEEP
algorithmgraph
user686605
user686605

Reputation:

Directed graph connectivity

Given a directed graph G, what is the best way to go about finding a vertex v such that there is a path from v to every other vertex in G?

This algorithm should run in linear time. Is there an existing algorithm that solves this? If not, I'd appreciate some insight into how this can be solved in linear time (I can only think of solutions that would certainly not take linear time).

Upvotes: 4

Views: 1573

Answers (3)

Dachuan Huang
Dachuan Huang

Reputation: 181

I think I've got a correct answer.

  1. Get the SCC.
  2. Condense each of the components into a single node.
  3. Check whether every pair of adjacent nodes is reachable.

This is a sufficient and necessary condition.

Upvotes: 0

David Nehme
David Nehme

Reputation: 21572

This can be done in linear time in the number of edges.

  1. Find the strongly connected components.
  2. Condense each of the components into a single node.
  3. Do a topological sort on the condensed graph, The node with the highest rank will have a path to each of the other nodes (if the graph is connected at all).

Upvotes: 2

Mike Sokolov
Mike Sokolov

Reputation: 7044

Make a list L of all vertices.

Choose one; call it V. From V, walk the graph, removing points from the list as you go, and keeping a stack of unvisited edges. When you find a loop (some vertex you visit is not on the list), pop one of the edges from the stack and proceed.

If the stack is empty, and L is not empty, then choose a new vertex from L, call it V, and proceed as before.

When L is finally empty, the V you last chose is an answer.

Upvotes: 3

Related Questions