數(shù)據(jù)結(jié)構(gòu)第七章

1、Chapter 7 Graph1. Definitions of graph2. Representation of Graphs Adjacency Matrix Adjacency Lists Adjacency Multilists3. Graph traverse Breadth-first search Depth-First Search4. Minimum Spanning Tree5. Shortest Path 6. Topological Sort7. Critical Path共一百八十九頁(yè)課時(shí)(ksh)安排 6學(xué)時(shí)教學(xué)內(nèi)容： 圖的基本概念；圖的存儲(chǔ)結(jié)構(gòu)；圖的遍歷；最小生

2、成(shn chn)樹(shù)；最短路徑；拓?fù)渑判蚝完P(guān)鍵路徑； 要求學(xué)生掌握： 1、熟悉圖的各種存儲(chǔ)結(jié)構(gòu)，了解實(shí)際問(wèn)題與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系；2、遍歷圖的遞歸和非遞歸算法；3、應(yīng)用圖的遍歷算法求各種簡(jiǎn)單路徑問(wèn)題，比如，最小生成樹(shù)最短路徑拓?fù)渑判蜿P(guān)鍵路徑等。教學(xué)重點(diǎn)及難點(diǎn)： 圖的各種存儲(chǔ)結(jié)構(gòu)，圖的遍歷算法，構(gòu)造最小生成樹(shù)的算法。 共一百八十九頁(yè)1 Definitions of Graph G( V, E ) where G := graph, V = V( G ) := finite nonempty set of vertices, and E = E( G ) := finite set

3、 of edges. Undirected graph: ( vi , vj ) = ( vj , vi ) := the same edge. Directed graph (digraph): := vivjtailhead Restrictions : (1) Self loop is illegal. (2) Multigraph is not considered01012 Complete graph: a graph that has the maximum number of edges021302131/7共一百八十九頁(yè)vivj vi and vj are adjacent

4、; ( vi , vj ) is incident on vi and vj vivj vi is adjacent to vj ; vj is adjacent from vi ; is incident on vi and vj Subgraph G G := V( G ) V( G ) & E( G ) E( G ) Path ( G) from vp to vq := vp, vi1, vi2, , vin, vq such that ( vp, vi1 ), ( vi1, vi2 ), , ( vin, vq ) or , , belong to E( G ) Length of a

5、 path := number of edges on the path Simple path := vi1, vi2, , vin are distinct Cycle := simple path with vp = vq vi and vj in an undirected G are connected if there is a path from vi to vj (and hence there is also a path from vj to vi) An undirected graph G is connected if every pair of distinct v

6、i and vj are connected2/7共一百八十九頁(yè) (Connected) Component of an undirected G := the maximal connected subgraph A tree := a graph that is connected and acyclic Strongly connected directed graph G := for every pair of vi and vj in V( G ), there exist directed paths from vi to vj and from vj to vi. If the

7、 graph is connected without direction to the edges, then it is said to be weakly connected Strongly connected component := the maximal subgraph that is strongly connected Degree( v ) := number of edges incident to v. For a directed G, we have in-degree and out-degree. For example:vin-degree(v) = 3;

8、out-degree(v) = 1; degree(v) = 4 Given G with n vertices and e edges, then A DAG := a directed acyclic graph3/7共一百八十九頁(yè) 圖是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu) G = (V , VR )其中， VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱(chēng) v 為弧尾，w 為弧頭。 謂詞 P(v,w) 定義了弧 的意義(yy)或信息一、圖的結(jié)構(gòu)(jigu)定義:共一百八十九頁(yè) 由于“弧”是有方向的，因此(ync)稱(chēng)由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。 AB E

9、 C D例如(lr):G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 共一百八十九頁(yè) 若VR 必有VR,即VR是對(duì)稱(chēng)的，則以無(wú)序?qū)?v,w) 代替(dit)這兩個(gè)有序?qū)Γ硎卷旤c(diǎn)v 和頂點(diǎn)w 之間的一條邊。 B CA D F E 由頂點(diǎn)集和邊集構(gòu)成(guchng)的圖稱(chēng)作無(wú)向圖。例如: G2=(V2,VR2)V2=A, B, C, D, E, FVR2=( A,B ), ( A,E ), ( B,E ), ( C,D ), ( D,F ), ( B,F ), ( C,F ) 共一百八十九頁(yè)名詞(mng c)和術(shù)語(yǔ)網(wǎng)、子圖 完全(wnqun)圖、稀

