Intuition The one core ideaA directed graph is a set of dots joined by one-way arrows. Topological sort lines those dots up on a straight track so that every arrow points forward — which is only possible when the arrows never loop back on themselves.
Before you can trust the parent note, you must own every piece of vocabulary it throws at you. This page builds each one from a picture, in the order they depend on each other. Nothing here assumes you have seen a graph before.
A vertex (plural vertices ) is just a labelled dot. It stands for one "thing" — a task, a course, a step. We usually name them with letters or numbers: u v 0 5
The letters u v x
Why we need it: everything else (edges, orderings) is built on top of vertices. No dots, nothing to connect or sort.
A directed edge written u → v u v u v u v
The arrowhead matters. u → v not the same as v → u u v
Intuition Why the direction is the whole pointTopological sort's entire job is to respect these arrows. If we ignored direction, there would be nothing to sort — we could put dots in any order. The arrow u → v rule : u v
The symbol E G = ( V , E ) the collection of all these arrows . The symbol V the collection of all the dots .
Definition Directed graphA directed graph G ( V , E ) V E G = ( V , E ) G V E
V V = { 0 , 1 , 2 , 3 , 4 , 5 } E E = { 5 → 0 , 5 → 2 , 4 → 0 , … }
Why we need it: the parent note says algorithms run in O ( V + E ) < ∣ V ∣ V E ∣ V ∣
The indegree of a vertex v indeg ( v ) into v v
Count only the arrowheads landing on v
Intuition Why Kahn's algorithm lives and dies on this numberA vertex with indeg ( v ) = 0 no unfinished prerequisites — it is ready to go right now. That is exactly the vertex Kahn's algorithm emits next. As you remove a vertex, every arrow it sent out disappears, so its neighbours' indegrees drop by one. When a neighbour's count hits zero, it becomes ready. That cascade is the whole algorithm.
Why we need it: the parent's indegree table (0:2, 1:2, 2:1, ...) is meaningless without this definition.
A cycle is a path of arrows that leads back to where it started, e.g. a → b → c → a
Intuition Why a cycle kills topological sortA cycle demands: a b b c c a a a no valid line-up can exist. This is why the parent keeps checking for cycles.
Zero / degenerate cases you must know:
A self-loop a → a
A graph with no edges at all: every ordering is valid (nothing constrains anything).
A single vertex, no edges : trivially sorted (the order is just that one vertex).
A DAG is a directed graph with no cycles . "Acyclic" = "without cycles". This is the exact class of graphs for which a topological order exists.
See Directed Acyclic Graph (DAG) for the deep dive. Why we need it: it is the precondition for the whole parent topic.
Definition Vertex colours during DFSWhile DFS explores, each vertex has a colour:
White = not visited yet.Gray = visited, still being explored (currently on the recursion stack — we went in but haven't come out).Black = fully finished (we explored everything reachable and popped it off).
Intuition Why gray is the cycle detectorIf DFS is standing at u u → v v gray , that means v v ⇝ u u → v
Why we need it: the DFS pseudocode says "if v u
f ( u ) moment DFS finishes vertex u u f ( u )
Why we need it: the entire correctness of the DFS-based algorithm rests on this one inequality.
O ( V + E ) O ( ⋯ ) how the running time grows as the graph grows. O ( V + E )
Why we need it: the parent claims both algorithms are O ( V + E )
Edge u to v - one-way arrow
Indegree - arrows into a vertex
Cycle - arrows that loop back
DAG - graph with no cycles
Kahn algorithm - remove indegree zero
Visited colours white gray black
DFS-based topological sort
Read top to bottom: dots and arrows come first, everything about ordering comes last.
Cover the right side and test yourself. You are ready for the parent note when every line is instant.
What does u → v "u v u v
What is indeg ( v ) The number of arrows pointing into v
What does ∣ V ∣ The count of vertices — how many dots the graph has.
What is a cycle, and why does it block sorting? A loop of arrows returning to start; it forces a vertex before itself, which is impossible.
What does DAG stand for? Directed Acyclic Graph — a directed graph with no cycles.
When does a topological order exist? If and only if the graph is a DAG.
What do white, gray, and black mean in DFS? Unvisited, on the stack (in progress), fully finished.
What does a gray neighbour signal during DFS? A back edge → a cycle.
State the finish-time law for an edge u → v f ( u ) > f ( v ) u v
What does O ( V + E ) Running time grows linearly with the number of vertices plus edges.
Parent topic — this page feeds directly into it.Directed Acyclic Graph (DAG) — the graph class defined in section 6.Cycle Detection in Directed Graphs — built on the cycle idea (section 5) and gray edges (section 7).Depth-First Search (DFS) — where finish times and colours come from.Breadth-First Search (BFS) — the traversal Kahn's indegree method mimics. 
