# The Problem

I have a set of edges (a, b), where a and 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 edges. 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.

• Have you tried thinking of an algorithm using BFS or DFS? – D.W. May 3 '20 at 15:37

Here is a quite non-optimal algorithm, to get you started.

Go over all edges $$(a,b)$$. For each edge, go again over all edges, and check how many times $$a$$ appears. Stop once you discover $$a$$ that appears only once (if this never happens, reject). We will take $$n_1 = a$$.

Go over all edges again, looking for the unique edge $$(n_1,b)$$ in which $$n_1$$ appears. Take $$n_2 = b$$.

Go over all edges again, looking for an edge $$(n_2,c)$$ in which $$n_2$$ appears on the left (if there is no such edge, reject). Take $$n_3 = c$$.

Continue in this way, finding $$n_4,\ldots,n_n$$.

This algorithm runs in $$O(n^2)$$. Using hashing, you should be able to improve it to $$O(n)$$.

• Are you sure this works? If there are any two edges (a, b) and (c, d) where a = c, then the graph is not linear. Every node should exist exactly once as a the source of an edge and once as a destination. Otherwise it should fail. – Dracam May 3 '20 at 15:46
• You also need to check that the different $n_i$ that you find are distinct. – Yuval Filmus May 3 '20 at 15:47

I figured out an algorithm that at least passes my test cases:

let N = set of all nodes
let E = set of all edges

if (|E| != |N|-1) fail

let possibleStartNodes = new set containing all of N
let nexts = new dictionary from node -> node

foreach (prev, next) in E:
if (next not in possibleStartNodes) fail
remove next from possibleStartNodes
nexts[prev] = next
end foreach

if (|possibleStartNodes| != 1) fail

let currentNode = the one node in possibleStartNodes
let ordering = new list
ordering.push(currentNode)

while (nexts contains value for currentNode)
ordering.push(next)
currentNode = next
end while

return ordering


$$O(n)$$ looks pretty reasonable to me. Are there any ways to improve?

Edit: I would appreciate any hints about the correct technical terms for the concepts I'm using