Graphs

Graphs#

Graph algorithms underpin networks, dependencies, routing, scheduling, recommendations, and far more. The vocabulary alone is worth knowing.

Vocabulary#

The terminology that gets used loosely in conversation but matters precisely in algorithm choice. Whether a graph is directed, weighted, dense, or acyclic determines which algorithms apply, and which run in polynomial time vs NP-hard.

  • Vertex / Node, the elements.

  • Edge, a connection between two vertices.

  • Directed, edges have a direction.

  • Weighted, edges have numeric weights.

  • Cyclic / acyclic, whether a path can return to its start.

  • Dense vs. sparse, E ≈ V² vs. E ≪ V².

  • Connected (undirected) / strongly connected (directed) – every vertex reachable from every other.

  • DAG, Directed Acyclic Graph. The structure of dependencies.

Representations#

The three storage forms for a graph. Pick by graph density. adjacency list for sparse graphs (almost all real graphs); adjacency matrix when E approaches V² or you need constant-time edge queries; edge list for batch algorithms that process edges in bulk.

  • Adjacency list, each vertex stores its neighbors. O(V + E) space. Default for sparse graphs.

  • Adjacency matrix, V×V matrix of booleans / weights. O(V²) space. Better for dense graphs and constant-time edge queries.

  • Edge list, list of (u, v, w) triples. Useful for bulk edge algorithms (Kruskal).

Traversal: BFS and DFS#

The two foundational graph traversals, both O(V+E) and the basis for almost every other graph algorithm. BFS visits layer by layer (shortest path in unweighted graphs); DFS descends as far as possible (cycle detection, components, topological order, edge classification).

Breadth-First Search (BFS)

  • Queue-based.

  • O(V + E).

  • Visits in increasing distance from the source.

  • Shortest path in unweighted graphs.

Depth-First Search (DFS)

  • Stack-based or recursive.

  • O(V + E).

  • Detects cycles, finds connected components, classifies edges (tree / back / forward / cross).

  • Foundation for many algorithms below.

Topological Sort#

Order DAG vertices so all edges go forward. The standard tool for build systems, task scheduling, and compiler dependency analysis; anywhere “do A before B” relationships need to collapse into a linear order. Two algorithms.

  • Kahn’s algorithm, repeatedly remove a vertex with in-degree zero.

  • DFS-based, post-order DFS, reverse the result.

Used for: build systems, task scheduling, compiler dependency analysis.

Shortest Paths#

The shortest-path family, organized by what edge weights you allow and whether you want one source’s distances or all-pair distances. The single-source case is far more common in practice; pick by weight constraints.

Single-source.

  • BFS, O(V + E). Unweighted graphs.

  • Dijkstra, O((V + E) log V) with a binary heap. Non-negative weights only.

  • Bellman-Ford, O(VE). Handles negative weights; detects negative cycles.

  • 0-1 BFS, O(V + E) when edges weigh 0 or 1; uses a deque.

All-pairs.

  • Floyd-Warshall, O(V³). Dense graphs; small V.

  • Johnson’s, O(V² log V + VE). Sparse graphs with negative weights.

Specialized.

  • A*, ALT (A* with landmarks), Contraction Hierarchies, routing on road networks; orders of magnitude faster than Dijkstra in practice.

Minimum Spanning Tree (MST)#

Smallest-weight set of edges connecting all vertices in an undirected graph. Used in network design (laying cable, trade- route planning), clustering, and as a subroutine in approximation algorithms. Three classic approaches.

  • Kruskal, sort edges; add if they don’t form a cycle (Union-Find). O(E log E).

  • Prim, grow a tree from one vertex, always adding the cheapest edge to a new vertex (priority queue). O((V + E) log V).

  • Borůvka, parallel-friendly historical algorithm.

Applications: network design, clustering, approximation algorithms.

Connectivity#

