Graph Algorithms Are Contracts, Not Recipes

Historical note: the implementations discussed here were added to the learn-dotnet DSA module on August 15, 2026. This article documents those learning artifacts; it does not claim benchmark or production results.

Graph algorithms are easy to collect and difficult to retain. A template for Dijkstra, another for topological sort, another for strongly connected components — then one forgotten condition turns a familiar snippet into a wrong answer.

A more durable approach is to learn each algorithm as a contract:

1. What inputs are valid?
2. What state does the algorithm maintain?
3. Which invariant makes each transition safe?
4. What exactly does the output mean?
5. How does an invalid assumption become visible?

The advanced graph module in learn-dotnet gives four useful examples.

Dijkstra: finalized distance is the invariant

The implementation uses an adjacency list, an array of distances, and .NET’s PriorityQueue<TElement, TPriority>:

distances[source] = 0;
queue.Enqueue(source, 0);

while (queue.TryDequeue(out var node, out var distance))
{
    if (distance != distances[node])
        continue;

    foreach (var edge in adjacency[node])
    {
        var candidate = checked(distance + edge.Weight);
        if (candidate >= distances[edge.To])
            continue;

        distances[edge.To] = candidate;
        queue.Enqueue(edge.To, candidate);
    }
}

The queue may contain stale entries because decreasing a key is represented by adding a new entry. The equality check discards an entry that no longer matches the best known distance. That small line is part of the correctness model, not an incidental optimization.

The input contract matters just as much: this implementation rejects negative weights. With a negative edge, the greedy claim that the next smallest distance is safe to finalize no longer holds. Returning plausible numbers would be more dangerous than failing at the boundary.

Kahn: the result carries cycle information

Topological order exists only for a directed acyclic graph. Kahn’s algorithm tracks the in-degree of every vertex, repeatedly removes zero-in-degree nodes, and decrements their outgoing neighbors.

The output contract should not pretend that a partial order is a complete answer. The learning implementation returns both the order and HasCycle. After processing, fewer emitted vertices than the graph contains is evidence that some dependency cycle prevented progress.

Tarjan: low-link values summarize reachability

Tarjan’s algorithm is often memorized as several arrays and a stack. Its mental model is more useful:

• index[v] records when DFS first discovered v;
• lowLink[v] is the earliest active discovery reachable from v through the DFS subtree and a back edge;
• the stack contains vertices that have not yet been assigned to a component;
• when lowLink[v] == index[v], v is the root of one strongly connected component.

The subtlety is “active.” An edge to a vertex already removed from the stack must not merge two completed components. That is why the implementation tracks onStack separately from whether a node was ever visited.

Union-Find: representation does the work

Disjoint-set union answers whether vertices belong to the same connected component while edges are added. Its two performance techniques encode clear invariants:

• path compression rewrites parent links during Find so later searches approach the representative directly;
• union by size or rank attaches the smaller tree under the larger one.

Kruskal’s minimum spanning tree algorithm then becomes a simple consumer: sort edges by weight and accept an edge exactly when its endpoints are in different sets. The data structure, not a special case in Kruskal, defines “would this edge create a cycle?”

Compare the contracts

This table is more reusable than four code listings. It tells us when an algorithm is applicable and which assertions belong in tests.

Test structure should mirror the contract

The repository tests include reachable and unreachable shortest paths, negative-weight rejection, valid dependency order, cycle detection, multiple strongly connected components, and disjoint-set connectivity. A robust test suite should also include isolated vertices, parallel edges where supported, self-loops, empty inputs, and overflow behavior chosen by the API.

For competitive programming, some validation may be omitted because the problem guarantees valid input. In a reusable library, the same omission is an API decision and should be documented. Context changes the boundary; it does not change the underlying invariant.

From memorization to reconstruction

When the contract is clear, code can be reconstructed:

• Dijkstra needs an ordered frontier and best-known distances.
• Kahn needs remaining prerequisites and a ready queue.
• Tarjan needs discovery order, active reachability, and component boundaries.
• Union-Find needs representatives and cheap merging.

That is the bridge between DSA study and engineering. The algorithm stops being a spell and becomes a small system whose state transitions can be explained, tested, and rejected when its assumptions do not hold.

Sources

• learn-dotnet advanced graph implementations
• PriorityQueue<TElement,TPriority> — .NET API