Graph structures model relationships between entities — service dependencies, social edges, road networks — where trees are too restrictive: cycles exist, multiple paths connect the same pair, and there’s no root. .NET has no Graph<T> type; you compose one from primitives, and the composition depends on which relationship question must be cheap. A Dictionary<TNode, List<TNode>> adjacency list makes neighbor traversal cheap; a bool[,] matrix makes edge-existence O(1); two int[] arrays (a disjoint set) make “are these connected?” near-O(1) without storing edges at all.

That last option is the reason this folder splits into three notes. Graph is the explicit representation — you keep vertices and edges and run traversals (BFS, DFS, Dijkstra) over them. Disjoint Set keeps no edges: it collapses the graph into “which component is this vertex in?”, trading every other question away for near-constant connectivity queries and merges. Union-Find is the companion to Disjoint Set — the two heuristics (union by rank, path compression) that keep that forest shallow, and the amortized O(α(n)) analysis that proves the near-constant bound.

Which Note You Need

flowchart TD
    A{What must be cheap?} -->|Paths, distances, orderings, cycles| B[Graph with BFS DFS Dijkstra]
    A -->|Same component as edges arrive over time| C[Disjoint Set]
    A -->|Both, canonical case Kruskal MST| D[Graph plus Disjoint Set]

The decision hinges on whether connectivity is static or dynamic. One-off “is B reachable from A?” on a fixed graph — a single BFS is simpler and answers directionality too. Edges arriving incrementally with connectivity queries interleaved — re-running BFS per query is O(V + E) each time, while a disjoint set amortizes to near-constant. The cost of the disjoint set: it only handles undirected connectivity and can never un-merge (no edge deletion).

Questions

When does a disjoint set beat BFS for connectivity, and what do you give up?

When edges arrive over time and connectivity queries interleave with insertions: each union/find is O(α(n)) ≈ O(1), versus O(V + E) to re-traverse per query. You give up everything except component identity — no paths, no distances, no directed reachability, and merges are irreversible (no edge deletion).

References

• Graph theory (Wikipedia) — vocabulary for vertices, edges, directed vs undirected, and connectivity; the shared language both child notes assume.
• Disjoint-set data structure (Wikipedia) — the operations, the forest representation, and the O(α(n)) analysis.
• PriorityQueue<TElement, TPriority> class — the one .NET primitive built specifically for weighted-graph algorithms (Dijkstra, Prim).