World's most popular travel blog for travel bloggers.

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

, , No Comments
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)$?

Asked By : Chicony

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.

enter image description here

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$.

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback