From Sources to an Ordering
A topological order lists the vertices of a directed graph so that every arc points forward in the list. The characterization of directed acyclic graphs (DAGs) gives an existence result; source removal turns that result into a concrete algorithm. Repeatedly choose a vertex with no incoming arc from the vertices still present, append it to the output, and remove it. The key implementation detail is to update the in-degrees of its out-neighbors as arcs are removed.
Throughout, a digraph is finite, with vertex set \(V\) and arc set \(A\); an arc from \(u\) to \(v\) is written \(u\to v\). We use adjacency lists: for each vertex \(u\), its list contains the vertices \(v\) for which \(u\to v\) is an arc. The in-degree of \(v\) is the number of arcs entering \(v\). A source has in-degree zero. A directed cycle is a closed directed path of positive length with no repeated vertices except its first and last. A DAG is a digraph with no directed cycle. A topological order is a listing of all vertices in which \(u\) occurs before \(v\) whenever \(u\to v\).
The stored in-degree is the number of arcs entering a vertex from vertices that are still present. When a vertex is removed, each of its outgoing arcs is removed too, so the stored in-degree of its head decreases by one. If that value becomes zero, the head is now a source and is added to the queue. Initially, compute all in-degrees by scanning the adjacency lists, then enqueue every vertex whose in-degree is zero.
The Queue Algorithm
Set the stored in-degree of each vertex equal to its in-degree in the input digraph. Enqueue every vertex with stored in-degree zero. Set the output list to empty.
While the queue is nonempty, remove its front vertex \(v\) and append \(v\) to the output list.
For each arc \(v\to w\), decrease the stored in-degree of \(w\) by one. If it becomes zero, enqueue \(w\).
If every vertex was appended, return the list as a topological order. If the queue becomes empty while vertices remain, report that the digraph is not a DAG.
The queue invariant is important: the queue contains precisely the remaining vertices whose stored in-degree is zero and that have not yet been removed; each such vertex appears in the queue only once. The queue holds its members, not vertices excluded for already being queued. Every initially zero in-degree vertex is enqueued once. Afterwards, a remaining vertex is enqueued precisely when its stored in-degree changes from one to zero. Since stored in-degrees only decrease, that transition can happen at most once. Removing a vertex removes it from the queue and from the remaining set; it cannot be enqueued again.
Worked Example: Ordering a DAG
Let \(D=(V,A)\), where \(V=\{a,b,c,d,e,f\}\) and \(A=\{a\to c,\ b\to c,\ b\to d,\ c\to e,\ d\to e\}\). Vertex \(f\) is isolated. The initial in-degrees are \(d^-(a)=0,\ d^-(b)=0,\ d^-(c)=2,\ d^-(d)=1,\ d^-(e)=2,\ d^-(f)=0\), so the initial queue is \([a,b,f]\). In the table, changes are listed in the order the outgoing arcs are scanned.
| Removed vertex | In-degree updates | Queue after the updates | Output so far |
|---|---|---|---|
| — | Initial values: \(0,0,2,1,2,0\) | \([a,b,f]\) | \([]\) |
| \(a\) | \(d^-(c):2\to1\) | \([b,f]\) | \([a]\) |
| \(b\) | \(d^-(c):1\to0\), enqueue \(c\); \(d^-(d):1\to0\), enqueue \(d\) | \([f,c,d]\) | \([a,b]\) |
| \(f\) | No outgoing arcs | \([c,d]\) | \([a,b,f]\) |
| \(c\) | \(d^-(e):2\to1\) | \([d]\) | \([a,b,f,c]\) |
| \(d\) | \(d^-(e):1\to0\), enqueue \(e\) | \([e]\) | \([a,b,f,c,d]\) |
| \(e\) | No outgoing arcs | \([]\) | \([a,b,f,c,d,e]\) |
The algorithm returns \(a,b,f,c,d,e\). Checking each arc: \(a\to c\) has positions \(1<4\), \(b\to c\) has \(2<4\), \(b\to d\) has \(2<5\), \(c\to e\) has \(4<6\), and \(d\to e\) has \(5<6\). Thus every arc points forward, as required.
Check: the initial in-degree sum is \(0+0+2+1+2+0=5\), equal to the five arcs listed in \(A\). The updates account for those arcs once each: one from \(a\), two from \(b\), one from \(c\), and one from \(d\); \(f\) and \(e\) have no outgoing arcs.
Why the Algorithm Works
Proof. Suppose instead that a nonempty finite DAG has no source. Then every vertex has an incoming arc. Choose a vertex \(v_0\), and repeatedly choose a predecessor: for each \(i\geq 0\), choose \(v_{i+1}\) with \(v_{i+1}\to v_i\). Because there are finitely many vertices, this sequence eventually repeats a vertex. Choose the first repeated vertex, say \(v_j=v_i\) with \(i<j\). The vertices \(v_i,v_{i+1},\ldots,v_{j-1}\) are distinct by the choice of the first repetition. The arcs \(v_{k+1}\to v_k\) for \(i\leq k<j\), including \(v_j\to v_{j-1}\) with \(v_j=v_i\), form a directed cycle. This contradicts that the digraph is a DAG. Therefore every nonempty finite DAG has a source. \(\square\)
Proof. First suppose the algorithm removes every vertex, and call the output \(v_1,\ldots,v_n\). When \(v_i\) is removed, it is a source among the vertices still present. If there were an arc \(v_j\to v_i\) with \(j>i\), then \(v_j\) would still be present at the time \(v_i\) was removed. That arc would give \(v_i\) a positive stored in-degree, contradicting its selection as a source. Therefore every arc \(v_i\to v_j\) satisfies \(i<j\), and the output is a topological order.
Now suppose the input is a DAG. At any stage, the digraph induced by the remaining vertices is also a DAG: a directed cycle among those vertices would already have been a directed cycle in the input. If any vertices remain, the lemma gives a source in this remaining digraph. By the queue invariant, that source is in the queue. Therefore the queue cannot become empty while vertices remain, and the algorithm eventually removes them all. By the first part, its output is a topological order.
Finally, if the algorithm removes every vertex, the first part gives a topological order. A digraph with a topological order cannot contain a directed cycle: along every arc of a directed cycle the position must strictly increase, including the final arc back to its starting vertex, which would require that position to be strictly greater than itself. Hence the input is a DAG. This proves the claimed equivalence. \(\square\)
Worked Example: The Queue Exhausts Before All Vertices Are Removed
Let \(D=(V,A)\), where \(V=\{1,2,3,4,5\}\) and \(A=\{1\to2,\ 2\to3,\ 3\to2,\ 3\to4\}\). The initial in-degrees are \(d^-(1)=0,\ d^-(2)=2,\ d^-(3)=1,\ d^-(4)=1,\ d^-(5)=0\). Thus the initial queue is \([1,5]\).
| Removed vertex | In-degree updates | Queue after the updates | Remaining vertices |
|---|---|---|---|
| — | Initial values: \(0,2,1,1,0\) | \([1,5]\) | \(\{1,2,3,4,5\}\) |
| \(1\) | \(d^-(2):2\to1\) | \([5]\) | \(\{2,3,4,5\}\) |
| \(5\) | No outgoing arcs | \([]\) | \(\{2,3,4\}\) |
The queue is empty but three vertices remain, so no topological order is returned. The remaining arcs include \(2\to3\) and \(3\to2\), a directed cycle. The in-degree calculations on the remaining vertices confirm why no source is available: vertex \(2\) has the incoming arc \(3\to2\), vertex \(3\) has \(2\to3\), and vertex \(4\) has \(3\to4\).
Check: the initial in-degree sum is \(0+2+1+1+0=4\), equal to the four arcs. Removing \(1\) deletes the single arc \(1\to2\), changing the sum of remaining in-degrees from \(4\) to \(3\); removing \(5\) deletes no arcs, so the sum stays \(3\). The three remaining arcs are exactly \(2\to3,\ 3\to2,\ 3\to4\).
Running Time with Adjacency Lists
Let \(n=|V|\) and \(m=|A|\). Initializing all stored in-degrees takes \(O(n)\) time to set the counters to zero and \(O(m)\) time to scan the adjacency lists and add one to the head of each arc. The initial scan also identifies which vertices have zero in-degree, using \(O(n)\) additional checks. Each vertex is enqueued at most once and removed from the queue at most once, so all queue operations together take \(O(n)\) time.
When a vertex is removed, the algorithm scans its outgoing adjacency list. Each arc occurs in the list of its tail, and each tail is removed at most once. Hence each arc is scanned at most once in this stage; its head's stored in-degree is decreased once for that arc. The total time spent scanning outgoing lists and updating in-degrees is \(O(m)\). Combining these costs gives \(O(n+m)\) time. The adjacency lists use \(O(n+m)\) space, and the stored in-degrees, queue, output list, and remaining-vertex bookkeeping use \(O(n)\) additional space.
This bound also handles degenerate inputs. If \(n=0\), there are no in-degrees to initialize, the queue is empty, and the empty output is a topological order because there are no arcs to check. If \(n>0\) and \(m=0\), every vertex is initially a source; each is enqueued and removed once, and the running time is \(O(n)\). Isolated vertices in a larger digraph are handled in the same way: they are sources and can appear anywhere in the output without violating an arc constraint.
Worked Example: Counting the Adjacency-List Work
Let \(D=(V,A)\), where \(V=\{p,q,r,s\}\) and \(A=\{p\to r,\ q\to r,\ r\to s\}\). Its adjacency lists are \(p:[r]\), \(q:[r]\), \(r:[s]\), and \(s:[]\). Initializing four counters and scanning the three listed arcs gives the in-degrees \(d^-(p)=0,\ d^-(q)=0,\ d^-(r)=2,\ d^-(s)=1\). The queue starts as \([p,q]\).
| Removed vertex | Arc scanned and update | Queue after the update | Output |
|---|---|---|---|
| \(p\) | \(p\to r:\ 2\to1\) | \([q]\) | \([p]\) |
| \(q\) | \(q\to r:\ 1\to0\), enqueue \(r\) | \([r]\) | \([p,q]\) |
| \(r\) | \(r\to s:\ 1\to0\), enqueue \(s\) | \([s]\) | \([p,q,r]\) |
| \(s\) | No outgoing arcs | \([]\) | \([p,q,r,s]\) |
The output is \(p,q,r,s\), and the three arcs point forward: \(p\to r\) has positions \(1<3\), \(q\to r\) has \(2<3\), and \(r\to s\) has \(3<4\). The initial degree sum is \(0+0+2+1=3\), equal to the three arcs. The algorithm scans four adjacency lists once, and the total number of entries scanned is \(1+1+1+0=3=m\); each arc causes exactly one in-degree decrement.
A Common Queue Mistake
Consider \(V=\{a,b,c\}\) and \(A=\{a\to c,\ b\to c\}\). The in-degrees are \(0,0,2\), and the correct initial queue is \([a,b]\). A mistaken invariant sometimes says that the queue contains zero-in-degree vertices “that have not already been queued.” Applied literally, that condition excludes both \(a\) and \(b\), even though both are in the queue. It would also fail to justify that a source is available for removal.
The correction is to say that the queue contains precisely the remaining vertices whose stored in-degree is zero and that have not yet been removed, with each such vertex appearing once. Here both \(a\) and \(b\) are remaining zero-in-degree vertices, so both belong to the queue. After removing \(a\), the update is \(d^-(c):2\to1\), and the queue is \([b]\); after removing \(b\), the update is \(d^-(c):1\to0\), so \(c\) is enqueued. The resulting order \(a,b,c\) respects both arcs.
Source removal is useful because it converts a global ordering condition into local updates. The algorithm does not need to guess a full order: it certifies each next vertex using its current in-degree. If a DAG is given, the source-existence argument guarantees progress; if the queue empties too soon, the partial output cannot be completed by this procedure, and the remaining digraph contains a directed cycle.
Check Your Understanding
For each question, distinguish the stored in-degree in the remaining digraph from the original in-degree.
- For \(V=\{x,y,z\}\) and \(A=\{x\to z,y\to z\}\), give the initial queue and all updates when the algorithm removes \(x\), then \(y\).
- Why can a remaining source never be absent from the queue under the stated invariant?
- Explain why a complete output of source removal cannot contain the vertices of a directed cycle.
- If a graph has \(n=0\) vertices, what output does the algorithm return, and why is it a topological order?
- For adjacency lists, why is the total number of outgoing-arc scans at most \(m\), rather than \(nm\)?