Explain depth-first search (DFS). Implement it recursively and iteratively in C#, and show how DFS detects cycles in a directed graph and produces a topological order, for example for build or migration dependencies.

1. Recursive DFS and the call stack

void Visit(Node n)
{
    if (!visited.Add(n)) return;
    Pre(n);
    foreach (var m in n.Next) Visit(m);
    Post(n);
}

The recursion depth equals the length of the current path. A chain of 100,000 nodes means 100,000 frames, which can overflow the 1 MB default thread stack, and a StackOverflowException kills the .NET process. For untrusted or very deep graphs, use the iterative form.

2. Iterative DFS that still gives post-order

A simple Stack<T> gives pre-order easily. For post-order (needed for topological sort) push a marker or keep an enumerator per frame:

stack of (node, enumerator over its neighbours)
push (start, start.Next.GetEnumerator())
while stack not empty:
    (n, it) = peek
    if it.MoveNext():
        m = it.Current
        if m is white: colour grey, push (m, m.Next.GetEnumerator())
        else if m is grey: cycle!
    else:
        pop; colour n black; output.Add(n)   <- post-order

This mirrors exactly what the recursive version does with the call stack, but the stack lives on the heap.

3. Edge classification

During DFS on a directed graph every edge u → v is one of:

Only back edges matter for cycle detection. In undirected graphs, a cycle is any edge to a visited node that is not the parent you came from.

4. Topological sort worked through

Dependencies (X -> Y means X depends on Y):
  Api   -> Domain, Infra
  Infra -> Domain
  Tests -> Api

DFS from Tests: Tests(grey) -> Api(grey) -> Domain(grey, no deps) -> black, output [Domain]
                                       -> Infra(grey) -> Domain(black, skip) -> black, output [Domain, Infra]
                 Api black, output [Domain, Infra, Api]
Tests black, output [Domain, Infra, Api, Tests]
Build order: Domain, Infra, Api, Tests

If edges point the other way ("X is needed by Y"), reverse the final list.

5. Recovering the cycle path

Keep a parent map or the current path stack. When you hit a grey node g, walk the path back from the current node until g:

path stack: [Tests, Api, Infra, Shared]
edge Shared -> Api (Api is grey)
cycle: Api -> Infra -> Shared -> Api

Reporting the cycle is what turns a hang into a fixable error message.

6. Backtracking is DFS over a decision tree

Generating permutations, solving sudoku, or exploring configuration combinations is DFS where each level is a choice. Undo the choice when you return (backtrack). Prune branches early when constraints already fail; that pruning is what makes backtracking usable.

7. Try it yourself

var deps = new Dictionary<string, string[]>
{
    ["Tests"] = ["Api"],
    ["Api"] = ["Domain", "Infra"],
    ["Infra"] = ["Domain"],
    ["Domain"] = [],
};
Console.WriteLine(string.Join(" -> ", TopoSort.Order(deps)));   // Domain -> Infra -> Api -> Tests

deps["Domain"] = ["Tests"];                                      // introduce a cycle
try { TopoSort.Order(deps); }
catch (InvalidOperationException ex) { Console.WriteLine(ex.Message); }

Use the TopoSort class from the code example.

public static class TopoSort
{
    private enum Colour : byte { White, Grey, Black }

    // deps[x] = things x depends on. Returns dependencies first. Iterative: no stack overflow.
    public static List<string> Order(IReadOnlyDictionary<string, string[]> deps)
    {
        var colour = new Dictionary<string, Colour>();
        var output = new List<string>(deps.Count);
        var path = new Stack<(string Node, IEnumerator<string> Next)>();

        foreach (var root in deps.Keys)
        {
            if (colour.GetValueOrDefault(root) != Colour.White) continue;
            colour[root] = Colour.Grey;
            path.Push((root, Neighbours(deps, root)));

            while (path.Count > 0)
            {
                var (node, next) = path.Peek();
                if (next.MoveNext())
                {
                    var dep = next.Current;
                    switch (colour.GetValueOrDefault(dep))
                    {
                        case Colour.White:
                            colour[dep] = Colour.Grey;
                            path.Push((dep, Neighbours(deps, dep)));
                            break;
                        case Colour.Grey:
                            throw new InvalidOperationException("Circular dependency: " + DescribeCycle(path, dep));
                        // Black: already ordered, nothing to do
                    }
                }
                else
                {
                    path.Pop();
                    colour[node] = Colour.Black;
                    output.Add(node);            // post-order: after all its dependencies
                }
            }
        }
        return output;
    }

    private static IEnumerator<string> Neighbours(IReadOnlyDictionary<string, string[]> deps, string n) =>
        ((IEnumerable<string>)(deps.TryGetValue(n, out var d) ? d : [])).GetEnumerator();

    private static string DescribeCycle(Stack<(string Node, IEnumerator<string> Next)> path, string start)
    {
        var nodes = path.Select(p => p.Node).Reverse().ToList();   // bottom of stack first
        var cycle = nodes.Skip(nodes.IndexOf(start)).Append(start);
        return string.Join(" -> ", cycle);
    }
}

// Recursive DFS for comparison: connected components in an undirected graph
public static int CountComponents(Dictionary<int, List<int>> g)
{
    var seen = new HashSet<int>();
    int count = 0;
    foreach (var v in g.Keys)
        if (seen.Add(v)) { count++; Dfs(v); }
    return count;

    void Dfs(int u)
    {
        foreach (var w in g[u])
            if (seen.Add(w)) Dfs(w);   // recursion depth up to V: fine for small graphs only
    }
}