Graph
Nodes connected by edges — the most general data structure. Roads, social networks, dependencies, and the web are all graphs; most hard practical problems are graph problems in disguise.
A graph is a set of vertices and a set of edges between them. Edges can be directed (one-way, like "A depends on B") or undirected, and weighted (costs, distances) or not. A tree is just a connected graph with no cycles; a DAG is a directed graph with none.
Two standard representations: the adjacency list (each node keeps a list of neighbours — O(V+E) space, the default) and the adjacency matrix (a V×V grid — O(1) edge lookup, O(V²) space, right for dense graphs or Floyd-Warshall).
Nearly every graph question reduces to a handful of primitives: BFS for unweighted shortest paths and level structure; DFS for reachability, cycle detection, and topological order; Dijkstra/A* for weighted shortest paths; Prim/Kruskal for cheapest connectivity (MST). Master those and most real problems become recognisable.
Operations
| Operation | Complexity |
|---|---|
| add vertex/edge (adj list) | O(1) |
| neighbour iteration | O(deg v) |
| BFS / DFS | O(V + E) |
| Dijkstra (heap) | O(E log V) |
Where it's used
Navigation and routing, dependency resolution and build systems, social networks, recommendation engines, network topology.