Graph Theory in C#

Using graph search to solve real-world problems in C#
Most day-to-day C# work involves flat collections: filter a list, sort a table, look something up by key. Those shapes are well served by LINQ and a dictionary. But some problems are about relationships rather than records, and flat collections handle them badly.

A few examples that show up in real systems:

Which permissions does a user inherit through nested role groups?
Which build targets need to rebuild when this one file changes?
Which accounts are linked, directly or indirectly, to this flagged account?
What is the shortest referral chain between two users?
Each of these is a reachability question, and reachability is what graph search answers.

Prerequisites
Working knowledge of C# generics and collections
.NET 8 or later (the code here was compiled and run against .NET 8)
No prior graph theory is assumed. The vocabulary is small and introduced as it is needed.

The vocabulary you actually need
A graph is a set of nodes connected by edges. In an undirected graph, an edge runs both ways: if Alice and Bob are friends, each is a friend of the other. In a directed graph, edges run one way: if module A imports module B, that says nothing about B importing A.

This distinction is not academic. Getting it wrong is the single most common bug in hand-rolled graph code, and it fails silently. Your traversal returns a plausible-looking result that is missing half the graph.

Traversal means visiting nodes by following edges. Two orders dominate:

Breadth-first search (BFS) visits everything one hop away, then everything two hops away, and so on. Because it expands in rings, the first time it reaches a node it has done so by the fewest possible hops. That property makes BFS the correct choice for shortest-path-by-hop-count.
Depth-first search (DFS) follows one branch as far as it goes before backtracking. It is the natural fit for cycle detection, topological sorting, and anything that needs to know when a subtree is fully explored.
Dijkstra's algorithm and A* extend this to graphs where edges carry different costs. They are out of scope here. If your edges are all equivalent, which covers most of the cases listed above, BFS and DFS are what you want.

Representing the graph
An adjacency list is the standard representation: a map from each node to the set of nodes it connects to. Sparse graphs, which is nearly all real-world graphs, use far less memory this way than with an adjacency matrix.

Four decisions in the implementation below are worth calling out before the code:

HashSet rather than List for neighbors. Adding the same edge twice is common when ingesting data, and a list would happily store duplicates, inflating traversal work and skewing any degree calculation.
AddEdge is bidirectional by default, with an opt-out. Undirected is the more common case and the one people forget to handle, so it is the default. Directed callers pass bidirectional: false explicitly, which makes the intent visible at the call site.
Both endpoints get registered as nodes. If only the source node becomes a dictionary key, the target exists as a neighbor but has no entry of its own, and traversals starting from it return nothing.
An optional IEqualityComparer. For string nodes, case sensitivity decides whether "Alice" and "alice" are one person or two. That belongs to the caller, not the data structure.
using System;
using System.Collections.Generic;

public class Graph where T : notnull
{
private readonly Dictionary> _adjacency;

public Graph(IEqualityComparer<T>? comparer = null)
{
    Comparer = comparer ?? EqualityComparer<T>.Default;
    _adjacency = new Dictionary<T, HashSet<T>>(Comparer);
}

private IEqualityComparer<T> Comparer { get; }

public IReadOnlyCollection<T> Nodes => _adjacency.Keys;

public void AddNode(T node)
{
    if (!_adjacency.ContainsKey(node))
        _adjacency[node] = new HashSet<T>(Comparer);
}

public void AddEdge(T from, T to, bool bidirectional = true)
{
    AddNode(from);
    AddNode(to);

    _adjacency[from].Add(to);

    if (bidirectional)
        _adjacency[to].Add(from);
}

public IReadOnlySet<T> Neighbors(T node) =>
    _adjacency.TryGetValue(node, out var set)
        ? set
        : (IReadOnlySet<T>)new HashSet<T>(Comparer);

}
Breadth-first search
BFS uses a queue. Pull a node, record it, enqueue any unvisited neighbors, repeat.

The detail that matters most is when a node is marked visited. Marking on enqueue, as below, guarantees each node enters the queue exactly once. Marking on dequeue instead lets a node be enqueued several times before it is first processed, which on a dense graph degrades badly.

