Graph terminology, adjacency list vs matrix vs edge list, directed acyclic graphs, topological sort and cycle detection, and real-world graphs such as DI containers, build systems and job schedulers.
A graph is a set of vertices (nodes) connected by edges. Edges can be directed or undirected, weighted or not, and the graph may contain cycles. Trees are a special case (connected, no cycles).
Representations:
Dictionary<TNode, List<TNode>>): O(V + E) memory, best for sparse graphs (most real ones).bool[V,V]): O(V²) memory, O(1) edge check, for small dense graphs.Backend graphs: service and package dependencies, DI containers, build systems (project references), workflow/job DAGs, permission inheritance, routing, social links.
For dependencies you need a DAG: find an execution order with topological sort (Kahn's algorithm, O(V + E)); if not all nodes can be ordered, there is a cycle.
| Term | Meaning |
|---|---|
| Vertex / edge | Node / connection |
| Directed / undirected | One-way (A → B) vs two-way |
| Weighted | Edge has a cost (distance, latency) |
| Degree (in/out) | Number of incoming/outgoing edges |
| Path / cycle | Sequence of edges / path returning to its start |
| DAG | Directed acyclic graph |
| Connected component | Group of nodes reachable from each other |
Graph: A → B, A → C, B → D, C → D
Adjacency list: Adjacency matrix: Edge list:
A: [B, C] A B C D (A,B) (A,C)
B: [D] A [ 0 1 1 0 ] (B,D) (C,D)
C: [D] B [ 0 0 0 1 ]
D: [] C [ 0 0 0 1 ]
D [ 0 0 0 0 ]
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Memory | O(V + E) | O(V²) |
| Iterate neighbours | O(degree) | O(V) |
| Check edge exists | O(degree) (O(1) with sets) | O(1) |
| Best for | Sparse graphs | Small, dense graphs |
A data platform ran ~400 nightly jobs with dependencies defined in configuration. A new job accidentally depended on a job that depended on it, and the home-grown scheduler simply waited forever: the nightly run stalled and reports were late. We replaced the ad-hoc logic with Kahn's algorithm at deploy time: build the graph, topologically sort, and fail the deployment with the cycle's path if any nodes remain. The same order drove parallel execution (all jobs with in-degree 0 run together).
Checks graph literacy and the ability to apply it to real engineering problems.
Green flags
Red flags
1. Count incoming edges (in-degree) for every node.
2. Queue all nodes with in-degree 0.
3. Repeatedly dequeue a node, append it to the order, and decrement the in-degree of its neighbours;
enqueue any neighbour that reaches 0.
4. If the order contains every node → valid order. Otherwise the remaining nodes are in or behind a cycle.
A → B → D in-degree: A0 B1 C1 D2
A → C → D order: A, (B, C), D ← B and C can run in parallel
Time O(V + E). Running each "level" (all nodes that become ready together) in parallel gives a natural parallel schedule.
white = unvisited, grey = on the current DFS path, black = finished
Visiting an edge to a GREY node means a back edge → cycle.
This also lets you report the cycle path (useful error messages: JobA → JobB → JobC → JobA).
| Option | When |
|---|---|
| In-memory adjacency lists | Up to millions of edges, computed per request or at startup |
Relational tables (Edges(From, To)) + recursive CTEs |
Hierarchies and moderate graph queries in SQL Server/PostgreSQL |
| Graph databases (Neo4j, Cosmos DB Gremlin, SQL Server graph tables) | Many multi-hop queries, relationship-heavy domains |
| Problem | Algorithm |
|---|---|
| Reachability, connected components | BFS / DFS |
| Shortest path, unweighted | BFS |
| Shortest path, weighted non-negative | Dijkstra with a priority queue |
| Ordering dependencies | Topological sort |
| Minimum spanning tree | Kruskal (union-find) / Prim |
| Detect cycles | DFS colours / union-find (undirected) |
(Traversal algorithms are covered in the Algorithms section.)
// Adjacency list + Kahn's topological sort with cycle detection
public sealed class DependencyGraph<T> where T : notnull
{
private readonly Dictionary<T, List<T>> _edges = new(); // prerequisite → dependants
public void AddNode(T node) => _edges.TryAdd(node, []);
public void AddDependency(T node, T dependsOn)
{
AddNode(node);
AddNode(dependsOn);
_edges[dependsOn].Add(node);
}
/// Returns batches of nodes that can run in parallel, in order.
public IReadOnlyList<IReadOnlyList<T>> ExecutionPlan()
{
var inDegree = _edges.Keys.ToDictionary(n => n, _ => 0);
foreach (var dependants in _edges.Values)
foreach (var d in dependants) inDegree[d]++;
var ready = inDegree.Where(kv => kv.Value == 0).Select(kv => kv.Key).ToList();
var plan = new List<IReadOnlyList<T>>();
int scheduled = 0;
while (ready.Count > 0)
{
plan.Add(ready);
scheduled += ready.Count;
var next = new List<T>();
foreach (var node in ready)
foreach (var dependant in _edges[node])
if (--inDegree[dependant] == 0) next.Add(dependant);
ready = next;
}
if (scheduled != _edges.Count)
{
var stuck = inDegree.Where(kv => kv.Value > 0).Select(kv => kv.Key);
throw new InvalidOperationException($"Cycle detected involving: {string.Join(", ", stuck)}");
}
return plan;
}
}
// Usage
var g = new DependencyGraph<string>();
g.AddDependency("Reports", "Sales");
g.AddDependency("Reports", "Inventory");
g.AddDependency("Sales", "Customers");
foreach (var batch in g.ExecutionPlan())
Console.WriteLine(string.Join(" | ", batch)); // Inventory | Customers, then Sales, then Reports
HashSet<T>.Many backend problems are graph problems in disguise: dependency ordering, impact analysis, permission inheritance, call-graph tracing. Recognising that lets me use proven algorithms (topological sort, BFS, Dijkstra) instead of fragile ad-hoc loops, and gives clear guarantees: O(V + E) time, cycles detected and reported.
The senior move is where to validate: reject cycles at configuration or deploy time, not at 2 am when the scheduler stalls. I also like to expose the graph (e.g. visualise job dependencies or service call graphs) because it makes blast radius and critical paths obvious to the whole team.
A tree is a hierarchy of nodes with one root, where each node has children and no cycles. A binary tree limits each node to two children (left, right). A binary search tree (BST) adds an ordering rule: left subtree < node < right subtree, so search, insert and delete take O(height).
If the tree is balanced, height is O(log n); if you insert sorted data into a plain BST it degenerates into a linked list with O(n) height. Self-balancing trees (red-black, AVL) keep O(log n); .NET's SortedSet and SortedDictionary are red-black trees.
Traversals: in-order (sorted output for a BST), pre-order (copy/serialise), post-order (delete/evaluate), level-order (BFS).
Trees are everywhere: database B+ tree indexes, file systems, JSON/XML/DOM, Roslyn syntax trees, expression trees, org charts.
A heap is a complete tree stored in an array that keeps the heap property: in a min-heap every parent ≤ its children, so the smallest item is always at the root.
.NET's PriorityQueue<TElement,TPriority> (.NET 6+) is an array-backed min-heap (4-ary internally). Enqueue, Dequeue, TryPeek, EnqueueDequeue; not stable for equal priorities; no decrease-key (Remove was added in .NET 9). For a max-heap, pass a reversed comparer.
Top K from a stream: keep a min-heap of size K; for each item, if it beats the heap's minimum, replace it. That is O(n log K) time and O(K) memory.
(Not to be confused with the managed heap, which is memory.)
Graph traversal means visiting every node reachable from a start node exactly once, using a visited set so cycles do not loop forever. The two basic orders are BFS (breadth-first, uses a queue) and DFS (depth-first, uses a stack or recursion).
BFS visits nodes in layers of distance 0, 1, 2, ... so the first time it reaches a node is via the fewest edges: it finds shortest paths in unweighted graphs. O(V + E) time, O(V) space. Uses: degrees of separation, nearest available item, impact of a change in a dependency graph, web crawling by depth.
DFS goes as deep as possible along one branch before backtracking. It uses recursion or an explicit stack, plus a visited set. O(V + E) time, O(V) space (the longest path).
Key uses:
How to tell it (STAR)
**S:** Our nightly [data run] stalled and reports were late because [12] jobs waited forever. **T:** I had to unblock it and make sure it could not happen again. **A:** I traced the prerequisites and found a dependency cycle introduced the day before. After fixing it, I replaced the scheduler's ordering logic with a topological sort that runs in CI and at deploy time, rejects cycles with a readable path, and runs independent jobs in parallel. **R:** The nightly run finished [40%] faster thanks to parallel batches, and two later cycles were caught in pull requests instead of production.
Last updated 23 Oct 2026.