## 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