public List BreadthFirst(T start)
{
var order = new List();
if (!_adjacency.ContainsKey(start))
return order;

var visited = new HashSet<T>(Comparer) { start };
var queue = new Queue<T>();
queue.Enqueue(start);

while (queue.Count > 0)
{
    var node = queue.Dequeue();
    order.Add(node);

    foreach (var neighbor in _adjacency[node])
    {
        if (visited.Add(neighbor))
            queue.Enqueue(neighbor);
    }
}

return order;

}
HashSet.Add returns false when the item was already present, so the check and the insert happen in one operation rather than a Contains followed by an Add.

Depth-first search, without the recursion
DFS is usually taught recursively, and the recursive version is genuinely more readable. It is also a production hazard: the call stack depth tracks the longest path in the graph. A chain of a few hundred thousand nodes, which is unremarkable for an import graph or an org hierarchy, will throw StackOverflowException. That exception cannot be caught in .NET. The process dies.

An explicit Stack moves the frames onto the heap and removes the failure mode entirely:

public List DepthFirst(T start)
{
var order = new List();
if (!_adjacency.ContainsKey(start))
return order;

var visited = new HashSet<T>(Comparer);
var stack = new Stack<T>();
stack.Push(start);

while (stack.Count > 0)
{
    var node = stack.Pop();

    if (!visited.Add(node))
        continue;

    order.Add(node);

    foreach (var neighbor in _adjacency[node])
    {
        if (!visited.Contains(neighbor))
            stack.Push(neighbor);
    }
}

return order;

}
Note the difference from BFS: here nodes are marked visited on pop, not on push, because the same node can legitimately be pushed by several neighbors before it is reached. The if (!visited.Add(node)) continue; line absorbs those duplicates.

{{CJ_AD_SLOT_2}}

Finding every connected component
A connected component is a maximal set of nodes where every node is reachable from every other node in the set. Maximal matters: if you can add another reachable node to the set, it was not a component to begin with.

A single traversal finds the one component containing your start node. Finding all of them means looping over every node and starting a fresh traversal from each one not yet seen:

public List> ConnectedComponents()
{
var components = new List>();
var seen = new HashSet(Comparer);

foreach (var node in _adjacency.Keys)
{
    if (seen.Contains(node))
        continue;

    var component = BreadthFirst(node);
    components.Add(component);

    foreach (var member in component)
        seen.Add(member);
}

return components;

}
This is correct for undirected graphs only. In a directed graph, mutual reachability is a stricter condition called a strongly connected component, and plain traversal does not compute it. A directed edge A to B means BFS from A finds B, but BFS from B may never find A, so the two are not in the same SCC even though one traversal groups them. Strongly connected components need Kosaraju's or Tarjan's algorithm. Running the code above on a directed graph and calling the output "components" is a real and easy-to-miss error.

Shortest path by hop count
Because BFS reaches every node by the fewest hops, recording how you arrived at each node yields the shortest path for free. Store a cameFrom map during traversal, then walk it backwards from the goal:

public List? ShortestPath(T start, T goal)
{
if (!_adjacency.ContainsKey(start) || !_adjacency.ContainsKey(goal))
return null;

if (Comparer.Equals(start, goal))
    return new List<T> { start };

var cameFrom = new Dictionary<T, T>(Comparer);
var visited = new HashSet<T>(Comparer) { start };
var queue = new Queue<T>();
queue.Enqueue(start);

while (queue.Count > 0)
{
    var node = queue.Dequeue();

    foreach (var neighbor in _adjacency[node])
    {
        if (!visited.Add(neighbor))
            continue;

        cameFrom[neighbor] = node;

        if (Comparer.Equals(neighbor, goal))
            return Reconstruct(cameFrom, start, goal);

        queue.Enqueue(neighbor);
    }
}

return null;

}

private List Reconstruct(Dictionary cameFrom, T start, T goal)
{
var path = new List { goal };
var current = goal;

while (!Comparer.Equals(current, start))
{
    current = cameFrom[current];
    path.Add(current);
}

path.Reverse();
return path;

}
Returning null distinguishes "no path exists" from an empty result. The nullable return type forces callers to handle the disconnected case rather than discovering it at runtime.

