There are two standard ways to represent a graph *G* = (*V, E*): as a collection of adjacency lists or as an adjacency matrix. The adjacency-list representation is usually preferred, because it provides a compact way to represent * sparse* graphs--those for which |

The * adjacency-list representation* of a graph

Adjacency lists can readily be adapted to represent * weighted graphs*, that is, graphs for which each edge has an associated

For the * adjacency-matrix representation* of a graph

Observe the symmetry along the main diagonal of the adjacency matrix in Figure 23.1(c). We define the the **transpose**** **of a matrix *A* = (*a _{ij}*) to be the matrix given by . Since in an undirected graph, (

The * transpose* of a directed graph

Given an adjacency-list representation of a multigraph *G* = (*V, E*), describe an *O*(*V+E*)-time algorithm to compute the adjacency-list representation of the "equivalent" undirected graph *G**'* = (*V, E**'*), where *E**'* consists of the edges in *E* with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.

The * square* of a directed graph

When an adjacency-matrix representation is used, most graph algorithms require time (*V*^{2}), but there are some exceptions. Show that determining whether a directed graph contains a * sink*--a vertex with in-degree |

The * incidence matrix* of a directed graph

Describe what the entries of the matrix product *BB*^{T} represent, where *B*^{T }is the transpose of *B*.

* Breadth-first search* is one of the simplest algorithms for searching a graph and the archetype for many important graph algorithms. Dijkstra's single-source shortest-paths algorithm (Chapter 25) and Prim's minimum-spanning-tree algorithm (Section 24.2) use ideas similar to those in breadth-first search.

