Union-Find vs Traversal vs Components vs Bridges

Four tools answer questions about whether a graph holds together, and the wording of the question picks one: union-find, a breadth-first or depth-first traversal, strongly connected components, or bridges and articulation points. The card sets them side by side and gives the rule for choosing.

All four group vertices by what can reach what, and all except union-find are a depth-first or breadth-first search underneath. They differ on three things: whether the graph is directed, whether its edges change while questions are asked, and whether the question is about reach or about what failure would break it. Union-find is the structure Kruskal's algorithm used: it keeps vertices in sets, merges two sets when an edge joins them, and says whether two vertices share a set in close to constant time.

Union-find is the tool when edges arrive over time and each question must be answered at once, because a traversal would start again from scratch after every new edge. It has two limits. It cannot remove an edge, since a merged set does not remember which edge merged it. And it cannot see direction: a union of A and B means A and B are together, whichever way the edge pointed. On the topic's directed graph, union-find over all eight edges puts the seven vertices into one set, while the graph has four strongly connected components, because G->F joins G to F although F cannot reach G.

A traversal answers the fixed-graph questions: the connected parts of an undirected graph, or everything reachable from one vertex in either kind. It does not answer whether two vertices reach each other in a directed graph without searching from both, which is the job components do for every pair at once. Bridges and articulation points ask a different question: which single edge or vertex, if removed, would disconnect the graph.

The rule: read what the question asks. Edges that keep arriving point to union-find. One-way edges and a question about reaching each other point to strongly connected components. A single failure point to bridges and articulation points. Anything else about a fixed graph is one traversal.