6
$\begingroup$

The question is in the title. What do you call "root nodes" in directed graphs. Is there a commonly accepted term? "Root" implies there's only one, which is not the case. I've scanned half a dozen glossaries before asking. I'm starting to suspect that no, there's no agreed moniker.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ A forest can have multiple roots, admittedly each tree has only one and in a forest every node belongs only to a single tree. $\endgroup$
    – Bergi
    Jan 10 at 4:09
  • 1
    $\begingroup$ @Bergi not all graphs are trees. Directed graphs can have multiple sources, multiple "roots", and still be connected. Trees are a subset of directed acyclic graphs (only one root, and only one path to each node.) $\endgroup$
    – bbsimonbb
    Jan 10 at 8:16
  • $\begingroup$ Yes, I just wanted to add that in forests (a special case of DAGs) there is not only a single root, while "root" is still the commonly accepted term for them. Otherwise see Russel's answer. $\endgroup$
    – Bergi
    Jan 10 at 8:24

1 Answer 1

Reset to default
15
$\begingroup$

I believe the common term for that is source. While a node with 0 out-degree is called a sink.

Improve this answer
$\endgroup$
7
  • 2
    $\begingroup$ Also note this applies to all directed graphs, not just directed acyclic graphs. $\endgroup$
    – Stef
    Jan 10 at 9:18
  • $\begingroup$ There may also be a more specific term that reflects the semantics of the graph in question. For example if the graph represents a finite state machine, the nodes might be referred to as "initial states" and "final states". $\endgroup$
    – Michael Kay
    Jan 10 at 12:18
  • 3
    $\begingroup$ @MichaelKay isn't it possible for an initial state to have in coming edges and final states have outgoing edges? $\endgroup$
    – Russel
    Jan 10 at 12:23
  • $\begingroup$ Not under the usual definitions: en.wikipedia.org/wiki/Finite-state_machine $\endgroup$
    – Michael Kay
    Jan 10 at 12:41
  • 1
    $\begingroup$ @MichaelKay Actually it depends. From wikipedia I don't see any mention that the set $F$ of final states must be such that $\delta(s,x) = s$ or undefined for any $s \in F$ or that the initial state doesn't have incoming edges. In fact with Buchi automata and finite states commonly have outgoing edges since the definition for acceptance in that case involves states that are visited an infinite number of times while recognizing an $\omega$-word. $\endgroup$
    – GACy20
    Jan 10 at 14:59

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.