Given a graph *G* = (*V, E*) and a distinguished * source* vertex

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. Gray and black vertices, therefore, have been discovered, but breadth-first search distinguishes between them to ensure that the search proceeds in a breadth-first manner. If (

Breadth-first search constructs a breadth-first tree, initially containing only its root, which is the source vertex *s*. 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. We say that *u* is the * predecessor* or

The breadth-first-search procedure BFS below assumes that the input graph* G* = (*V, E*) is represented using adjacency lists. It maintains several additional data structures with each vertex in the graph. The color of each vertex *u* *V* is stored in the variable *color*[*u*], and the predecessor of *u* is stored in the variable [*u*]. If *u* has no predecessor (for example, if *u* = *s* or *u* has not been discovered), then [*u*] = NIL. The distance from the source s to vertex *u* computed by the algorithm is stored in *d*[*u*]*.* The algorithm also uses a first-in, first-out queue *Q* (see Section 11.1) to manage the set of gray vertices.

BFS(G,s)

1foreach vertexuV[G] - {s}

2docolor[u] WHITE

3d[u]

4 [u] NIL

5color[s] GRAY

6d[s] 0

7 [s] NIL

8Q{s}

9whileQ

10douhead[Q]

11foreachvAdj[u]

12do ifcolor[v] = WHITE

13thencolor[v] GRAY

14d[v]d[u] + 1

15 [v]u

16 ENQUEUE(Q,v)

17 DEQUEUE(Q)

18color[u] BLACK

Figure 23.3 illustrates the progress of BFS on a sample graph.

At the beginning of this section, we claimed that breadth-first search finds the distance to each reachable vertex in a graph *G* = (*V,E*) from a given source vertex *s* *V*. Define the * shortest-path distance* (

(s,v)(s,u) + 1 .

d[v] =d[u] + 1

(s,u) + 1

(s,v) .

We can now prove that breadth-first search correctly finds shortest-path distances.

if *v* *s*, then [*v*] is set to *u* for some *u* *V _{k}* - 1, and

*v* is inserted into the queue *Q*.

As we have noted before, there is certainly at most one such point.

The procedure BFS builds a breadth-first tree as it searches the graph, as illustrated in Figure 23.3. The tree is represented by the field in each vertex. More formally, for a graph *G* = (*V, E*) with source *s*, we define the * predecessor subgraph* of

V_{}_{ = {v V : [v] NIL} {s}}

E_{}_{ = {([v],v) E : v V}_{ }- {s}} .

The predecessor subgraph *G*_{} is a * breadth-first tree* if

PRINT-PATH(G,s,v)

1ifv=s

2thenprints

3else if[v] = NIL

4thenprint "no path from"s"to"v"exists"

5elsePRINT-PATH(G,s,[v])

6 printv

Give an efficient algorithm to determine if an undirected graph is bipartite.

The * diameter* of a tree

The strategy followed by depth-first search is, as its name implies, to search "deeper" in the graph whenever possible. In depth-first search, edges are explored out of the most recently discovered vertex *v* that still has unexplored edges leaving it. When all of *v*'s edges have been explored, the search "backtracks" to explore edges leaving the vertex from which *v* was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered vertices remain, then one of them is selected as a new source and the search is repeated from that source. This entire process is repeated until all vertices are discovered.

As in breadth-first search, whenever a vertex *v* is discovered during a scan of the adjacency list of an already discovered vertex *u*, depth-first search records this event by setting *v*'s predecessor field [*v*] to *u*. Unlike breadth-first search, whose predecessor subgraph forms a tree, the predecessor subgraph produced by a depth-first search may be composed of several trees, because the search may be repeated from multiple sources. The * predecessor subgraph* of a depth-first search is therefore defined slightly differently from that of a breadth-first search: we let

E_{}_{ = {([v], v) : v V and [v] NIL} .}

The predecessor subgraph of a depth-first search forms a * depth-first forest* composed of several

As in breadth-first search, vertices are colored during the search to indicate their state. Each vertex is initially white, is grayed when it is * discovered* in the search, and is blackened when it is

Besides creating a depth-first forest, depth-first search also * timestamps *each vertex. Each vertex

d[u] <f[u] .

Vertex *u* is WHITE before time *d*[*u*], GRAY between time *d*[*u*] and time *f*[*u*], and BLACK thereafter.

DFS(G)

1foreach vertexuV[G]

2docolor[u] WHITE

3 [u] NIL

4time0

5foreach vertexuV[G]

6do ifcolor[u] = WHITE

7thenDFS-VISIT(u)

Figure 23.4 illustrates the progress of DFS on the graph shown in Figure 23.2.

In each call DFS-VISIT(*u*), vertex *u* is initially white. Line 1 paints *u *gray, and line 2 records the discovery time *d*[*u*] by incrementing and saving the global variable *time*. Lines 3-6 examine each vertex *v* adjacent to *u* and recursively visit *v* if it is white. As each vertex *v* *Adj*[*u*] is considered in line 3, we say that edge (*u, v*) is * explored* by the depth-first search. Finally, after every edge leaving

In any depth-first search of a (directed or undirected) graph *G* = (*V, E*), for any two vertices *u* and *v*, exactly one of the following three conditions holds:

the intervals [*d*[*u*], â[*u*]] and [*d*[*v*], â[*v*]] are entirely disjoint,

The case in which *d*[*v*] < *d*[*u*] is similar, with the roles of *u* and *v *reversed in the above argument.

* Proof* Immediate from Theorem 23.6.

In a depth-first forest of a (directed or undirected) graph *G* = (*V, E*), vertex *v* is a descendant of vertex *u* if and only if at the time *d*[*u*] that the search discovers *u*, vertex *v* can be reached from *u* along a path consisting entirely of white vertices.

Another interesting property of depth-first search is that the search can be used to classify the edges of the input graph *G* = (*V, E*). This edge classification can be used to glean important information about a graph. For example, in the next section, we shall see that a directed graph is acyclic if and only if a depth-first search yields no "back" edges (Lemma 23.10).

1. * Tree edges* are edges in the depth-first forest

2. * Back edges* are those edges (

3. * Forward edges* are those nontree edges (

4. * Cross edges* are all other 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.

1. WHITE indicates a tree edge,

2. GRAY indicates a back edge, and

3. BLACK indicates a forward or cross edge.

We now show that forward and cross edges never occur in a depth-first search of an undirected graph.

We shall see many applications of these theorems in the following sections.

Show how depth-first search works on the graph of Figure 23.6. Assume that the **for** loop of lines 5-7 of the DFS procedure considers the vertices in alphabetical order, and assume that each adjacency list is ordered alphabetically. Show the discovery and finishing times for each vertex, and show the classification of each edge.

Show the parenthesis structure of the depth-first search shown in Figure 23.4.

* a. *a tree edge or forward edge if and only if

* b. *a back edge if and only if

* c. *a cross edge if and only if

Show that in an undirected graph, classifying an edge (*u, v*) as a tree edge or a back edge according to whether (*u,v*) or (*v,u*) is encountered first during the depth-first search is equivalent to classifying it according to the priority of types in the classification scheme.

Show that a depth-first search of an undirected graph *G* can be used to identify the connected components of *G,* and that the depth-first forest contains as many trees as *G *has connected components. More precisely, show how to modify depth-first search so that each vertex* v* is assigned an integer label *cc*[*v*] between 1 and *k,* where *k* is the number of connected components of *G,* such that *cc*[*u*]* = cc*[*v*] if and only if *u* and *v* are in the same connected component.

A directed graph *G = *(*V, E*) is * singly connected* if implies that there is at most one simple path from

This section shows how depth-first search can be used to perform topological sorts of directed acyclic graphs, or "dags" as they are sometimes called. A * topological sort* of a dag

The following simple algorithm topologically sorts a dag.

TOPOLOGICAL-SORT(G)

1 call DFS(G) to compute finishing timesf[v] for each vertexv

2 as each vertex is finished, insert it onto the front of a linked list

3returnthe linked list of vertices

A directed graph *G* is acyclic if and only if a depth-first search of *G* yields no back edges.

TOPOLOGICAL-SORT(*G*) produces a topological sort of a directed acyclic graph *G*.

Show the ordering of vertices produced by TOPOLOGICAL-SORT when it is run on the dag of Figure 23.8.

Give an algorithm that determines whether or not a given undirected graph *G* = (*V, E*) contains a cycle. Your algorithm should run in *O*(*V*) time, independent of |*E|.*

We now consider a classic application of depth-first search: decomposing a directed graph into its strongly connected components. This section shows how to do this decomposition using two depth-first searches. Many algorithms that work with directed graphs begin with such a decomposition; this approach often allows the original problem to be divided into subproblems, one for each strongly connected component. Combining the solutions to the subproblems follows the structure of connections between strongly connected components; this structure can be represented by a graph known as the "component" graph, defined in Exercise 23.5-4.

STRONGLY-CONNECTED-COMPONENTS(G)

1 call DFS(G) to compute finishing timesf[u] for each vertexu

2 computeG^{T}

3 call DFS(G^{T}), but in the main loop of DFS, consider the vertices

in order of decreasingf[u] (as computed in line 1)

4 output the vertices of each tree in the depth-first forest of step 3 as a

separate strongly connected component

To prove STRONGLY-CONNECTED-COMPONENTS correct, we introduce the notion of the **forefather*** *(*u*) of a vertex *u*, which is the vertex *w *reachable from *u* that finished last in the depth-first search of line l. In other words,

(*u*) = that vertex *w* such that and *f*[*w*] is maximized .

Note that (*u*) = *u* is possible because *u* is reachable from itself, and hence

f[u]f[(u)] .

We can also show that ((u)) = (u), by the following reasoning. For any vertices u, v V,

The first theorem justifies calling ø(*u*) a "forefather" of *u*.

* Proof* We have , by the definition of forefather, and since ø(

The following theorem gives a stronger result relating forefathers to strongly connected components.

The following theorem formalizes this argument.

C(r) = {vV: (v) =r}.

We now prove that a vertex *u *is placed in *T *if and only if *u * *C*(*r*).

How can the number of strongly connected components of a graph change if a new edge is added?

We denote the **component**** ****graph**** **of *G* = (*V*, *E*) by *G*^{SCC }= (*V*^{SCC}, *E*^{SCC}), where *V*^{SCC }contains one vertex for each strongly connected component of *G* and *E*^{SCC }contains the edge (*u*, *v*) if there is a directed edge from a vertex in the strongly connected component of *G *corresponding to *u* to a vertex in the strongly connected component of *G* corresponding to *v*. Figure 23.9(c) shows an example. Prove that *G*^{SCC }is a dag.

A directed graph *G* = (*V*, *E*) is said to be * semiconnected* if, for any two vertices

23-1 Classifying edges by breadth-first search

A depth-first forest classifies the edges of a graph into tree, back, forward, and cross edges. A breadth-first tree can also be used to classify the edges reachable from the source of the search into the same four categories.

**a****.** Prove that in a breadth-first search of an undirected graph, the following properties hold:

1. There are no back edges and no forward edges.

2. For each tree edge (*u*,*v*), we have *d*[*v*] = *d*[*u*] + 1.

3. For each cross edge (*u*,*v*), we have *d*[*v*] = *d*[*u*] or *d*[*v*] = *d*[*u*]* *+ 1.

**b****.** Prove that in a breadth-first search of a directed graph, the following properties hold:

1. There are no forward edges.

2. For each tree edge (*u*,*v*), we have *d*[*v*] = *d*[*u*] + 1.

3. For each cross edge (*u*,*v*), we have *d*[*v*] *d*[*u*] + 1.

4. For each back edge (*u*,*v*), we have 0 *d*[*v*] < *d*[*u*].

23-2 Articulation points, bridges, and biconnected components

Let *G* = (*V*, *E*) be a connected, undirected graph. An * articulation point *of

Show how to compute *low*[] for all vertices *V *in *O*(*E*) time.

**d****.** Show how to compute all articulation points in *O*(*E*) time.

**e****. **Prove that an edge of *G* is a bridge if and only if it does not lie on any simple cycle of *G*.

**f****.** Show how to compute all the bridges of *G* in *O*(*E*) time.

**g****.** Prove that the biconnected components of *G* partition the nonbridge edges of* G*.

An * Euler tour* of a connected, directed graph

**a****.** Show that *G* has an Euler tour if and only if

Even [65] and Tarjan [188] are excellent references for graph algorithms.