Topological Sort

• A topological ordering of a graph is an ordering of all the vertecies in a graph such that if node A -> B, then A will come before B in the ordering.

• We can think of the edges as B depends on A. So in order to get to node B, we must get through node A.

• If a graph is a DAG, it has topological ordering, and if a graph has topological ordering, it is also a DAG.

Constraints

• A graph must be a DAG (directed acyclic graph) for topological sorting to be possible.

  • Why:

    • If non-directed, then A <--> B for all nodes, so there is no ordering possible.

    • Acyclic because if a cycle does exist, then then that means there exist at least one cycle in the graph where all the nodes depend on each other (which do we chose first?).

Algorithm

1. Select node S that has no incoming edges, and push into some set.

2. Remove node S from graph (and its connections)

3. See 1.

5
a->b
a->c
a->d
a->e
b->d
c->d
c->e
d->e