Topologically sort a directed graph
Return a topological ordering of a directed acyclic graph, or reject the graph when it contains a cycle.
Course progress
Problem 79 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
edges = [0->1, 0->2, 1->3, 2->3]
Expected output
0 1 2 3
What is happening?
Vertex 0 has no prerequisites and comes first. Vertices 1 and 2 then become available, and vertex 3 can appear only after both have been processed.
Solution strategy
Build the right mental model
Count incoming edges, queue every zero-indegree vertex, and remove outgoing edges as vertices are emitted. A short result reveals a cycle.
Core concepts
graphs · Kahn's algorithm
Complexity
Time O(vertices + edges), space O(vertices + edges).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for topological-sort
using System;
using System.Collections.Generic;
class Program
{
static List<int> TopologicalSort(List<int>[] graph)
{
int[] indegree = new int[graph.Length];
foreach (List<int> neighbors in graph)
foreach (int neighbor in neighbors) indegree[neighbor]++;
var queue = new Queue<int>();
for (int vertex = 0; vertex < graph.Length; vertex++)
if (indegree[vertex] == 0) queue.Enqueue(vertex);
var order = new List<int>();
while (queue.Count > 0)
{
int vertex = queue.Dequeue();
order.Add(vertex);
foreach (int neighbor in graph[vertex])
if (--indegree[neighbor] == 0) queue.Enqueue(neighbor);
}
if (order.Count != graph.Length) throw new InvalidOperationException("Graph contains a cycle.");
return order;
}
static void Main()
{
var graph = new[] {
new List<int> { 1, 2 }, new List<int> { 3 },
new List<int> { 3 }, new List<int>()
};
Console.WriteLine(string.Join(" ", TopologicalSort(graph)));
}
}Knowledge check
Questions students often ask
What is the main idea behind topologically sort a directed graph?
Count incoming edges, queue every zero-indegree vertex, and remove outgoing edges as vertices are emitted. A short result reveals a cycle.
What is the time and space complexity of this solution?
Time O(vertices + edges), space O(vertices + edges).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.