 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 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.