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 ? comparer = null) { Comparer = comparer ?? EqualityComparer .Default; _adjacency = new Dictionary >(Comparer); } private IEqualityComparer Comparer { get; } public IReadOnlyCollection Nodes => _adjacency.Keys; public void AddNode(T node) { if (!_adjacency.ContainsKey(node)) _adjacency[node] = new HashSet (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 Neighbors(T node) => _adjacency.TryGetValue(node, out var set) ? set : (IReadOnlySet )new HashSet (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 (Comparer) { start }; var queue = new Queue (); 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 (Comparer); var stack = new Stack (); 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 { start }; var cameFrom = new Dictionary (Comparer); var visited = new HashSet (Comparer) { start }; var queue = new Queue (); 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 cor