= Graph algorithm
A <graph algorithm> computes a property of a <graph> or constructs a related object from its <graph vertices> and <graph edges>. The <input> representation matters: an <adjacency list> lets an <algorithm> inspect the neighbours of one <graph vertex> without scanning every possible pair of <graph vertices>, whereas an <adjacency matrix> provides direct tests for individual <graph edges>.
For example, <breadth-first search> finds every <graph vertex> reachable from a starting <graph vertex> $s$. Mark $s$, place it in a <FIFO queue>, then repeatedly remove the oldest marked <graph vertex> and mark/enqueue each previously unmarked neighbour. A <graph vertex> is enqueued at most once, so scanning <adjacency lists> costs $O(|V|+|E|)$. The <FIFO queue> processes distance layers in order; the first discovery of a <graph vertex> supplies a shortest <graph path> in an unweighted <graph>.
For <graph edges> $a\!\to b$, $a\!\to c$, $b\!\to d$, starting at $a$ discovers $b,c$ before $d$, with distances $0,1,1,2$. The same <graph> can support different questions: <depth-first search> investigates traversal structure, <Dijkstra's algorithm> uses nonnegative <edge weight>[edge weights] for shortest <graph paths>, and a <minimum spanning tree> minimizes the total weight needed to connect an undirected <graph>. Matching the <algorithm> to its assumptions is part of modelling the problem.
Back to article page
