World's most popular travel blog for travel bloggers.

# [Solved]: How do I find the roots of the disconnected subgraphs of a directed graph?

, ,
Problem Detail:

If I have a directed acyclic graph $G(V,E)$, which may consist of several disconnected subgraphs $G_i(V_i,E_i) \subset G(V,E)$, how do I find the root of every subgraph $G_i(V_i,E_i)$?

#### Answered By : Mario Cervera

You can apply the following algorithm:

1. Identify the weakly connected components (i.e., the disconnected subgraphs). To do this, you can turn all edges into undirected edges and, then, use a graph traversal algorithm.

2. For each component, select the node that has no incoming edges (i.e., the source node) as the root. If there is more than one source node, then there is no root in this component.

Note that this solution assumes the root of a directed acyclic graph $G=(V,E)$ to be a node $r$ such that $\forall v \in V-\{r\} \Rightarrow \exists P=[(r, v_1),(v_1,v_2), ...,(v_{n-1},v)]$, where $P$ represents a directed path from $r$ to $v$.