10、疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹(shù)、生成森林共一百八十九頁(yè)ABECF1597211132 有時(shí)圖的邊或弧具有與它相關(guān)的數(shù)，這種與圖的邊或弧相關(guān)的數(shù)叫做權(quán)。這些權(quán)可以表示從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的距離或耗費(fèi)(hofi)。 弧或邊帶權(quán)的圖分別稱(chēng)為網(wǎng)(有向網(wǎng)、無(wú)向網(wǎng))。共一百八十九頁(yè)AEFBBC假設(shè)有兩個(gè)(lin )圖 G=(V,VR) 和 G=(V,VR)如果 VV, VRVR，則稱(chēng) G 為 G 的子圖。ABECF圖 G圖 G共一百八十九頁(yè)假設(shè)(jish)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 含有(hn yu) e=n(n-1

11、)/2 條邊的無(wú)向圖稱(chēng)作完全圖；含有 e=n(n-1) 條弧的有向圖稱(chēng)作 有向完全圖 若邊或弧的個(gè)數(shù) enlogn，則稱(chēng)作稀疏圖， 否則稱(chēng)作稠密圖。共一百八十九頁(yè) 假若頂點(diǎn)(dngdin)v 和頂點(diǎn)w 之間存在一條邊，則稱(chēng)頂點(diǎn)v 和w 互為鄰接點(diǎn)；例如(lr):ID(B) = 3ID(A) = 2 邊(v,w) 和頂點(diǎn)v 和w 相關(guān)聯(lián)； 和頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目定義為頂點(diǎn)v的度。ACDFEB共一百八十九頁(yè)對(duì)有向圖來(lái)說(shuō)，頂點(diǎn)(dngdin)的出度: 以頂點(diǎn)v為弧尾的弧的數(shù)目；頂點(diǎn)(dngdin)的入度: 以頂點(diǎn)v為弧頭的弧的數(shù)目。頂點(diǎn)的度(TD)=出度(OD)+入度(ID)ABECF例如:ID(

12、B) = 2OD(B) = 1TD(B) = 3共一百八十九頁(yè)設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列(xli) u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱(chēng)從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑。路徑上邊的數(shù)目稱(chēng)作路徑長(zhǎng)度。ABECF如:長(zhǎng)度(chngd)為3的路徑A,B,C,F簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑?；芈?序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。共一百八十九頁(yè) 若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通(xingtng)，則稱(chēng)此圖為連通圖；否則，稱(chēng)之為非連通圖。BACDFEBACDFE連通(lintng)圖非連通圖共一百八十九頁(yè) 若無(wú)向(w

13、 xin)圖為非連通圖，則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通分量。BACDFECDFBAE共一百八十九頁(yè) 若任意(rny)兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖。ABECFABECF對(duì)有向圖，強(qiáng)連通(lintng)圖共一百八十九頁(yè)ABECF否則(fuz)，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量。BCFAE共一百八十九頁(yè) 假設(shè)一個(gè)連通圖有 n 個(gè)頂點(diǎn)和 e 條邊，其中 n-1 條邊和 n 個(gè)頂點(diǎn)構(gòu)成一個(gè)極小(j xio)連通子圖，稱(chēng)該極小(j xio)連通子圖為此連通圖的生成樹(shù)。BACDFEBACDFE連通(lintng)圖連通圖的生成樹(shù)共一百八十九頁(yè) 一個(gè)有向圖的生成森林由若干棵有

14、向樹(shù)組成，含有(hn yu)圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹(shù)的弧。BACDFEBACDFE一個(gè)(y )有向圖及其生成森林 對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量的生成樹(shù)的集合為此非連通圖的生成森林共一百八十九頁(yè)二、抽象數(shù)據(jù)類(lèi)型圖的定義(dngy)ADT Graph 數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合， 稱(chēng)為頂點(diǎn)集。 數(shù)據(jù)關(guān)系R: R=VR VR=| v,wv且P(v,w)， 表示 從v 到w 的弧，謂詞(wi c)P(v,w)定義了弧 的意義或信息。 基本操作P:ADT Graph共一百八十九頁(yè)結(jié)構(gòu)(jigu)的建立和銷(xiāo)毀插入(ch r)或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪問(wèn)操

15、作遍歷插入和刪除弧基本操作共一百八十九頁(yè)CreateGraph(&G, V, VR): / 按定義(dngy)(V, VR) 構(gòu)造圖DestroyGraph(&G): / 銷(xiāo)毀(xiohu)圖結(jié)構(gòu)的建立和銷(xiāo)毀共一百八十九頁(yè)對(duì)頂點(diǎn)的訪問(wèn)(fngwn)操作LocateVex(G, u); / 若G中存在(cnzi)頂點(diǎn)u，則返回該頂點(diǎn)在 / 圖中“位置” ；否則返回其它信息。GetVex(G, v); / 返回 v 的值。PutVex(&G, v, value); / 對(duì) v 賦值value。共一百八十九頁(yè)對(duì)鄰接(ln ji)點(diǎn)的操作FirstAdjVex(G, v); / 返回(fnhu) v

16、的“第一個(gè)鄰接點(diǎn)” 。若該頂點(diǎn) / 在 G 中沒(méi)有鄰接點(diǎn)，則返回“空”。NextAdjVex(G, v, w); / 返回 v 的(相對(duì)于 w 的)“下一個(gè)鄰接點(diǎn)”。 / 若w是v的最后一個(gè)鄰接點(diǎn)，則返回“空”。共一百八十九頁(yè)插入或刪除(shnch)頂點(diǎn)InsertVex(&G, v); /在圖G中增添(zngtin)新頂點(diǎn)v。DeleteVex(&G, v); / 刪除G中頂點(diǎn)v及其相關(guān)的弧。共一百八十九頁(yè)插入(ch r)和刪除弧InsertArc(&G, v, w); / 在G中增添(zngtin)弧，若G是無(wú)向的， / 則還增添對(duì)稱(chēng)弧。DeleteArc(&G, v, w); /在G中刪

