1
$\begingroup$

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)$?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.