A worked example
Nine users, two friendship clusters, and one account with no connections:

var graph = new Graph(StringComparer.OrdinalIgnoreCase);

graph.AddEdge("Alice", "Bob");
graph.AddEdge("Bob", "Carol");
graph.AddEdge("Carol", "Dave");
graph.AddEdge("Alice", "Erin");
graph.AddEdge("Erin", "Dave");

graph.AddEdge("Frank", "Grace");
graph.AddEdge("Grace", "Heidi");

graph.AddNode("Ivan");

Console.WriteLine(string.Join(" -> ", graph.BreadthFirst("Alice")));
Console.WriteLine(string.Join(" -> ", graph.DepthFirst("Alice")));

foreach (var component in graph.ConnectedComponents())
Console.WriteLine(string.Join(", ", component));

var path = graph.ShortestPath("Alice", "Dave");
Console.WriteLine(path is null ? "no path" : string.Join(" -> ", path));
Output:

Breadth-first from Alice:
Alice -> Bob -> Erin -> Carol -> Dave

Depth-first from Alice:
Alice -> Erin -> Dave -> Carol -> Bob

Connected components:
1: Alice, Bob, Erin, Carol, Dave
2: Frank, Grace, Heidi
3: Ivan

Shortest path Alice to Dave:
Alice -> Erin -> Dave (2 hops)

Shortest path Alice to Frank:
no path
Three things in that output are worth reading carefully.

Ivan appears as his own single-node component, which is correct and is a case that breaks naive implementations. Alice reaches Dave in two hops through Erin, not three through Bob and Carol, confirming BFS found the shorter of the two available routes. And Alice to Frank returns no path, because the two clusters are genuinely disconnected.

One caveat on ordering: HashSet does not guarantee enumeration order, so the relative position of same-distance siblings (Bob and Erin above) is an implementation detail and should not be asserted in tests. The distances are deterministic; the tie-breaking is not. If you need stable ordering, sort each neighbor set before enumerating.

{{CJ_AD_SLOT_3}}

Complexity and where it stops working
All four traversals run in O(V + E) time and O(V) space, where V is nodes and E is edges. Every node is visited once and every edge is examined once.

That is fast, and it is also the ceiling. The practical limits:

Memory is the binding constraint. O(V) for the visited set plus the adjacency structure itself means the whole graph lives in RAM. Somewhere in the low millions of nodes, depending on T, this stops being viable in a single process.
BFS peak queue size scales with the widest level. On a graph with high fan-out, such as a follower network with celebrity accounts, the queue can hold a large fraction of all nodes at once. The average case looks fine and the worst case does not.
Repeated queries recompute everything. If you are answering the same reachability question against a slow-changing graph many times, cache the components rather than re-traversing.
Weighted edges need different algorithms. The moment edges carry costs, BFS gives you the fewest-hops path, which is not the cheapest path. That is Dijkstra's territory.
Cycles, worth noting, are not a problem here. The visited set handles them by construction. Cyclic graphs terminate correctly:

Cyclic graph BFS from 1: 1 -> 2 -> 3
Cycles only cause infinite loops in implementations that omit visit tracking, which is why the visited set is present from the first version rather than added as an optimization.

When to use a library instead
The code above is roughly 120 lines and it is worth writing yourself when the graph is a small part of a larger system, when you want no extra dependency, or when you are learning the algorithms.

Reach for QuikGraph instead when you need weighted algorithms, topological sort, minimum spanning trees, maximum flow, or graph serialization. Reimplementing Dijkstra correctly, including the priority queue behavior, is more error-prone than most people expect.

If the graph is the system rather than a component of it, and especially if it needs to be queried and persisted, a graph database such as Neo4j is a better fit than any in-process structure.

Summary
The four operations above cover a large share of practical graph work in C#: BFS for shortest hops, DFS for exhaustive exploration, component detection for clustering, and path reconstruction for explaining a result. The implementation is small enough to read in one sitting and to test thoroughly.

The failure modes to watch are the quiet ones. Directed edges where you assumed undirected, recursion depth on long chains, and calling a directed traversal result a connected component. None of the three throws an exception. All three produce answers that look reasonable and are wrong.