17、除弧，若G是無(wú)向的， /則還刪除對(duì)稱(chēng)弧。共一百八十九頁(yè)遍 歷DFSTraverse(G, v, Visit(); /從頂點(diǎn)v起深度優(yōu)先(yuxin)遍歷圖G，并對(duì)每 /個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先(yuxin)遍歷圖G，并對(duì)每 /個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。共一百八十九頁(yè)7.2 圖的存儲(chǔ)(cn ch)表示一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)(cn ch)表示二、圖的鄰接表存儲(chǔ)表示三、有向圖的十字鏈表存儲(chǔ)表示 四、無(wú)向圖的鄰接多重表存儲(chǔ)表示共一百八十九頁(yè)二. Representation of Graphs1.

18、 Adjacency Matrixadj_mat n n is defined for G(V, E) with n vertices, n 1 : Note: If G is undirected, then adj_mat is symmetric. Thus we can save space by storing only half of the matrix.4/7共一百八十九頁(yè)一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)(cn ch)表示鄰接矩陣: 表示結(jié)點(diǎn)間相鄰關(guān)系(gun x)的矩陣，用一個(gè)二維數(shù)組來(lái)表示集合VR。此二維數(shù)組稱(chēng)為鄰接矩陣。 若G是一個(gè)具有n個(gè)結(jié)點(diǎn)的圖，其鄰接矩陣是一個(gè)n階方陣。

19、共一百八十九頁(yè)(1) 無(wú)向(w xin)圖的鄰接矩陣定義(dngy) 設(shè)G=(V,VR)是有n(n 1)個(gè)頂點(diǎn)的無(wú)向圖，則G的鄰接矩陣是一個(gè)nn 矩陣:Ai,j=Aj,i=0 VR1 VR共一百八十九頁(yè) V1V2V4V3V50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 00 1 1 0 0無(wú)向圖的鄰接矩陣為對(duì)稱(chēng)(duchn)方陣；鄰接矩陣第i行（或第i列）的元素之和則是頂點(diǎn)Vi的度。共一百八十九頁(yè)定義 設(shè)G=(V,VR)是有n(n1)個(gè)頂點(diǎn)的有向圖，G的鄰接矩陣是具有如下(rxi)性質(zhì)的nn方陣: Ai,j=(2) 有向圖的鄰接矩陣1 當(dāng) E0 當(dāng) E共一百八十九頁(yè)有向

20、圖的鄰接矩陣為非對(duì)稱(chēng)矩陣(j zhn)；鄰接矩陣第i行的元素之和為頂點(diǎn)Vi的出度；鄰接矩陣第j列的元素之和為頂點(diǎn)Vj的入度。V1V2V3V40 1 1 00 0 0 00 0 0 11 0 0 0共一百八十九頁(yè)定義 設(shè)G=(V,VR)是有n(n1)個(gè)頂點(diǎn)的網(wǎng)，G的鄰接矩陣是具有如下(rxi)性質(zhì)的nn方陣: Ai,j=wij 當(dāng) E 當(dāng) E(3) 網(wǎng)的鄰接矩陣共一百八十九頁(yè)V1V3V6V5V4V23548715695 5 7 4 9 5 6 5 3 1 網(wǎng)N網(wǎng)N的鄰接矩陣共一百八十九頁(yè)#define INFINITY INF_MAX / 最大值#define MAX_VERTEX_NUM 20

21、 / 最大頂點(diǎn)(dngdin)個(gè)數(shù)Typedef enum DG,DN,UDG,UDN GraphKind; / 有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng)圖的鄰接矩陣存儲(chǔ)(cn ch)表示：共一百八十九頁(yè)typedef struct ArcCell / 弧的定義 VRType adj; / VRType是頂點(diǎn)關(guān)系類(lèi)型， / 對(duì)無(wú)權(quán)圖，用1或0表示相鄰(xin ln)否 / 對(duì)帶權(quán)網(wǎng)，則為權(quán)值類(lèi)型 InfoType *info; / 該弧相關(guān)信息的指針 ArcCell, AdjMatrix MAX_VERTEX_NUM MAX_VERTEX_NUM;共一百八十九頁(yè)typedef struct / 圖的定義

22、 VertexType vexsMAX_VERTEX_NUM; / 頂點(diǎn)向量(xingling) AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; / 圖的種類(lèi)標(biāo)志 MGraph;共一百八十九頁(yè)優(yōu)點(diǎn)： 借助于鄰接矩陣，容易判定任意兩個(gè)(lin )頂點(diǎn)之間是否有邊（或?。┫噙B，并容易求得各個(gè)頂點(diǎn)的度。 對(duì)于無(wú)向圖，頂點(diǎn)Vi 的度是鄰接矩陣第i 行（或第i列）的元素之和。 對(duì)于有向圖，第i 行的元素之和為頂點(diǎn)Vi 的出度；第j 列的元素之和為頂點(diǎn)Vj的入度。缺點(diǎn)： 占用的存儲(chǔ)單元個(gè)數(shù)只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，

23、而與邊的數(shù)目無(wú)關(guān)。共一百八十九頁(yè)1 Definitions2. Adjacency ListsReplace each row by a linked listExample0121graph00graph12graph2Note: The order of nodes in each list does not matter.For undirected G:S = n heads + 2e nodes = (n+2e) ptrs+2e ints5/7共一百八十九頁(yè)1 DefinitionsDegree( i ) = number of nodes in graph i (if G is u

24、ndirected).T of examine E(G) = O( n + e )If G is directed, we need to find in-degree(v) as well.Method 1 Add inverse adjacency lists.Example0121inv00inv11inv2Method 2 Multilist (Ch 3.2) representation for adj_mat i j tail ihead jcolumn for headrow for tail6/7共一百八十九頁(yè)1 DefinitionsAdjacency MultilistsI

