Student Center | Instructor's Center | Introduction to Algorithms | Home

Introduction to Algorithms, 2/e

Thomas H. Cormen, Dartmouth College
Charles E. Leiserson, Massachusetts Institute of Technology
Ronald L. Rivest, Massachusetts Institute of Technology
Clifford Stein, Columbia University

Elementary Graph Algorithms

Glossary

sparse	There are two standard ways to represent a graph G = (V, E). Sparse graphs are those for which \|E\| is much less than \|V\|². (See page 527)



dense	There are two standard ways to represent a graph G = (V, E). When a graph is dense, \|E\| is close to \|V\|². (See page 527)



adjacency-list representation	of a graph G = (V, E) consists of an array Adj of \|V\| lists, one for each vertex in V. For each u ∈ V, the adjacency list Adj[u] contains all the vertices v such that there is an edge (u, v) ∈ E. That is, Adj[u] consists of all the vertices adjacent to u in G. (Alternatively, it may contain pointers to these vertices.) The vertices in each adjacency list are typically stored in an arbitrary order. (See page 528)



weighted graphs	graphs for which each edge has an associated weight, typically given by a weight function w : E → R. (See page 529)



adjacency-matrix representation	For this representation of a graph G = (V, E), we assume that the vertices are numbered 1, 2, . . . , \|V\| in some arbitrary manner. So the representation of a graph G consists of a \|V\| x \|V\| matrix A = (a_ij) such that . (See page 529)



transpose	The transpose of a matrix A = (a_ij) is the matrix A^T = (a_ij^T) given by a_ij^T = a_ji. Since in an undirected graph, (u, v) and (v, u) represent the same edge, the adjacency matrix A of an undirected graph is its own transpose: A = A^T. (See page 529)



square	of a directed graph G = (V, E) is the graph G² = (V, E²) such that (u, w) ∈ E² if and only if for some v ∈ V, both (u, v) ∈ E and (v, w) ∈ E. That is, G² contains an edge between u and w whenever G contains a path with exactly two edges between u and w. (See page 530)



universal sink	a vertex with in-degree \|V\| - 1 and out-degree 0 (See page 530)



breadth-first search	one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Given a graph G = (V, E) and a distinguished source vertex s, breadth-first search systematically explores the edges of G to "discover" every vertex that is reachable from s. It computes the distance (smallest number of edges) from s to each reachable vertex. It also produces a "breadth-first tree" with root s that contains all reachable vertices. For any vertex v reachable from s, the path in the breadth-first tree from s to v corresponds to a "shortest path" from s to v in G, that is, a path containing the smallest number of edges. Breadth-first search is so named because it expands the frontier between discovered and undiscovered vertices uniformly across the breadth of the frontier. That is, the algorithm discovers all vertices at distance k from s before discovering any vertices at distance k + 1. (See page 531)



discovered	To keep track of progress, breadth-first search colors each vertex white, gray, or black. All vertices start out white and may later become gray and then black. A vertex is discovered the first time it is encountered during the search, at which time it becomes nonwhite. (See page 531)



predecessor or parent	Whenever a white vertex v is discovered in the course of scanning the adjacency list of an already discovered vertex u, the vertex v and the edge (u, v) are added to the tree. Since a vertex is discovered at most once, it has at most one parent. (See page 532)



shortest-path distance	δ(s, v) from s to v is the minimum number of edges in any path from vertex s to vertex v; if there is no path from s to v, then δ(s, v) = ∞. (See page 534)



shortest path	A path of length δ(s, v) from s to v is said to be a shortest path from s to v. (See page 535)



predecessor subgraph	The predecessor subgraph for a breadth-first search, G is defined as G_π = (V_π, E_π), where V_π = {v ∈ V : π[v] ≠ NIL} ∪ {s} and E_π = {(π[v], v) : v ∈ V_π - {s}}. The predecessor subgraph of a depth-first search is defined slightly differently from that of a breadth-first search: let G_π = (V, E_π), where E_π = (V, E_π = {(Π[v], v) : v ∈ V and Π[v] ≠ NIL}. The predecessor subgraph of a depth-first search forms a depth-first forest composed of several depth-first trees. (See page 537, 540)



breadth-first tree	The predecessor subgraph G_Π is a breadth-first tree if V_Π consists of the vertices reachable from s and, for all v ∈ V_Π, there is a unique simple path from s to v in G_Π that is also a shortest path from s to v in G. A breadth-first tree is in fact a tree, since it is connected and \|E_Π\| = \|V_Π\| - 1. (See page 538)



tree edges	in a breadth-first tree, the edges in E_π. In a depth-first forest G_π, edge (u, v) is a tree edge if v was first discovered by exploring edge (u, v). (See page 538, 546)



finished	In a predecessor subgraph, each vertex is initially white, is grayed when it is discovered in the search, and is blackened when it is finished, that is, when its adjacency list has been examined completely. (See page 540)



timestamps	Besides creating a depth-first forest, depth-first search also timestamps each vertex. Each vertex v has two timestamps: the first timestamp d[v] records when v is first discovered (and grayed), and the second timestamp f[v] records when the search finishes examining v's adjacency list (and blackens v). (See page 541)



explored	As each vertex v ∈ Adj[u] is considered in DFS-VISIT line 4, we say that edge (u, v) is explored by the depth-first search. (See page 542)



parenthesis structure	Another important property of depth-first search is that discovery and finishing times have parenthesis structure. If we represent the discovery of vertex u with a left parenthesis "(u" and represent its finishing by a right parenthesis "u)", then the history of discoveries and finishings makes a well-formed expression in the sense that the parentheses are properly nested. (See page 543)



back edges	are those edges (u, v) connecting a vertex u to an ancestor v in a depth-first tree. Self-loops, which may occur in directed graphs, are considered to be back edges. (See page 546)



forward edges	are those nontree edges (u, v) connecting a vertex u to a descendant v in a depth-first tree. (See page 546)



cross edges	are all other edges (not tree, back, or forward edges). They can go between vertices in the same depth-first tree, as long as one vertex is not an ancestor of the other, or they can go between vertices in different depth-first trees. (See page 546)



biconnected component	G = (V, E) is a connected, undirected graph. A biconnected component of G is a maximal set of edges such that any two edges in the set lie on a common simple cycle. (See page 558)



articulated point	An articulated point of G is a vertex whose removal disconnects G, where G = (V, E) is a connected, undirected graph. (See page 558)



bridge	G = (V, E) is a connected, undirected graph. A bridge of G is an edge whose removal disconnects G. (See page 558)



Euler tour	An Euler tour of a connected, directed graph G = (V, E) is a cycle that traverses each edge of G exactly once, although it may visit a vertex more than once. (See page 559)

2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.