📄 chap23.htm
字号:
<HTML><HEAD>
<TITLE>Intro to Algorithms: CHAPTER 23: ELEMENTARY GRAPH ALGORITHMS</TITLE></HEAD><BODY BGCOLOR="#FFFFFF">
<a href="chap24.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A>
<a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A>
<a href="partvi.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A>
<h1><a name="08a0_0001">CHAPTER 23: ELEMENTARY GRAPH ALGORITHMS<a name="08a0_0001"></h1><P>
This chapter presents methods for representing a graph and for searching a graph. Searching a graph means systematically following the edges of the graph so as to visit the vertices of the graph. A graph-searching algorithm can discover much about the structure of a graph. Many algorithms begin by searching their input graph to obtain this structural information. Other graph algorithms are organized as simple elaborations of basic graph-searching algorithms. Techniques for searching a graph are at the heart of the field of graph algorithms.<P>
Section 23.1 discusses the two most common computational representations of graphs: as adjacency lists and as adjacency matrices. Section 23.2 presents a simple graph-searching algorithm called breadth-first search and shows how to create a breadth-first tree. Section 23.3 presents depth-first search and proves some standard results about the order in which depth-first search visits vertices. Section 23.4 provides our first real application of depth-first search: topologically sorting a directed acyclic graph. A second application of depth-first search, finding the strongly connected components of a directed graph, is given in Section 23.5.<P>
<h1><a name="08a2_1736">23.1 Representations of graphs<a name="08a2_1736"></h1><P>
<a name="08a2_1727"><a name="08a2_1728"><a name="08a2_1729"><a name="08a2_172a">There are two standard ways to represent a graph <I>G</I> = (<I>V, E</I>): 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 <I><B>sparse</I></B> graphs--those for which |<I>E</I>| is much less than |<I>V|<SUP></I>2</SUP>. Most of the graph algorithms presented in this book assume that an input graph is represented in adjacency-list form. An adjacency-matrix representation may be preferred, however, when the graph is <I><B>dense</I></B><FONT FACE="CG Times (W1)" SIZE=2>--</FONT>|<I>E|</I> is close to |<I>V|<SUP></I>2 </SUP>-- or when we need to be able to tell quickly if there is an edge connecting two given vertices. For example, two of the all-pairs shortest-paths algorithms presented in Chapter 26 assume that their input graphs are represented by adjacency matrices.<P>
<a name="08a2_172b"><a name="08a2_172c">The <I><B>adjacency-list representation</I></B> of a graph <I>G</I> = (<I>V, E</I>) consists of an array <I>Adj</I> of <I>|V|</I> lists, one for each vertex in <I>V.</I> For each <I>u </I><img src="../images/memof12.gif"><I> V,</I> the adjacency list <I>Adj</I>[<I>u</I>] contains (pointers to) all the vertices <I>v</I> such that there is an edge (<I>u,v</I>) <img src="../images/memof12.gif"> <I>E</I>. That is, <I>Adj</I>[<I>u</I>] consists of all the vertices adjacent to <I>u</I> in <I>G</I>. The vertices in each adjacency list are typically stored in an arbitrary order. Figure 23.1(b) is an adjacency-list representation of the undirected graph in Figure 23.1(a). Similarly, Figure 23.2(b) is an adjacency-list representation of the directed graph in Figure 23.2(a).<P>
<img src="466_a.gif"><P>
<h4><a name="08a2_1737">Figure 23.1 Two representations of an undirected graph. (a) An undirected graph G having five vertices and seven edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G.<a name="08a2_1737"></sub></sup></h4><P>
<img src="466_b.gif"><P>
<h4><a name="08a2_1738">Figure 23.2 Two representations of a directed graph. (a) A directed graph G having six vertices and eight edges. (b) An adjacency-list representation of G. (c) The adjacency-matrix representation of G.<a name="08a2_1738"></sub></sup></h4><P>
If <I>G</I> is a directed graph, the sum of the lengths of all the adjacency lists is |<I>E|</I>, since an edge of the form (<I>u,v</I>) is represented by having <I>v</I> appear in <I>Adj</I>[<I>u</I>]. If <I>G</I> is an undirected graph, the sum of the lengths of all the adjacency lists is 2|<I>E|</I>, since if (<I>u,v</I>) is an undirected edge, then <I>u</I> appears in <I>v</I>'s adjacency list and vice versa. Whether a graph is directed or not, the adjacency-list representation has the desirable property that the amount of memory it requires is <I>O</I>(max(<I>V, E</I>)) <I>= O</I>(<I>V + E</I>).<P>
<a name="08a2_172d"><a name="08a2_172e"><a name="08a2_172f"><a name="08a2_1730">Adjacency lists can readily be adapted to represent <I><B>weighted graphs</I></B>, that is, graphs for which each edge has an associated <I><B>weight</I></B>, typically given by a<I><B> weight function</I></B><I> w </I>: <I>E</I> <img src="../images/arrow12.gif"> <B>R</B>. For example, let <I>G</I> = (<I>V, E</I>) be a weighted graph with weight function <I>w</I>. The weight <I>w</I>(<I>u,v</I>) of the edge (<I>u,v</I>) <img src="../images/memof12.gif"> <I>E</I> is simply stored with vertex <I>v</I> in <I>u</I>'s adjacency list. The adjacency-list representation is quite robust in that it can be modified to support many other graph variants.<P>
A potential disadvantage of the adjacency-list representation is that there is no quicker way to determine if a given edge (<I>u,v</I>) is present in the graph than to search for <I>v</I> in the adjacency list <I>Adj</I>[<I>u</I>]. This disadvantage can be remedied by an adjacency-matrix re presentation of the graph, at the cost of using asymptotically more memory.<P>
<a name="08a2_1731"><a name="08a2_1732"><a name="08a2_1733">For the <I><B>adjacency-matrix representation</I></B> of a graph <I>G</I> = (<I>V, E</I>), we assume that the vertices are numbered 1, 2, . . . , |<I>V|</I> in some arbitrary manner. The adjacency-matrix representation of a graph <I>G</I> then consists of a |<I>V| <img src="../images/mult.gif"> |V|</I> matrix <I>A = </I>(<I>a<SUB>ij</I></SUB>) such that<P>
<img src="467_a.gif"><P>
Figures 23.1(c) and 23.2(c) are the adjacency matrices of the undirected and directed graphs in Figures 23.1(a) and 23.2(a), respectively. The adjacency matrix of a graph requires <img src="../images/bound.gif">(<I>V</I><SUP>2</SUP>) memory, independent of the number of edges in the graph.<P>
<a name="08a2_1734"><a name="08a2_1735">Observe the symmetry along the main diagonal of the adjacency matrix in Figure 23.1(c). We define the the <I><B>transpose</I> </B>of a matrix <I>A</I> = (<I>a<SUB>ij</I></SUB>) to be the matrix <img src="467_b.gif"> given by <img src="467_c.gif">. Since in an undirected graph, (<I>u,v</I>) and (<I>v,u</I>) represent the same edge, the adjacency matrix <I>A</I> of an undirected graph is its own transpose: <I>A = A</I><SUP>T</SUP>. In some applications, it pays to store only the entries on and above the diagonal of the adjacency matrix, thereby cutting the memory needed to store the graph almost in half.<P>
Like the adjacency-list representation of a graph, the adjacency-matrix representation can be used for weighted graphs. For example, if <I>G</I> = (<I>V, E</I>) is a weighted graph with edge-weight function <I>w</I>, the weight <I>w</I>(<I>u, v</I>) of the edge (<I>u,v</I>) <img src="../images/memof12.gif"> <I>E</I> is simply stored as the entry in row <I>u</I> and column <I>v </I>of the adjacency matrix. If an edge does not exist, a <FONT FACE="Courier New" SIZE=2>NIL</FONT> value can be stored as its corresponding matrix entry, though for many problems it is convenient to use a value such as 0 or <img src="../images/infin.gif">.<P>
Although the adjacency-list representation is asymptotically at least as efficient as the adjacency-matrix representation, the simplicity of an adjacency matrix may make it preferable when graphs are reasonably small. Moreover, if the graph is unweighted, there is an additional advantage in storage for the adjacency-matrix representation. Rather than using one word of computer memory for each matrix entry, the adjacency matrix uses only one bit per entry.<P>
<h2><a name="08a3_1740">Exercises<a name="08a3_1740"></h2><P>
<a name="08a3_1741">23.1-1<a name="08a3_1741"><P>
Given an adjacency-list representation of a directed graph, how long does it take to compute the out-degree of every vertex? How long does it take to compute the in-degrees?<P>
<a name="08a3_1742">23.1-2<a name="08a3_1742"><P>
Give an adjacency-list representation for a complete binary tree on 7 vertices. Give an equivalent adjacency-matrix representation. Assume that vertices are numbered from 1 to 7 as in a binary heap.<P>
<a name="08a3_1743">23.1-3<a name="08a3_1743"><P>
<a name="08a3_1736"><a name="08a3_1737">The <I><B>transpose</I></B> of a directed graph <I>G</I> = (<I>V, E</I>) is the graph <I>G</I><SUP>T</SUP> = (<I>V</I>, <I>E</I><SUP>T</SUP>), where <I>E</I><SUP>T</SUP> = {(<I>v,u</I>) <img src="../images/memof12.gif"> <I>V</I> <img src="../images/mult.gif"><I> V </I>: (<I>u,v</I>) <img src="../images/memof12.gif"> <I>E</I>}. Thus, <I>G</I><SUP>T</SUP> is <I>G</I> with all its edges reversed. Describe efficient algorithms for computing <I>G</I><SUP>T</SUP> from <I>G</I>, for both the adjacency-list and adjacency-matrix representations of <I>G</I>. Analyze the running times of your algorithms.<P>
<a name="08a3_1744">23.1-4<a name="08a3_1744"><P>
<a name="08a3_1738"><a name="08a3_1739">Given an adjacency-list representation of a multigraph <I>G</I> = (<I>V, E</I>), describe an <I>O</I>(<I>V+E</I>)-time algorithm to compute the adjacency-list representation of the "equivalent" undirected graph <I>G</I><I>'</I> = (<I>V, E</I><I>'</I>), where <I>E</I><I>'</I> consists of the edges in <I>E</I> with all multiple edges between two vertices replaced by a single edge and with all self-loops removed.<P>
<a name="08a3_1745">23.1-5<a name="08a3_1745"><P>
<a name="08a3_173a"><a name="08a3_173b">The <I><B>square</I></B> of a directed graph <I>G</I> = (<I>V, E</I>) is the graph <I>G<SUP>2</I></SUP> = (<I>V, E</I><SUP>2</SUP>) such that (<I>u,w</I>) <img src="../images/memof12.gif"> <I>E</I><SUP>2</SUP> if and only if for some <I>v </I><img src="../images/memof12.gif"><I> V</I>, both (<I>u,v</I>) <img src="../images/memof12.gif"> <I>E</I> and (<I>v,w</I>) <img src="../images/memof12.gif"> <I>E.</I> That is,<I> G</I><SUP>2</SUP> contains an edge between <I>u</I> and <I>w</I> whenever <I>G</I> contains a path with exactly two edges between <I>u</I> and <I>w</I>. Describe efficient algorithms for computing <I>G</I><SUP>2</SUP> from <I>G </I>for both the adjacency-list and adjacency-matrix representations of <I>G</I>. Analyze the running times of your algorithms.<P>
<a name="08a3_1746">23.1-6<a name="08a3_1746"><P>
<a name="08a3_173c">When an adjacency-matrix representation is used, most graph algorithms require time <img src="../images/bound.gif">(<I>V</I><SUP>2</SUP>), but there are some exceptions. Show that determining whether a directed graph contains a <I><B>sink</I></B>--a vertex with in-degree |<I>V|</I> - 1 and out-degree 0--can be determined in time <I>O</I>(<I>V</I>), even if an adjacency-matrix representation is used.<P>
<a name="08a3_1747">23.1-7<a name="08a3_1747"><P>
<a name="08a3_173d"><a name="08a3_173e"><a name="08a3_173f">The <I><B>incidence matrix</I></B> of a directed graph <I>G</I> = (<I>V, E</I>) is a |<I>V| <img src="../images/mult.gif"> |</I>E| matrix <I>B</I> = (<I>b<SUB>ij</I></SUB>) such that<P>
<img src="469_a.gif"><P>
Describe what the entries of the matrix product <I>BB</I><SUP>T</SUP> represent, where <I>B</I><SUP>T </SUP>is the transpose of <I>B</I>.<P>
<P>
<P>
<h1><a name="08a4_174d">23.2 Breadth-first search<a name="08a4_174d"></h1><P>
<a name="08a4_1740"><a name="08a4_1741"><I><B>Breadth-first search</I></B> 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.<P>
<a name="08a4_1742"><a name="08a4_1743"><a name="08a4_1744">Given a graph <I>G</I> = (<I>V, E</I>) and a distinguished <I><B>source</I></B> vertex <I>s</I>, breadth-first search systematically explores the edges of <I>G</I> to "discover" every vertex that is reachable from <I>s</I>. It computes the distance (fewest number of edges) from <I>s</I> to all such reachable vertices. It also produces a "breadth-first tree" with root <I>s</I> that contains all such reachable vertices. For any vertex <I>v</I> reachable from <I>s</I>, the path in the breadth-first tree from <I>s</I> to <I>v</I> corresponds to a "shortest path" from <I>s</I> to <I>v</I> in <I>G</I>, that is, a path containing the fewest number of edges. The algorithm works on both directed and undirected graphs.<P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -