Graphs

A graph is a set of points, called vertices, joined by lines, called edges. It describes anything made of objects and links between them, such as towns and the roads between them. This page names the parts of a graph and counts, straight from the input, how many edges touch each vertex. To store a graph for an algorithm such as a search, use an adjacency list.

An edge list keeps the edges of a graph in one vector, one record per edge, usually in the order they were read. It is enough when an algorithm goes over all the edges or sorts them by weight; when it needs the neighbours of a vertex, use an adjacency list instead.

An adjacency matrix stores a graph with $n$ vertices as an n \times n table, where the cell in row $u$ and column $v$ says whether there is an edge between $u$ and $v$. Checking whether two vertices are joined reads one cell.

An adjacency list keeps, for every vertex of a graph, the list of its neighbours. Most graph algorithms take a vertex and go over its neighbours, and the adjacency list gives them in time proportional to their number.

Depth-first search (DFS) finds every vertex of a graph that can be reached from a start vertex. Run it from every vertex not yet reached, and it splits a graph or a grid into connected components. If you need the fewest edges to each vertex, use breadth-first search instead.

Breadth-first search (BFS) finds the fewest edges from one vertex to every other vertex of a graph in which every edge counts the same, such as flights between cities or moves in a maze. If the edges have different lengths, use Dijkstra's algorithm instead.

To split an undirected graph or a grid into connected components, start a search from every vertex that no earlier search has reached. This counts the components, measures their sizes and tells whether two vertices are in the same one, all in O(n + m). If the edges are added one by one between the questions, use a disjoint set union instead.

Flood fill paints every cell of a grid that can be reached from a given cell through side neighbours of the same colour. If you need the fewest moves between two cells, use BFS instead.

Cycle detection finds out whether a graph has a cycle, a path that comes back to the vertex it started from without using any edge twice, and prints one. It is a depth-first search with one extra check per edge, works for two-way and one-way edges, and runs in O(n + m) for $n$ vertices and $m$ edges. If you need a cycle whose edge lengths add up to a negative number, use Bellman–Ford instead.

Multi-source BFS finds, for every vertex of a graph or every cell of a grid, the fewest edges to the nearest of several sources, such as the nearest exit or the nearest burning cell. It is one breadth-first search whose queue (first in, first out) starts with all of them. If the edges have different lengths, use Dijkstra's algorithm with all sources at distance 0 instead.

A state graph is what you search when the position alone does not decide the next moves: you may carry a key, face a direction or hold some water in two jugs. Each vertex is a position together with that extra information, and BFS or Dijkstra's algorithm runs on it unchanged.

Topological sort puts the vertices of a directed graph in a row so that every edge goes from an earlier vertex to a later one, like tasks ordered so that each comes after the tasks it waits for. It runs in O(n + m) and tells you when a cycle makes such an order impossible. In a graph without cycles, the same order gives shortest and longest paths in one pass.

0-1 BFS finds the shortest distance from one vertex to every other vertex in a graph where each edge weighs 0 or 1, such as a map where some moves are free and others cost one step. If every edge weighs 1, plain BFS is enough; if the weights can be 2 or more, use Dijkstra's algorithm.

Dijkstra's algorithm finds the shortest distance from one vertex to every other vertex in a graph whose edges have lengths that are not negative, such as a map of roads. If every step costs the same, as in a maze, BFS is simpler; if some lengths are negative, use Bellman–Ford.

The Bellman–Ford algorithm finds the shortest distance from one vertex to every other vertex of a directed graph, even when some edges have negative weights. It also detects negative cycles, around which the distances keep dropping forever. If no weight is negative, Dijkstra's algorithm gives the same answers in O((n + m) \log m) instead of $O(nm)$.

SPFA (Shortest Path Faster Algorithm) finds the shortest distances from one vertex in a directed graph with negative edge weights, like Bellman–Ford, but it re-checks only the edges out of vertices whose distance has just dropped. It also detects negative cycles. Its worst case is still $O(nm)$, so if no weight is negative, use Dijkstra's algorithm instead.

The Floyd–Warshall algorithm finds the shortest distance between every pair of vertices of a weighted graph in O(n^3), so it fits graphs with up to a few hundred vertices. It allows negative edges and detects negative cycles. If you need the distances from one vertex only, use Dijkstra's algorithm or Bellman–Ford instead.

Kruskal's algorithm finds a minimum spanning tree of an undirected weighted graph: the cheapest set of edges that connects all its vertices. It works on a plain list of edges. Prim's algorithm builds the same tree by growing it from one vertex.

Prim's algorithm finds a minimum spanning tree of an undirected weighted graph: the cheapest set of edges that connects all its vertices. If you need the shortest routes from one vertex instead, use Dijkstra's algorithm.

A strongly connected component of a directed graph is a largest set of vertices in which every vertex can reach every other one. Shrinking each component to one vertex turns any directed graph into a graph without cycles, so problems about reachability or paths in graphs with cycles become topological sort or DP problems. Kosaraju's algorithm finds the components with two DFS passes in O(n + m). With two-way edges, plain connected components are enough.

A tree is a connected graph with no cycles, such as a company where every employee has exactly one boss. Rooting it at one vertex gives each vertex a parent, a depth and a subtree, and one depth-first search computes all three in $O(n)$, which answers questions such as how many people work under each boss. For a binary search tree, with a left and a right child per node, see binary search tree.

A graph is bipartite if its vertices can be coloured with two colours so that every edge joins two different colours. Breadth-first search checks this in O(n + m) by giving each newly reached vertex the colour opposite to the vertex it was reached from; when it fails, the graph has a cycle of odd length. To pair up the vertices of one colour with the vertices of the other, see maximum matching instead.