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)$?
1
$\begingroup$
$\endgroup$
-
2$\begingroup$ Acyclic graphs have sources and sinks, but root? What is this? $\endgroup$ – HEKTO Sep 9 '16 at 15:21
-
$\begingroup$ @HEKTO: as I understand it, a root node in a directed graph allows you to reach all of the other nodes in the graph. Source nodes do not have this property. $\endgroup$ – Mario Cervera Sep 9 '16 at 18:48
1
$\begingroup$
$\endgroup$
You can apply the following algorithm:
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.
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$.
answered Sep 9 '16 at 18:08
1
$\begingroup$
$\endgroup$
It should be:
$V - \{ b\ | \exists a. (a,b) \in E \}$
This is, all the vertices exept those which are the destination of some directed edge