25、n adjacency list, for each ( i, j ) we have two nodes:jgraphiigraphjNow lets combine the two nodes into one:graphigraphjnodev1v2marknextv1nextv2Example0123graph0graph1graph2graph3010223Weighted Edges adj_mat i j = weight adjacency lists multilists : add a weight field to the node.7/7共一百八十九頁(yè) 鄰接表是圖的一種

26、鏈?zhǔn)酱尜A結(jié)構(gòu)。在鄰接表中，對(duì)圖的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i 個(gè)單鏈表中的結(jié)點(diǎn)表示頂點(diǎn)i 的所有鄰接頂點(diǎn)。鏈表中每個(gè)結(jié)點(diǎn)由三個(gè)域組成： adivex info nextarcadivex 頂點(diǎn)vi的鄰接點(diǎn)info 存貯與邊和弧相關(guān)(xinggun)的權(quán)值nextarc指向vi下一個(gè)鄰接點(diǎn)的指針 二、圖的鄰接(ln ji)表存儲(chǔ)表示表結(jié)點(diǎn)共一百八十九頁(yè)在每個(gè)鏈表上附設(shè)一個(gè)表頭結(jié)點(diǎn)，由兩個(gè)域組成： data fristarc data 存貯與頂點(diǎn)vi有關(guān)信息的數(shù)據(jù)；fristarc 指向vi的第一個(gè)鄰接(ln ji)點(diǎn)的指針。表頭結(jié)點(diǎn)通常以順序結(jié)構(gòu)的形式存儲(chǔ)，以便隨機(jī)訪問(wèn)任一頂點(diǎn)的鄰接點(diǎn)鏈表。頭結(jié)

27、點(diǎn)(ji din)共一百八十九頁(yè)V1V2V3V4V531424320210101234 在無(wú)向圖的鄰接表中，頂點(diǎn)(dngdin)Vi的度恰為第i個(gè)鏈表中的表結(jié)點(diǎn)數(shù).V1V2V4V3V5無(wú)向(w xin)圖的鄰接表共一百八十九頁(yè)2130V1V2V3V40123 有向圖的鄰接(ln ji)表中，第i個(gè)鏈表中的表結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)Vi的出度。 在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧。有向圖的鄰接(ln ji)表V1V2V3V4共一百八十九頁(yè)V1V2V3V430200123有向圖的逆鄰接(ln ji)表V1V2V3V4 有向圖的逆鄰接表中，第i個(gè)鏈表中的表結(jié)點(diǎn)個(gè)數(shù)是頂點(diǎn)(dngdin)Vi的入度。 在有

28、向圖的逆鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。共一百八十九頁(yè)typedef struct ArcNode int adjvex; / 該弧所指向的頂點(diǎn)的位置 struct ArcNode *nextarc; / 指向下一條弧的指針(zhzhn) InfoType *info; / 該弧相關(guān)信息的指針 ArcNode;adjvex nextarc info弧的結(jié)點(diǎn)(ji din)結(jié)構(gòu)(表結(jié)點(diǎn)(ji din)共一百八十九頁(yè)typedef struct VNode VertexType data; / 頂點(diǎn)(dngdin)信息 ArcNode *firstarc; / 指向第一條依附該頂點(diǎn)的

29、弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc頂點(diǎn)的結(jié)點(diǎn)(ji din)結(jié)構(gòu)(頭結(jié)點(diǎn)(ji din)共一百八十九頁(yè)typedef struct AdjList vertices; / 表頭結(jié)點(diǎn)向量 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)(dngdin)數(shù)和弧數(shù) int kind; / 圖的種類(lèi)標(biāo)志 ALGraph;圖的結(jié)構(gòu)(jigu)定義共一百八十九頁(yè)優(yōu)點(diǎn)： 當(dāng)邊數(shù)頂點(diǎn)個(gè)數(shù)的平方(mn2)時(shí)，節(jié)省存儲(chǔ)空間； 運(yùn)算方便，容易(rngy)找到任意頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)。缺點(diǎn)： 要判定任意兩個(gè)頂點(diǎn)之間是否有邊或弧相連時(shí)，則需掃描

