How it works
A topological order places each node before the nodes that depend on it in a directed acyclic graph. Here an edge from A to C means A must be scheduled before C. Kahn's algorithm counts incoming edges and begins with nodes whose prerequisite count is zero.
A and B are initially ready. Removing each decrements C's incoming count, and C becomes ready only after both have been processed. Processing C makes D ready. The SortedSet chooses among simultaneously ready names deterministically, so the displayed order is A, B, C, D.
A graph can have several valid topological orders. The ordinal tie rule is a presentation policy, not a mathematical requirement. Tests should verify that every dependency edge respects the resulting positions, while exact-output tests should also state any deterministic tie policy the application intentionally chooses.
A cycle prevents all its remaining nodes from becoming ready. If processing stops before every declared node was output, the graph cannot be fully ordered under these dependencies. The second example demonstrates this failure with A depending through B back to A. Returning a partial list as if it were complete would hide the invalid schedule.
Practice with two independent chains, a node with no edges, and a self-loop. Predict the initial ready set and the point where each node's count becomes zero. Add validation if input neighbors may refer to undeclared nodes, because the small sample assumes a complete node dictionary.
Finally, use the result to model a tiny build or lesson-prerequisite plan. Keep edge direction explicit in names and documentation; reversing the meaning of an edge can produce a valid-looking order for the wrong problem. The algorithm's correctness depends on declared prerequisites, accurate counts, and a clear failure when a complete schedule does not exist.
A working example
using System;
using System.Linq;
using System.Collections.Generic;
using System.Globalization;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.CompilerServices;
var graph = new Dictionary<string, string[]> {
["A"] = new[] { "C" }, ["B"] = new[] { "C" }, ["C"] = new[] { "D" }, ["D"] = Array.Empty<string>()
};
Console.WriteLine(string.Join(",", Sort(graph)));
try { Sort(new Dictionary<string, string[]> { ["A"] = new[] { "B" }, ["B"] = new[] { "A" } }); }
catch (InvalidOperationException) { Console.WriteLine("cycle"); }
static List<string> Sort(Dictionary<string, string[]> graph) {
var degree = graph.Keys.ToDictionary(key => key, _ => 0, StringComparer.Ordinal);
foreach (var neighbors in graph.Values) foreach (string next in neighbors) degree[next]++;
var ready = new SortedSet<string>(degree.Where(pair => pair.Value == 0).Select(pair => pair.Key), StringComparer.Ordinal);
var result = new List<string>();
while (ready.Count > 0) {
string node = ready.Min!; ready.Remove(node); result.Add(node);
foreach (string next in graph[node]) if (--degree[next] == 0) ready.Add(next);
}
if (result.Count != graph.Count) throw new InvalidOperationException("Dependency cycle");
return result;
}
Expected output
A,B,C,D cycle
A node becomes ready only after its incoming dependency count reaches zero.