Find all connected nodes in adjacency list

Question

I have an adjacency list for a DAG, and I need to find all connected nodes from all nodes, for example : for a DAG below

1 -> 3 -> 4  
2 -> 4  
3 -> 2    
4 -> 5  
5 -> NULL  

I need this :

1 -> {2, 3, 4, 5}
2 -> {4, 5}
3 -> {2, 4, 5}
4 -> {5}
5 -> NULL  

Is there any efficient algorithm for this ?

Answer 1

As you mentioned a DAG you can use following algorithm to get all connected components to given vertex :-

1. Do a Topological Sort of the all nodes in graph
2. Start in decreasing order of the sorted nodes.
3. Maintain a Set of all connected nodes for each node.
4. Sort adjacency list of vertex u in toposort order
5. For vertex u and each edge(u,v) and !Set(u).contains(v) do Set(u) = Set(u) union Set(v) union v
6. Do this for all node in decreasing order of toposort.

Time Complexity :-

Toposort : O(E)

Caculating Set : O(V^2*logV)

Total: O(V^2*logV)

Example:-

1 -> 3 -> 4  
2 -> 4  
3 -> 2    
4 -> 5  
5 -> NULL  

TopoSort: 1,3,2,4,5

Visiting in descending order :-
1. Set(5) = {null}
2. Set(4) = Set(5) + 5 = {5}
3. Set(2) = Set(4) + 4 = {4,5}
4. Set(3) = Set(2) + 2 = {2,4,5}
5. Set(1) = Set(3) + 1 = {1,2,4,5}