Neural Sync Active

DAGs and Topological Sorting

Registry Synced

DAGs and Topological Sorting

768 words

4 min read

Reading compass

Now · 🎯 Learning Objectives

DAGs and Topological Sorting

🎯 Learning Objectives

By the end of this topic, you will be able to:

Define a Directed Acyclic Graph (DAG)
Perform topological sorting using Kahn's algorithm and DFS
Apply DAGs to model dependencies and scheduling
Detect cycles in directed graphs

📋 Prerequisites

Graph Fundamentals — directed graphs
DFS — graph traversal concepts

📖 Core Content

20.1 What is a DAG?

A Directed Acyclic Graph (DAG) is a directed graph with no cycles. This means you can never start at a vertex, follow directed edges, and return to it. Real-world DAGs:

Course prerequisites (Math 1 → Math 2 → Advanced ML)
Build dependencies (compile A before B which depends on A)
Git version history (commits form a DAG)
Family tree (ancestor → descendant)

💡 Why this matters: DAGs model any system with dependencies and partial order. Understanding DAGs is essential for dependency management, build systems, and scheduling.

20.2 Properties of DAGs

Every DAG has at least one source (vertex with in-degree 0)
Every DAG has at least one sink (vertex with out-degree 0)
A DAG can be topologically sorted (linear ordering respecting edge directions)
A directed graph is a DAG iff it has a topological ordering

20.3 Topological Sorting

A topological sort is a linear ordering of vertices such that for every directed edge

u \to v

u

comes before

v

in the ordering. (Diagram) Topological order:

[\text{Math 1}, \text{Stats 1}, \text{Math 2}, \text{ML Foundation}]

20.4 Kahn's Algorithm (BFS-based)

Algorithm:

Compute in-degree of all vertices
Enqueue all vertices with in-degree 0
While queue not empty:
- Dequeue vertex $v$ , add to result
- For each neighbor $w$ of $v$ : decrement in-degree of $w$
- If in-degree of $w$ becomes 0, enqueue $w$
If result size < number of vertices → graph has a cycle! Time complexity: $O(V + E)$

20.5 DFS-based Topological Sort

Algorithm:

Run DFS on the graph
Add vertex to a stack after all its neighbors are processed (post-order)
Pop from stack to get topological order

20.6 Cycle Detection

If Kahn's algorithm terminates with fewer than

|V|

vertices sorted, the graph has a cycle. Example:

1 \to 2

2 \to 3

3 \to 1

has no vertex with in-degree 0 → cycle detected!

📐 Key Formulas — Summary Table

Concept	Description
DAG	Directed graph with no cycles
Topological sort	Linear ordering $u$ before $v$ for all $u \to v$
Kahn's algorithm	BFS-based, uses in-degree
DFS topological	Post-order DFS traversal
Cycle detection	Kahn's: incomplete sort = cycle
Source	Vertex with in-degree 0
Sink	Vertex with out-degree 0

⚠️ Common Pitfalls

Pitfall 1: Topological Sort ≠ Unique

Multiple valid topological orderings can exist for the same DAG (any ordering respecting the partial order is valid).

Pitfall 2: Only DAGs Have Topological Sorts

A graph with a cycle has NO topological ordering (since a cycle would require

v

before

u

and

u

before

v

Pitfall 3: Confusing Sources and Sinks

Sources have in-degree 0 (no prerequisites). Sinks have out-degree 0 (no dependents).

📝 Practice Questions

Q1: Is a DAG with a single vertex a DAG?

Yes — no cycle possible with one vertex.

$\boxed{\text{Yes}}$ Q2: Find a topological order for $1\to2$ , $1\to3$ , $2\to4$ , $3\to4$ .

$[1, 2, 3, 4]$ or $[1, 3, 2, 4]$

$\boxed{[1,2,3,4] \text{ or } [1,3,2,4]}$ Q3: Does a complete directed graph on 3 vertices contain a cycle?

Yes — it's a directed cycle of length 3.

$\boxed{\text{Yes}}$ Q4: What data structure does Kahn's algorithm use?

Queue.

$\boxed{\text{Queue}}$ Q5: In Kahn's algorithm, if result has fewer than $|V|$ elements, what does it mean?

The graph has a cycle.

$\boxed{\text{Cycle detected}}$ Q6: Give an application of topological sorting.

Course prerequisite ordering, build dependency resolution, task scheduling.

$\boxed{\text{Dependency resolution}}$ Q7: How many sources must a DAG have?

At least one.

$\boxed{\text{At least 1}}$ Q8: Does every DAG have a unique topological ordering?

No — multiple valid orderings typically exist.

$\boxed{\text{No}}$

🔗 Cross-References

Previous: Graph Traversal
Next: Shortest Path Algorithms
Across courses: PDSA (DAG-based scheduling), Build systems (Make, Gradle) Join Discord Previous10.2 Graph Traversal (BFS/DFS)Next11.1 Shortest Path Algorithms