I have a set of
(a, b), where
b are nodes in a directed, acyclic graph (DAG).
The number of edges is guaranteed to be the number of nodes - 1.
I am looking for an algorithm that finds a sequence of nodes
[n_1, ... n_n] so that the sequence contains all nodes in the graph, and that all edges
(n_i, n_i+1) for
0 < i < n exist in
If that sequence is not possible because the given set of
edges is not equal to the set of edges required, then I need an error to be thrown.
Edit: the graph may have an arbitrary number of disconnected components. I obviously don't consider a graph with multiple disconnected components as linear.
Ideas so far
Note that I am checking that the number of
edges is exactly the number of edges required for such a sequence to exist. As a result, the algorithm can fail when there are two edges that share a source or a destination. However, I still need to get that sequence.
I realize that topological sort returns a linear order of a directed graph, which satisfies my requirements. However, I still want to fail when the graph is not exactly linear like that, instead of getting a linear order anyways.
Maybe I can validate, then do a topological sort. But that sounds inefficient. I am also not sure about the formal names of things in this problem, so it's hard to simply look up an algorithm. I feel like I am missing some simple connection or trick here.
Could you provide me with an algorithm that accomplishes this? I'll take pseudocode or any language of your choice.