30、第i個(gè)或第j個(gè)鏈表，不及鄰接矩陣方便。共一百八十九頁(yè)三、有向圖的十字(sh z)鏈表存儲(chǔ)表示 十字鏈表是圖的另一種鏈?zhǔn)酱尜A結(jié)構(gòu)(jigu)，可以看成是將有向圖的鄰接表和逆鄰接表結(jié)合起來(lái)得到的一種鏈表。在十字鏈表中，對(duì)應(yīng)于有向圖的每個(gè)頂點(diǎn)和每一條弧都有一個(gè)結(jié)點(diǎn)。 共一百八十九頁(yè)弧的結(jié)點(diǎn)(ji din)結(jié)構(gòu)(弧結(jié)點(diǎn)(ji din)弧尾頂點(diǎn)(dngdin)位置 弧頭頂點(diǎn)位置 弧的相關(guān)信息指向下一個(gè)有相同弧尾的結(jié)點(diǎn)指向下一個(gè)有相同弧頭的結(jié)點(diǎn)typedef struct ArcBox / 弧的結(jié)構(gòu)表示 int tailvex, headvex; InfoType *info; struct ArcBox

31、 *hlink, *tlink; ArcBox;共一百八十九頁(yè)頂點(diǎn)(dngdin)的結(jié)點(diǎn)結(jié)構(gòu)(頂點(diǎn)(dngdin)結(jié)點(diǎn))頂點(diǎn)(dngdin)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧指向該頂點(diǎn)的第一條出弧typedef struct VexNode / 頂點(diǎn)的結(jié)構(gòu)表示 VertexType data; ArcBox *firstin, *firstout; VexNode;共一百八十九頁(yè)typedef struct VexNode xlistMAX_VERTEX_NUM; / 頂點(diǎn)結(jié)點(diǎn)(表頭向量(xingling) int vexnum, arcnum; / 有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;有

32、向圖的結(jié)構(gòu)表示(biosh)(十字鏈表)共一百八十九頁(yè)V1V2V3V4V1V2V3V4203031322301020123共一百八十九頁(yè)優(yōu)點(diǎn)： 容易(rngy)找到以Vi為尾的弧，也容易找到以Vi為頭的弧，因而容易求得頂點(diǎn)的出度和入度。共一百八十九頁(yè)四、無(wú)向圖的鄰接多重表存儲(chǔ)(cn ch)表示 鄰接多重表是無(wú)向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 每一條邊用一個(gè)結(jié)點(diǎn)(ji din)表示(邊結(jié)點(diǎn)) mark ivex ilink jvex jlink info該邊依附的兩個(gè)頂點(diǎn)指向下一條依附于頂點(diǎn)ivex的邊標(biāo)志域，用于標(biāo)記該條邊是否被搜索過(guò)指向下一條依附于頂點(diǎn)jvex的邊指向和邊相關(guān)的各種信息的指針域共一

33、百八十九頁(yè)每一個(gè)頂點(diǎn)(dngdin)也用一個(gè)結(jié)點(diǎn)表示：(頂點(diǎn)(dngdin)結(jié)點(diǎn)) data firstedge 存儲(chǔ)和該頂點(diǎn)相關(guān)的信息指示第一條依附于該頂點(diǎn)的邊 在鄰接多重表中，所有依附于同一頂點(diǎn)的邊串聯(lián)在同一鏈表中，由于每條邊依附于兩個(gè)(lin )頂點(diǎn)，則每個(gè)邊結(jié)點(diǎn)同時(shí)鏈接在兩個(gè)(lin )鏈表中。共一百八十九頁(yè)typedef struct Ebox VisitIf mark; / 訪問(wèn)標(biāo)記(bioj) int ivex, jvex; /該邊依附的兩個(gè)頂點(diǎn)的位置 struct Ebox *ilink, *jlink; /指向下一條依附于頂點(diǎn)的邊 InfoType *info; / 該邊信息

34、指針 EBox;邊的結(jié)構(gòu)(jigu)表示鄰接多重表的說(shuō)明： 共一百八十九頁(yè)typedef struct / 鄰接(ln ji)多重表 VexBox adjmulistMAX_VERTEX_NUM; /表頭向量 int vexnum, edgenum; /當(dāng)前頂點(diǎn)數(shù)和邊數(shù) AMLGraph;頂點(diǎn)(dngdin)的結(jié)構(gòu)表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附該頂點(diǎn)的邊 VexBox;無(wú)向圖的結(jié)構(gòu)表示共一百八十九頁(yè)V1V2V4V3V501234V1V2V3V4V5012141032324共一百八十九頁(yè) 對(duì)無(wú)

35、向圖而言，鄰接多重表和鄰接表的差別，僅僅在于同一條邊在鄰接表中用兩個(gè)結(jié)點(diǎn)表示，而在鄰接多重表中只有一個(gè)結(jié)點(diǎn)。因此，除了在邊結(jié)點(diǎn)中增加一個(gè)標(biāo)志(biozh)域外，鄰接多重表所需的存儲(chǔ)量和鄰接表相同。在鄰接多重表上，各種基本操作的實(shí)現(xiàn)和鄰接表相似。共一百八十九頁(yè)7.3 圖的遍歷(bin l) 從圖中某個(gè)頂點(diǎn)出發(fā)，訪遍圖中其余(qy)頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程，叫做圖的遍歷。共一百八十九頁(yè) 圖的遍歷要比樹(shù)的遍歷復(fù)雜得多。因?yàn)閳D中任一頂點(diǎn)都可能和其余的頂點(diǎn)相鄰接。所以，在訪問(wèn)了某個(gè)頂點(diǎn)之后，可能沿著某條搜索路徑(ljng)又回到該頂點(diǎn)上。為了避免同一頂點(diǎn)被多次訪問(wèn)，在遍歷圖的過(guò)程中，

36、必須記下每個(gè)已訪問(wèn)過(guò)的頂點(diǎn)。為此，我們可設(shè)一個(gè)輔助數(shù)組visited0.n-1，它的初始值置為“假”或者“0”，一旦訪問(wèn)了頂點(diǎn)Vi，便置visitedi為“真”或者被訪問(wèn)時(shí)的次序號(hào)。共一百八十九頁(yè)深度優(yōu)先搜索(su su)（縱向優(yōu)先搜索(su su)）Depth-First Search廣度(gungd)優(yōu)先搜索（橫向優(yōu)先搜索）Breadth-First Search通常有兩條遍歷圖的路徑：遍歷應(yīng)用舉例共一百八十九頁(yè) 從圖中某個(gè)頂點(diǎn)V0 出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從V0的各個(gè)未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先搜索(su su)遍歷圖，直至圖中所有和V0有路徑相通的頂點(diǎn)都被訪問(wèn)到。一、深度優(yōu)先搜索(s

37、u su)遍歷圖 (Depth-First Search)連通圖的深度優(yōu)先搜索遍歷共一百八十九頁(yè)Vw1SG1SG2SG3W1、W2和W3 均為 V 的鄰接(ln ji)點(diǎn)，SG1、SG2 和 SG3 分別為含頂點(diǎn)W1、W2和W3 的子圖。訪問(wèn)頂點(diǎn) V;for (W1、W2、W3 ) 若該鄰接點(diǎn)W未被訪問(wèn)， 則從它出發(fā)進(jìn)行深度(shnd)優(yōu)先搜索遍歷w2w3w2共一百八十九頁(yè)V1V2V3V4V5V6V7V8深度優(yōu)先(yuxin)搜索結(jié)果： V1 V2 V4 V8 V5 V3 V6 V7共一百八十九頁(yè)從上頁(yè)的圖解(tji)可見(jiàn): 1. 深度優(yōu)先(yuxin)搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷；

38、解決的辦法是：為每個(gè)頂點(diǎn)設(shè)立一個(gè) “訪問(wèn)標(biāo)志 visitedw”。 2. 如何判別V的鄰接點(diǎn)是否被訪問(wèn)？共一百八十九頁(yè)void DFS(Graph G, int v) / 從頂點(diǎn)v出發(fā)，深度優(yōu)先搜索遍歷連通(lintng)圖 G visitedv = TRUE; VisitFunc(v); / 訪問(wèn)第v 個(gè)結(jié)點(diǎn) for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w / 遞歸調(diào)用DFS / DFS共一百八十九頁(yè) 首先將圖中每個(gè)頂點(diǎn)的訪問(wèn)標(biāo)志設(shè)為 FALSE, 之后，

39、從圖中某個(gè)頂點(diǎn)v0出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次(yc)從v0的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v0有路徑相通的頂點(diǎn)都被訪問(wèn)到為止；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。非連通(lintng)圖的深度優(yōu)先搜索遍歷共一百八十九頁(yè)F F F F F F F F FTTTTTTTTTachdkfe bg訪問(wèn)(fngwn)標(biāo)志:訪問(wèn)(fngwn)次序:例如:0 1 2 3 4 5 6 7 8(a) (b) (c) (d) (e) (f) (g) (h) (k)abchdekfgachkfedbg共一百八十九頁(yè)voi

40、d DFSTraverse(Graph G, Status (*Visit)(int v) / 對(duì)圖 G 作深度優(yōu)先遍歷。 VisitFunc = Visit; / 使用全局變量，使DFS不必(bb)設(shè)函數(shù)指針參數(shù) for (v=0; vG.vexnum; +v) visitedv = FALSE; / 訪問(wèn)標(biāo)志數(shù)組初始化 for (v=0; vw1, V-w2, V-w8 的路徑長(zhǎng)度為1；V-w7, V-w3, V-w5 的路徑長(zhǎng)度為2；V-w6, V-w4 的路徑長(zhǎng)度為3。Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4廣度優(yōu)先搜索結(jié)果： V-w1-w2-w8 -w7-

41、w3-w5 - w6-w4 共一百八十九頁(yè)廣度優(yōu)先(yuxin)搜索結(jié)果： V1 V2 V3 V4 V5 V6 V7 V8V1V2V3V4V5V6V7V8共一百八十九頁(yè) 廣度優(yōu)先搜索圖的過(guò)程是以v為起始點(diǎn)，由近至遠(yuǎn)，依次訪問(wèn)和v有路徑相通且路徑長(zhǎng)度為1，2，的頂點(diǎn)。類(lèi)似于樹(shù)的按層次遍歷過(guò)程。 和深度優(yōu)先搜索類(lèi)似，在遍歷的過(guò)程中也需要一個(gè)訪問(wèn)標(biāo)志數(shù)組。并且，為了(wi le)順次訪問(wèn)路徑長(zhǎng)度為2、3、的頂點(diǎn)，需附設(shè)隊(duì)列以存儲(chǔ)以被訪問(wèn)的路徑長(zhǎng)度為1，2，的頂點(diǎn)。共一百八十九頁(yè) void BFSTraverse(Graph G, Status (*Visit)(int v) for (v=0; vG

42、.vexnum; +v) visitedv = FALSE; / 初始化訪問(wèn)(fngwn)標(biāo)志 InitQueue(Q); / 置空的輔助隊(duì)列Q for ( v=0; vnext = Q.rear-next = NULLvoid EnQueue( LinkQueue& Q, QelemType e ) p = (QueuePtr) malloc (sizeof(QNode); p-data = e; p-next = NULL; p-priou = Q.front Q.rear-next = p; Q.rear = p;void DeQueue( LinkQueue& Q, QelemType

43、& e ) Q.front = Q.front-next; e = Q.front-data共一百八十九頁(yè)Applications of Depth-First Search/* a generalization of preorder traversal */void DFS ( Vertex V ) /* this is only a template */ visited V = true; /* mark this vertex to avoid cycles */ for ( each W adjacent to V ) if ( !visited W )DFS( W ); /* T

44、 = O( |E| + |V| ) as long as adjacency lists are used */0123456DFS ( 0 )1. Undirected Graphsvoid ListComponents ( Graph G ) for ( each V in G ) if ( !visited V ) DFS( V ); printf(“n“); 780 1 4 6 5 2 37 81/15共一百八十九頁(yè)7.4 圖的連通性和生成(shn chn)樹(shù)1、連通(lintng)圖 從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可遍歷完圖中所有頂點(diǎn)，這個(gè)圖就是連通圖。V1V

45、2V3V4V5V6V7V8共一百八十九頁(yè)2、圖的生成樹(shù) 設(shè)G=(V,E)是個(gè)連通圖，而E(G)為連通圖中所有邊的集合，若從圖中任一頂點(diǎn)開(kāi)始作一次搜索過(guò)程(guchng)，則將E(G)分成兩個(gè)集合：T(G)和B(G)。 T(G)是遍歷圖時(shí)走過(guò)的邊的集合， B(G)是剩余邊的集合， T(G)和圖中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子樹(shù)，稱(chēng)為圖G的生成樹(shù)。 圖的生成樹(shù)不唯一，從不同結(jié)點(diǎn)出發(fā)進(jìn)行搜索，可以得到不同的生成樹(shù)。共一百八十九頁(yè)深度(shnd)優(yōu)先生成樹(shù)：由深度(shnd)優(yōu)先搜索得到的生成樹(shù)。廣度優(yōu)先生成樹(shù)：由廣度優(yōu)先搜索得到的生成樹(shù)。 12345678 無(wú)向圖 深度優(yōu)先(yuxin)生成樹(shù)

46、 廣度優(yōu)先(yuxin)生成樹(shù)1234567812345678共一百八十九頁(yè)3、最小代價(jià)生成樹(shù) 任何具有n個(gè)頂點(diǎn)(dngdin)的連通圖，至少有n-1條邊，而且所有具有n-1條邊的連通圖都是樹(shù)。若在連通圖的各條邊上賦以權(quán)值即網(wǎng)絡(luò)表示相應(yīng)的代價(jià)，那么，則從連通圖中選擇一棵總代價(jià)最小的樹(shù)，即為最小代價(jià)生成樹(shù)。 共一百八十九頁(yè) Minimum Spanning Tree【Definition】 A spanning tree of a graph G is a tree which consists of V( G ) and a subset of E( G )Example A complete

47、 graph and three of its spanning treesNote: The minimum spanning tree is a tree since it is acyclic - the number of edges is |V| 1.It is minimum for the total cost of edges is minimized.It is spanning because it covers every vertex.A minimum spanning tree exists if G is connected.Adding a non-tree e

48、dge to a spanning tree, we obtain a cycle.7/10共一百八十九頁(yè) 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1條線路，如何在最節(jié)省(jishng)經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？4、最小代價(jià)生成(shn chn)樹(shù)的應(yīng)用問(wèn)題的提出：共一百八十九頁(yè) 在每?jī)蓚€(gè)城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價(jià)。n個(gè)城市之間，最多可能設(shè)置 n(n-1)/2 條線路，那么，如何在這些可能的線路中選擇(xunz) n-1 條，以使總的耗費(fèi)最少呢？1245631234555666共一百八十九頁(yè) 可以用連通網(wǎng)來(lái)表示n個(gè)城市以及n個(gè)城

49、市之間可能設(shè)置的通信線路，其中，網(wǎng)的頂點(diǎn)表示城市，邊表示兩城市之間的線路，賦予邊的權(quán)值表示相應(yīng)的代價(jià)。對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹(shù)，每一棵生成樹(shù)都可以是一個(gè)通訊網(wǎng)?，F(xiàn)在，我們要選擇(xunz)這樣一棵生成樹(shù)，也就是總的耗費(fèi)最少。共一百八十九頁(yè) 構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即： 在 e 條帶權(quán)的邊中選取 n-1 條邊（不構(gòu)成(guchng)回路），使“權(quán)值之和”為最小。算法(sun f)二：克魯斯卡爾 (Kruskal) 法該問(wèn)題等價(jià)于：算法一：普里姆 (Prim) 法基本思想： 按權(quán)值非遞減次序構(gòu)造最小代價(jià)生成樹(shù)。共一百八十九頁(yè) 取圖中任意(rny)一個(gè)頂點(diǎn) v 作為生成樹(shù)的根，之

50、后往生成樹(shù)上添加新的頂點(diǎn) w。在添加的頂點(diǎn) w 和已經(jīng)在生成樹(shù)上的頂點(diǎn)v 之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點(diǎn) v 和 w 之間的邊中取值最小。之后繼續(xù)往生成樹(shù)上添加頂點(diǎn)，直至生成樹(shù)上含有 n 個(gè)頂點(diǎn)為止。（1）普里姆算法的基本(jbn)思想共一百八十九頁(yè)abcdegf例如(lr):195141827168213ae12dcbgf7148531621所得(su d)生成樹(shù)權(quán)值和= 14+8+3+5+16+21 = 67共一百八十九頁(yè) 在生成樹(shù)的構(gòu)造過(guò)程(guchng)中，圖中 n 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集V-U ，則應(yīng)在所有連通U中

51、頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊。一般情況下所添加的頂點(diǎn)(dngdin)應(yīng)滿足下列條件:UV-U共一百八十九頁(yè) 設(shè)置一個(gè)輔助數(shù)組，對(duì)當(dāng)前VU集中(jzhng)的每個(gè)頂點(diǎn)，記錄和頂點(diǎn)集U中頂點(diǎn)相連接的代價(jià)最小的邊：struct VertexType adjvex; / U集中(jzhng)的頂點(diǎn)序號(hào) VRType lowcost; / 邊的權(quán)值 closedge MAX_VERTEX_NUM;共一百八十九頁(yè)abcdegf195141827168213ae12dcb7aaa19141814例如(lr):e12ee8168d3dd7213c55gf共一百八十九頁(yè)abcdegf51416821

52、3共一百八十九頁(yè)void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從頂點(diǎn)(dngdin)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù) k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 輔助數(shù)組初始化 if (j!=k) closedgej = u, G.arcskj.adj ; / adjvex, lowcost closedgek.lowcost = 0; / 初始，Uu for (i=0; i0, ViV-U printf(closedgek.adjvex, G.vexsk); / 輸出生成樹(shù)上一條邊

53、的兩個(gè)頂點(diǎn) closedgek.lowcost = 0; / 第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) / 修改其它頂點(diǎn)的最小邊 if (G.arcskj.adj closedgej.lowcost) / 新頂點(diǎn)并入U(xiǎn)后重新選擇最小邊 closedgej = G.vexsk, G.arcskj.adj ; 共一百八十九頁(yè)具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加(tin ji)不使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止?？紤]問(wèn)題的出發(fā)點(diǎn): 為使生成(shn chn)樹(shù)上邊的權(quán)值之和達(dá)

54、到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能地小。（2）克魯斯卡爾算法的基本思想共一百八十九頁(yè)abcdegf195141827168213ae12dcbgf7148531621例如(lr):7121819共一百八十九頁(yè)abcdegf514168213共一百八十九頁(yè)算法(sun f)描述:構(gòu)造非連通圖 ST=( V, ); /v表示頂點(diǎn)(dngdin)的集合， / 表示邊的集合，首先是空 k = i = 0; / k 計(jì)選中的邊數(shù) while (kn-1) +i; 檢查邊集 E 中第 i 條權(quán)值最小的邊(u,v); 若(u,v)加入ST后不使ST中產(chǎn)生回路， 則 輸出邊(u,v); 且 k+;/最

55、多對(duì)e條邊各掃描一次，每次選擇最小代價(jià)的邊需O(loge)，第一次選擇需要O(e)共一百八十九頁(yè)(2) Kruskals Algorithm maintain a forestvoid Kruskal ( Graph G ) T = ; while ( T contains less than |V| 1 edges & E is not empty ) choose a least cost edge (v, w) from E ; delete (v, w) from E ; if ( (v, w) does not create a cycle in T ) add (v, w) to

56、T ; else discard (v, w) ; if ( T contains fewer than |V| 1 edges ) Error ( “No spanning tree” ) ;/* DeleteMin */* Union / Find */T = O( |E| log |E| )9/10共一百八十九頁(yè)普里姆算法(sun f)克魯斯卡爾算法(sun f)時(shí)間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍（3）比較兩種算法共一百八十九頁(yè)7.6 兩點(diǎn)之間的 最短路徑(ljng)問(wèn)題 求從某個(gè)源點(diǎn)到其余(qy)各點(diǎn)的最短路徑 每一對(duì)頂點(diǎn)之間的最短路徑共一百八十九頁(yè)Shor

57、test Path AlgorithmsGiven a digraph G = ( V, E ), and a cost function c( e ) for e E( G ). The length of a path P from source to destination is (also called weighted path length).1. Single-Source Shortest-Path ProblemGiven as input a weighted graph, G = ( V, E ), and a distinguished vertex, s, find

58、the shortest weighted path from s to every other vertex in G.v1v2v6v7v3v4v52421310258461v1v2v6v7v3v4v52421310258461Negative-cost cycleNote: If there is no negative-cost cycle, the shortest path from s to s is defined to be zero.6/17共一百八十九頁(yè) Unweighted Shortest Pathsv1v2v6v7v3v4v500: v31: v1 and v6112

59、: v2 and v4223: v5and v733 Sketch of the ideaBreadth-first search ImplementationTable i .Dist := distance from s to vi /* initialized to be except for s */Table i .Known := 1 if vi is checked; or 0 if notTable i .Path := for tracking the path /* initialized to be 0 */7/17共一百八十九頁(yè)void Unweighted( Tabl

60、e T ) int CurrDist; Vertex V, W; for ( CurrDist = 0; CurrDist NumVertex; CurrDist + ) for ( each vertex V )if ( !T V .Known & T V .Dist = CurrDist ) T V .Known = true; for ( each W adjacent to V ) if ( T W .Dist = Infinity ) T W .Dist = CurrDist + 1;T W .Path = V; /* end-if Dist = Infinity */ /* end