Data Structure
Graph
A set of vertices (nodes) connected by edges, modeling relationships like networks, maps, and dependencies.
Nodes and connections.
A graph is a bunch of points (vertices) joined by lines (edges). It's how we model things that are connected: friends in a social network, cities linked by roads, or web pages linked by hyperlinks.
- Directed — edges have a direction (one-way follows); undirected — mutual connections.
- Weighted — edges carry a cost/distance.
- Cyclic vs acyclic — whether you can loop back to where you started.
Representations and traversal.
- Adjacency list — each vertex stores its neighbors; space O(V+E), great for sparse graphs.
- Adjacency matrix — a V×V grid; O(1) edge lookup but O(V²) space, good for dense graphs.
core traversals
BFS queue-based, shortest path in unweighted graphs, level order DFS stack/recursion, cycle detection, topological sort, components
Classic algorithms.
- Shortest paths — Dijkstra (non-negative weights), Bellman–Ford (handles negatives/detects negative cycles), A* (heuristic-guided), Floyd–Warshall (all pairs).
- Minimum spanning tree — Kruskal (union-find) and Prim (priority queue).
- Ordering & structure — topological sort (DAGs), strongly connected components (Tarjan/Kosaraju).
- Flow & matching — max-flow/min-cut (Ford–Fulkerson/Edmonds–Karp), bipartite matching.
- Union-Find (DSU) — near-O(1) connectivity with path compression + union by rank.