topological sort II
Concept
Topological sort on DAGs
Topological ordering rules out cycles
cycle
contradiction
Homework: DAG must have at least one source and one sink
Kahn’s algorithm
using DFS finish times, decreasing order of finish times
IsDAG(G):
run a full DFS forest to compute finish times
for each edge u -> v:
if finish[u] <= finish[v]:
return false
return true
parentheses property lemma