A graph is a non-linear data structure consisting of nodes, also called vertices, and edges that connect pairs of vertices. Two principal ways exist to represent a finite graph in memory: an adjacency matrix is a square matrix whose entries indicate whether pairs of vertices are adjacent, while an adjacency list is a collection of unordered lists where each list describes the set of neighbors of one vertex. Several specialized graph types also appear in practice: a directed acyclic graph (DAG) has no directed cycles and forms the basis of topological sorting, a forest is a disjoint union of trees in which any two vertices are connected by at most one path, a multigraph permits multiple edges between the same pair of vertices, a hypergraph generalizes the edge to connect any number of vertices, and a planar graph can be drawn in the plane with no crossing edges, a property captured by Euler's formula \(v - e + f = 2\) for a connected planar graph with v vertices, e edges, and f faces. Graph decomposition, the process of breaking a graph into subgraphs such as connected components, biconnected components, or strongly connected components, often simplifies analysis and solution design.
The two foundational traversal algorithms for graphs are breadth-first search (BFS) and depth-first search (DFS). BFS starts at a source node and explores the graph layer by layer, visiting all neighbors of the current depth before moving to the next. DFS starts at a chosen root and explores as far as possible along each branch before backtracking. A spanning tree of a graph is a subset of edges that covers all vertices with the minimum possible number of edges, contains no cycles, and is connected; a minimum spanning tree (MST) further minimizes the total edge weight. Two classical greedy algorithms find an MST: Prim's algorithm grows a single tree by repeatedly adding the cheapest edge that connects the tree to a new vertex, while Kruskal's algorithm picks the edge of least possible weight that connects any two trees in the forest. For shortest paths, Dijkstra's algorithm finds shortest paths from a source in a graph with non-negative weights, the Bellman-Ford algorithm handles graphs with negative edge weights (though not negative-weight cycles) and is improved by SPFA, the Shortest Path Faster Algorithm, which works well on random sparse graphs but has worst-case exponential behavior. Floyd-Warshall solves the all-pairs shortest path problem, and Johnson's algorithm finds all-pairs shortest paths while allowing negative edge weights but no negative-weight cycles, using Dijkstra with reweighted edges. A* search is a graph traversal and path search algorithm that is complete, optimal, and optimally efficient when guided by an admissible heuristic.
Beyond traversal and shortest paths, graphs admit a rich collection of structural and combinatorial algorithms. Topological sorting of a DAG produces a linear ordering of vertices such that for every directed edge \(u \to v\), u appears before v; Kahn's algorithm implements this by repeatedly removing nodes with zero in-degree. The strongly connected components (SCCs) of a directed graph can be found in linear time by either Tarjan's algorithm, which uses DFS together with discovery times and low-link values, or Kosaraju's algorithm, which performs two passes of DFS. An articulation point, or cut vertex, is a vertex whose removal disconnects the graph, while a bridge is an edge whose removal disconnects it. Maximum flow problems are solved by the Ford-Fulkerson algorithm, which uses DFS or BFS to find augmenting paths; the Edmonds-Karp algorithm is an implementation that uses BFS and runs in \(O(VE^2)\) time; Dinic's algorithm improves on this by using level graphs and blocking flows; and the push-relabel algorithm is generally even more efficient. The Max-Flow Min-Cut theorem states that the maximum flow from source to sink equals the capacity of the minimum cut. Matching problems include maximum bipartite matching, solved efficiently by the Hopcroft-Karp algorithm in \(O(E\sqrt{V})\) time, and the stable marriage problem, which finds a stable matching between two equally sized sets given each element's preferences. An Eulerian path visits every edge exactly once, and a Hamiltonian path visits every vertex exactly once. Graph coloring assigns labels to vertices so that no two adjacent vertices share a label, and the chromatic number is the smallest number of colors required. In computational geometry, the convex hull of a set of points is the smallest convex polygon containing them, Graham scan finds it in \(O(n \log n)\) time, and line intersection seeks the intersection points of lines or line segments. Finally, 2-SAT, the satisfiability problem where each clause has exactly two literals, can be solved in linear time using strongly connected components.