Graph Algorithms

A graph G = (V, E) is a set of vertices (nodes) V together with a set of edges E, where each edge connects a pair of vertices. Vertices model objects; edges model relationships between them.

The degree of a vertex is the number of edges incident to it (a self-loop usually counts twice). By the handshaking lemma, the sum of all degrees equals 2·|E|.

In a directed graph, the in-degree of a vertex is the number of edges pointing into it, and the out-degree is the number of edges leaving it. The sum of in-degrees equals the sum of out-degrees, both equal to |E|.

In an undirected graph an edge {u, v} is symmetric and traversable both ways. In a directed graph (digraph) an edge (u, v) is an ordered pair traversable only from u to v.

A weighted graph assigns a numeric weight (cost, length, or capacity) to each edge (or vertex). Many algorithms such as Dijkstra and MST operate on edge weights.

A multigraph permits multiple parallel edges between the same pair of vertices. A self-loop is an edge whose two endpoints are the same vertex.