Let G = (V, E) be a graph which is hierarchical in the sense that its vertices are arranged in levels/layers (say 1 to k) and an edge can only be from a vertex at level i to a vertex at level i+1. Vertices at level 1 and k are called the roots and the leaves, respectively. The problem is to find all descendant leaves of each root.For instance, for the following graph,the answer would be:1: 12, 132: 12, 133: 12, 13, 14, 15, 164: 14, 15, 16A naive solution can be to run a DFS for each root which will take O(r(n+m)) time where r is #roots, n is #vertices and m is #edges.Can we do better?Another way to see the same graph is that it is a bipartite DAG.
Efficiently listing all last-level descendants of each root in a proper hierarchical graph (bipartite DAG)
algorithms;graphs;algorithm analysis;graph traversal