intro video

Find an order of vertices in a Directed acyclic graph such that preserves the ordering, when the edges in the graph are interpreted as a Partial ordering.

An example of application is to find a way of taking a set of subjects which have dependencies between them (represented as directed edges), which require you to take some subjects before another. Another uses

Algorithm:

1. Find all nodes that have In-degree $0$
2. Delete one of these nodes, and go back to step 1.

Basically, the graph is a graph of "unmet dependencies", and so every time we meet a dependency we remove it from the graph

For it to have a solution the graph must be a DAG, which can be more or less interpreted as it needing to satisfy the axioms of a Partial ordering (though not literally)

How to implement in Adjacency list data structure. More efficient implementation

An alternative

Another algorithm is to Depth-first search on the DAG with reversed edges (i.e. so that we want to do first things which are "below"), and follow the rule: {add a node to the list exactly after the DFS has visited all of its children}

This algorithm works because of the following. Assume that {we add a node to the list exactly after we have visited all of its children}. Now, if for node n, its children c has already been visited, then either:

• n is a descendent of c, in which case, there would be a cycle.
• n is not a descendent of c. In DFS, after a node is visited, we always visit all of its descendants, before any other node. So in this case n must have been visited after all the descendents of c, and therefore after c has already been added to the list This works whether the graph is a simple tree or DAG. This property of DFS still holds. No matter how we encountered, if we encounter a visited children in a DAG, we know it must have been added already.

Therefore if all children of n have been visited, then all of its children have been added.

Therefore adding every node exactly after all its children have been visited implies that every node is added after all of its children have been added.