Directed Acyclic Graphs

Def Directed graph with no cycles are called directed acyclic graphs.

Lemma 1: every DAG has at least one source (proof by contradiction)

Lemma 2: If v is a souce vertex of G, then G is a DAG if and only if G-v is a DAG

Find topological ordering

While G has at least one vertex
If G has some source,
Choose one source and output it
Delete the source and all its outgoing edges from G
Else
Return that G is not a DAG