topological sort II

Work in Progress

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