How “joined up” a graph is. Connected components for undirected graphs; strongly connected components for directed; articulation points and bridges for finding the critical pieces whose removal would split the graph.

  • Connected components (undirected), BFS / DFS / Union-Find.

  • Strongly connected components (SCC) (directed), Tarjan’s (one-pass DFS) or Kosaraju’s (two-pass DFS, on graph and reverse). Both O(V + E).

  • Articulation points and bridges, vertices / edges whose removal disconnects the graph. Tarjan’s algorithm.

Cycles#

Detection is easy and polynomial; enumeration is hard. DFS back-edge detection covers the common “is there a cycle” question; finding all cycles in a graph is generally exponential.

  • Detect cycle in directed graph, DFS, look for back edges.

  • Detect cycle in undirected graph, DFS or Union-Find while processing edges.

  • Find all cycles, generally exponential; algorithms like Johnson’s list elementary cycles.

Eulerian and Hamiltonian Paths#

Two famous “visit everything once” problems with very different complexity stories. Eulerian (every edge) is polynomial; Hamiltonian (every vertex) is NP-complete. The distinction is one of the standard examples of how a small change in problem statement flips the tractability story.

  • Eulerian, visits every edge exactly once. Exists iff the graph is connected and (undirected) every vertex has even degree, or (directed) every vertex has equal in- and out-degree, with at most one imbalance pair. Polynomial-time to find.

  • Hamiltonian, visits every vertex exactly once. NP-complete to decide.

Network Flow#

How much “flow” can pass from a source to a sink given edge capacities. The framework is more general than it looks – the min-cut max-flow theorem turns a wide range of problems (bipartite matching, image segmentation, project selection) into max-flow instances.

  • Ford-Fulkerson with augmenting paths.

  • Edmonds-Karp (BFS-based), O(VE²).

  • Dinic, O(V²E), much faster in practice.

Min-cut max-flow theorem, the maximum flow equals the minimum cut capacity. Underlies bipartite matching, image segmentation, project selection.

Bipartite Matching#

Match vertices in two sets such that no vertex is matched twice. The classic “assignment problem”, pairing workers to jobs, ads to slots, students to rooms. Two algorithms cover the unweighted and weighted cases.

  • Hopcroft-Karp, O(E √V).

  • Hungarian algorithm, weighted bipartite matching (assignment problem). O(V³).

Applications: assignment of jobs to workers, online ad allocation.

Graph Coloring#

Assign colors to vertices so adjacent vertices differ. Optimal coloring is NP-complete; bipartiteness (2-colorability) is polynomial. Real applications (scheduling, register allocation, frequency assignment) usually settle for greedy approximations.

  • Chromatic number decision is NP-complete.

  • 2-coloring (bipartiteness check), O(V + E) with BFS.

  • Greedy, O(V + E); not optimal in general.

Applications: scheduling, register allocation in compilers, frequency assignment.

Algorithms in Practice#

Where the algorithms above show up in real software. Each entry maps a category of work to the graph algorithm it typically rests on; knowing the mapping is most of the value of studying graph algorithms in the first place.

  • Dependency / build systems, topological sort.

  • Pathfinding (games, robots), A*.

  • Route planning (maps), Dijkstra at small scale, Contraction Hierarchies / Hub Labels at planet scale.

  • Recommendations, collaborative filtering as bipartite graph algorithms; personalised PageRank.

  • PageRank / centrality, iterative power-method; underlies search ranking.

  • Community detection, modularity, label propagation.

  • Social-graph queries, BFS up to depth 3 or so; pre-computed friend-of-friend tables for hot paths.

Graph Libraries#

Mature graph libraries by language, plus the specialized graph stores for very large workloads. Most prototyping work ends up in NetworkX or igraph; production graph systems pull in a graph database (Neo4j, Memgraph) or a distributed engine when scale demands it.

For very large graphs, specialized stores (Neo4j, Memgraph, JanusGraph) or distributed engines (Pregel-family, GraphX) make sense.

Contents