Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 101
Текст из файла (страница 101)
The adjacency-listrepresentation is quite robust in that it can be modified to support many other graph variants.A potential disadvantage of the adjacency-list representation is that there is no quicker way todetermine if a given edge (u, v) is present in the graph than to search for v in the adjacency listAdj[u]. This disadvantage can be remedied by an adjacency-matrix representation of thegraph, at the cost of using asymptotically more memory.
(See Exercise 22.1-8 for suggestionsof variations on adjacency lists that permit faster edge lookup.)For the adjacency-matrix representation of a graph G = (V, E), we assume that the verticesare numbered 1, 2,..., |V| in some arbitrary manner. Then the adjacency-matrix representationof a graph G consists of a |V| × |V| matrix A = (aij) such thatFigures 22.1(c) and 22.2(c) are the adjacency matrices of the undirected and directed graphsin Figures 22.1(a) and 22.2(a), respectively.
The adjacency matrix of a graph requires Θ(V2)memory, independent of the number of edges in the graph.Observe the symmetry along the main diagonal of the adjacency matrix in Figure 22.1(c). Wedefine the transpose of a matrix A = (aij) to be the matrixgiven by. Since in anundirected graph, (u, v) and (v, u) represent the same edge, the adjacency matrix A of anundirected graph is its own transpose: A = AT. In some applications, it pays to store only theentries on and above the diagonal of the adjacency matrix, thereby cutting the memory neededto store the graph almost in half.Like the adjacency-list representation of a graph, the adjacency-matrix representation can beused for weighted graphs. For example, if G = (V, E) is a weighted graph with edge-weightfunction w, the weight w(u, v) of the edge (u, v) E is simply stored as the entry in row u andcolumn v of the adjacency matrix.
If an edge does not exist, a NIL value can be stored as itscorresponding matrix entry, though for many problems it is convenient to use a value such as0 or ∞.Although the adjacency-list representation is asymptotically at least as efficient as theadjacency-matrix representation, the simplicity of an adjacency matrix may make it preferablewhen graphs are reasonably small.
Moreover, if the graph is unweighted, there is an additionaladvantage in storage for the adjacency-matrix representation. Rather than using one word ofcomputer memory for each matrix entry, the adjacency matrix uses only one bit per entry.Exercises 22.1-1Given an adjacency-list representation of a directed graph, how long does it take to computethe out-degree of every vertex? How long does it take to compute the in-degrees?Exercises 22.1-2Give an adjacency-list representation for a complete binary tree on 7 vertices.
Give anequivalent adjacency-matrix representation. Assume that vertices are numbered from 1 to 7 asin a binary heap.Exercises 22.1-3The transpose of a directed graph G = (V, E) is the graph GT = (V, ET), where ET = {(v, u)V × V : (u, v) E}. Thus, GT is G with all its edges reversed. Describe efficient algorithms forcomputing GT from G, for both the adjacency-list and adjacency-matrix representations of G.Analyze the running times of your algorithms.Exercises 22.1-4Given an adjacency-list representation of a multigraph G = (V, E), describe an O(V + E)-timealgorithm 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 verticesreplaced by a single edge and with all self-loops removed.Exercises 22.1-5The square of a directed graph G = (V, E) is the graph G2 = (V, E2) such that (u, w) E2 ifand only if for some v V , both (u, v) E and (v, w) E.
That is, G2 contains an edgebetween u and w whenever G contains a path with exactly two edges between u and w.Describe efficient algorithms for computing G2 from G for both the adjacency-list andadjacency-matrix representations of G. Analyze the running times of your algorithms.Exercises 22.1-6When an adjacency-matrix representation is used, most graph algorithms require time Ω(V2),but there are some exceptions.
Show that determining whether a directed graph G contains auniversal sink-a vertex with in-degree |V| - 1 and out-degree 0-can be determined in timeO(V), given an adjacency matrix for G.Exercises 22.1-7The incidence matrix of a directed graph G = (V, E) is a |V| × |E| matrix B = (bij) such thatDescribe what the entries of the matrix product B BT represent, where BT is the transpose of B.Exercises 22.1-8Suppose that instead of a linked list, each array entry Adj[u] is a hash table containing thevertices v for which (u, v) E.
If all edge lookups are equally likely, what is the expectedtime to determine whether an edge is in the graph? What disadvantages does this schemehave? Suggest an alternate data structure for each edge list that solves these problems. Doesyour alternative have disadvantages compared to the hash table?22.2 Breadth-first searchBreadth-first search is one of the simplest algorithms for searching a graph and the archetypefor many important graph algorithms. Prim's minimum-spanning-tree algorithm (Section23.2) and Dijkstra's single-source shortest-paths algorithm (Section 24.3) use ideas similar tothose in breadth-first search.Given a graph G = (V, E) and a distinguished source vertex s, breadth-first searchsystematically explores the edges of G to "discover" every vertex that is reachable from s.
Itcomputes the distance (smallest number of edges) from s to each reachable vertex. It alsoproduces a "breadth-first tree" with root s that contains all reachable vertices. For any vertex vreachable 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. The algorithm workson both directed and undirected graphs.Breadth-first search is so named because it expands the frontier between discovered andundiscovered vertices uniformly across the breadth of the frontier. That is, the algorithmdiscovers all vertices at distance k from s before discovering any vertices at distance k + 1.To keep track of progress, breadth-first search colors each vertex white, gray, or black.
Allvertices start out white and may later become gray and then black. A vertex is discovered thefirst time it is encountered during the search, at which time it becomes nonwhite. Gray andblack vertices, therefore, have been discovered, but breadth-first search distinguishes betweenthem to ensure that the search proceeds in a breadth-first manner.
If (u, v) E and vertex u isblack, then vertex v is either gray or black; that is, all vertices adjacent to black vertices havebeen discovered. Gray vertices may have some adjacent white vertices; they represent thefrontier between discovered and undiscovered vertices.Breadth-first search constructs a breadth-first tree, initially containing only its root, which isthe source vertex s.
Whenever a white vertex v is discovered in the course of scanning theadjacency list of an already discovered vertex u, the vertex v and the edge (u, v) are added tothe tree. We say that u is the predecessor or parent of v in the breadth-first tree. Since a vertexis discovered at most once, it has at most one parent. Ancestor and descendant relationships inthe breadth-first tree are defined relative to the root s as usual: if u is on a path in the tree fromthe root s to vertex v, then u is an ancestor of v and v is a descendant of u.The breadth-first-search procedure BFS below assumes that the input graph G = (V, E) isrepresented using adjacency lists.
It maintains several additional data structures with eachvertex in the graph. The color of each vertex u V is stored in the variable color[u], and thepredecessor of u is stored in the variable π[u]. If u has no predecessor (for example, if u = s oru has not been discovered), then π[u] = NIL. The distance from the source s to vertex ucomputed by the algorithm is stored in d[u]. The algorithm also uses a first-in, first-out queueQ (see Section 10.1) to manage the set of gray vertices.BFS(G, s)1 for each vertex uV [G] - {s}2do color[u] ← WHITE3d[u] ← ∞4π[u] ← NIL5 color[s] ← GRAY6 d[s] ← 07 π[s] ← NIL8 Q ← Ø9 ENQUEUE(Q, s)10 while Q ≠ Ø11do u ← DEQUEUE(Q)12for each vAdj[u]13do if color[v] = WHITE14then color[v] ← GRAY15d[v] ← d[u] + 116π[v] ← u17ENQUEUE(Q, v)18color[u] ← BLACKFigure 22.3 illustrates the progress of BFS on a sample graph.Figure 22.3: The operation of BFS on an undirected graph.
Tree edges are shown shaded asthey are produced by BFS. Within each vertex u is shown d[u]. The queue Q is shown at thebeginning of each iteration of the while loop of lines 10-18. Vertex distances are shown nextto vertices in the queue.The procedure BFS works as follows. Lines 1-4 paint every vertex white, set d[u] to beinfinity for each vertex u, and set the parent of every vertex to be NIL.Line 5 paints the sourcevertex s gray, since it is considered to be discovered when the procedure begins. Line 6initializes d[s] to 0, and line 7 sets the predecessor of the source to be NIL.
Lines 8-9 initializeQ to the queue containing just the vertex s.The while loop of lines 10-18 iterates as long as there remain gray vertices, which arediscovered vertices that have not yet had their adjacency lists fully examined. This while loopmaintains the following invariant:•At the test in line 10, the queue Q consists of the set of gray vertices.Although we won't use this loop invariant to prove correctness, it is easy to see that it holdsprior to the first iteration and that each iteration of the loop maintains the invariant. Prior tothe first iteration, the only gray vertex, and the only vertex in Q, is the source vertex s. Line11 determines the gray vertex u at the head of the queue Q and removes it from Q. The forloop of lines 12-17 considers each vertex v in the adjacency list of u.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
