Graphs: The Data Structure Behind Almost Every Interesting System

Almost every graph problem starts with picking a representation. An adjacency list (one list per node) is the default for sparse graphs and most competitive programming problems — O(V + E) space and fast iteration over a node's neighbors. An adjacency matrix trades space (O(V²)) for O(1) edge lookups, useful when the graph is dense or small.

Getting the representation right early avoids rewriting the whole solution later — something I learned the hard way in early contests.

BFS explores level by level and gives shortest paths on unweighted graphs; DFS explores depth-first and underlies cycle detection, topological sort, and connected components. For weighted graphs, Dijkstra's algorithm (with a priority queue) handles non-negative weights in O((V + E) log V); Bellman-Ford handles negative weights and detects negative cycles in O(VE); Floyd-Warshall computes all-pairs shortest paths in O(V³) when the graph is small enough.

Union-Find (Disjoint Set Union) answers connectivity and grouping questions in near-constant time per operation and is the backbone of Kruskal's minimum spanning tree algorithm. Tarjan's and Kosaraju's algorithms find strongly connected components in directed graphs, which matters for anything modeling dependencies or cyclic relationships.

These structures map directly onto real systems: a service dependency graph is a DAG that needs topological sort before deployment ordering makes sense; a C2C marketplace matching buyers to sellers across categories is a bipartite graph; and clustering ambiguous transactions, like I did at Nexius AI, borrows the same connected-components thinking used to group nodes in a graph.