Finding all the roots in a directed graph

Question

I need to find an algorithm for finding all the roots in a directed graph, in O(n+m).

I have an algorithm for finding a single root:

1. Run DFS(v) on some v in V. If the result is a single spanning tree, then v is a root. Otherwise, the result is a forest of trees. Then:
2. Run DFS(u) on the root of the last tree. If the result is a single spanning tree, then u is a root. Else, there are no roots in the graph.

Now if I want to find all the roots, is the best way to just run the above algorithm O(n) times, on a different vertex in the last tree every time ? Assuming I found a root, if another root exists then it must be on the last tree, then is it O(n+m) if I continue to run the above algorithm until receiving "no root exists" or until going over all vertices ?

Thanks in advance !

Gezira

look up topological sort. Still your question does not make a look of sense. The term root is only defined for a root. I assume you need all vertices with no incoming edge? – Ensure

@IvayloStrandjev ... which are called "source vertices". – Millwater

Assuming you have found a root correctly, you may then find vertices that have a directed path to that root. All such vertices shall be roots themselves. Or you can reverse the direction of all edges and conduct a DFS or BFS from that found root. All the vertices encountered shall be roots themselves. – Herrah

@Gezira As I said, IMO if you reverse the direction of all edges and conduct a DFS or BFS from the root, then you can get all the new roots. – Herrah

Is reversing the direction of all edges O(n) ? – Gezira

Yes, reversing all edges is O(n) where n is the number of edges. – Herrah

@AbhishekBansal We were asked to give an algorithm in O(|V|+|E|), however the first algorithm I described is O(|E|) and your algorithm is O(|E|) which gives me O(2|E|) = O(|E|). What am I missing ? – Gezira

One small edit for my last comment: Look up topological sort. Still your question does not make a look of sense. The term root is only defined for a tree. I assume you need all vertices with no incoming edge? – Ensure

@IvayloStrandjev we were taught that in a graph G, a root is a vertex in which any other vertex is reachable from it. – Gezira

@Gezira if E >> V, then O(V+E) ~ O(E) (our solution), and if V >> E, then O(V+E) > O(E) which means our solution has achieved better complexity. – Herrah

Answer 1

Two approaches:

1. Reverse the graph and calculate DFS-loop() and note the vertices which have no outgoing edges (like Abhishek said).

2. More efficient - Run DFS-loop() on the graph and keep track of vertices with no incoming edges using a true, false table.

Method 1 takes twice as long in the worst case.

Nikko

can you elaborate on the second method? – Herrah

But as per OP's definition, a root can have incoming edges also. In fact if there is a node without any incoming edge, then that node is the single only root of the tree because it cannot be traversed from any other 'possible root node'. – Herrah

there can be more than one root in graph which have no incoming edges – Nikko

if you mean root can have incoming edges than it is part of SCC with no incoming edges . So we use Kasaraju's algorthim for SCC's to reduce the graph to one on which 2.> can work. – Nikko

Answer 2

First you should find all strongly connected components in graph. To build it in leaner time you can use Kosaraju's algorithm or Tarjan's algorithm. All root should be located in one such component. Next you find strongly connected components without incoming edges to it. If you have more then one such component, graph has no root vertices. In you has only one component, you should check that you can reach others component from it, in this case this components contains all root in graph.

Old variant.

You should calculate the number of incoming edges to vertex, this can be done in O(m). All vertices with zero number of incoming edges will be a root of the graph, for this you will need O(n) time.

Blackdamp

I think you are mixing up "root" and "source". Unless I'm mistaken, a root is a node from which each other node can be reached via directed edges. The root might itself have incoming edges, and definitely not each node with no such edges would be a root. – Cointon