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共一百八十九頁課時(ksh)安排 6學(xué)時教學(xué)內(nèi)容： 圖的基本概念；圖的存儲結(jié)構(gòu)；圖的遍歷；最小生

2、成(shn chn)樹；最短路徑；拓?fù)渑判蚝完P(guān)鍵路徑； 要求學(xué)生掌握： 1、熟悉圖的各種存儲結(jié)構(gòu)，了解實(shí)際問題與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系；2、遍歷圖的遞歸和非遞歸算法；3、應(yīng)用圖的遍歷算法求各種簡單路徑問題，比如，最小生成樹最短路徑拓?fù)渑判蜿P(guān)鍵路徑等。教學(xué)重點(diǎn)及難點(diǎn)： 圖的各種存儲結(jié)構(gòu)，圖的遍歷算法，構(gòu)造最小生成樹的算法。 共一百八十九頁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共一百八十九頁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共一百八十九頁 (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共一百八十九頁 圖是由一個頂點(diǎn)集 V 和一個弧集 VR構(gòu)成的數(shù)據(jù)結(jié)構(gòu) G = (V , VR )其中， VR| v,wV 且 P(v,w) 表示從 v 到 w 的一條弧，并稱 v 為弧尾，w 為弧頭。 謂詞 P(v,w) 定義了弧 的意義(yy)或信息一、圖的結(jié)構(gòu)(jigu)定義:共一百八十九頁 由于“弧”是有方向的，因此(ync)稱由頂點(diǎn)集和弧集構(gòu)成的圖為有向圖。 AB E

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

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

11、)/2 條邊的無向圖稱作完全圖；含有 e=n(n-1) 條弧的有向圖稱作 有向完全圖 若邊或弧的個數(shù) enlogn，則稱作稀疏圖， 否則稱作稠密圖。共一百八十九頁 假若頂點(diǎn)(dngdin)v 和頂點(diǎn)w 之間存在一條邊，則稱頂點(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共一百八十九頁對有向圖來說，頂點(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共一百八十九頁設(shè)圖G=(V,VR)中的一個頂點(diǎn)序列(xli) u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱從頂點(diǎn)u 到頂點(diǎn)w 之間存在一條路徑。路徑上邊的數(shù)目稱作路徑長度。ABECF如:長度(chngd)為3的路徑A,B,C,F簡單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。回路:序列中第一個頂點(diǎn)和最后一個頂點(diǎn)相同的路徑。共一百八十九頁 若圖G中任意兩個頂點(diǎn)之間都有路徑相通(xingtng)，則稱此圖為連通圖；否則，稱之為非連通圖。BACDFEBACDFE連通(lintng)圖非連通圖共一百八十九頁 若無向(w

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

14、向樹組成，含有(hn yu)圖中全部頂點(diǎn)，但只有足以構(gòu)成若干棵不相交的有向樹的弧。BACDFEBACDFE一個(y )有向圖及其生成森林 對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林共一百八十九頁二、抽象數(shù)據(jù)類型圖的定義(dngy)ADT Graph 數(shù)據(jù)對象V：V是具有相同特性的數(shù)據(jù)元素的集合， 稱為頂點(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共一百八十九頁結(jié)構(gòu)(jigu)的建立和銷毀插入(ch r)或刪除頂點(diǎn)對鄰接點(diǎn)的操作對頂點(diǎn)的訪問操

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

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

17、除弧，若G是無向的， /則還刪除對稱弧。共一百八十九頁遍 歷DFSTraverse(G, v, Visit(); /從頂點(diǎn)v起深度優(yōu)先(yuxin)遍歷圖G，并對每 /個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先(yuxin)遍歷圖G，并對每 /個頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。共一百八十九頁7.2 圖的存儲(cn ch)表示一、圖的數(shù)組(鄰接矩陣)存儲(cn ch)表示二、圖的鄰接表存儲表示三、有向圖的十字鏈表存儲表示 四、無向圖的鄰接多重表存儲表示共一百八十九頁二. 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共一百八十九頁一、圖的數(shù)組(鄰接矩陣)存儲(cn ch)表示鄰接矩陣: 表示結(jié)點(diǎn)間相鄰關(guān)系(gun x)的矩陣，用一個二維數(shù)組來表示集合VR。此二維數(shù)組稱為鄰接矩陣。 若G是一個具有n個結(jié)點(diǎn)的圖，其鄰接矩陣是一個n階方陣。

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

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

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

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

23、而與邊的數(shù)目無關(guān)。共一百八十九頁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共一百八十九頁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共一百八十九頁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共一百八十九頁 鄰接表是圖的一種

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

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

28、向圖的逆鄰接表中，對每個頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧。共一百八十九頁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)共一百八十九頁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)共一百八十九頁typedef struct AdjList vertices; / 表頭結(jié)點(diǎn)向量 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)(dngdin)數(shù)和弧數(shù) int kind; / 圖的種類標(biāo)志 ALGraph;圖的結(jié)構(gòu)(jigu)定義共一百八十九頁優(yōu)點(diǎn)： 當(dāng)邊數(shù)頂點(diǎn)個數(shù)的平方(mn2)時，節(jié)省存儲空間； 運(yùn)算方便，容易(rngy)找到任意頂點(diǎn)的第一個鄰接點(diǎn)和下一個鄰接點(diǎn)。缺點(diǎn)： 要判定任意兩個頂點(diǎn)之間是否有邊或弧相連時，則需掃描

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

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

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

34、指針 EBox;邊的結(jié)構(gòu)(jigu)表示鄰接多重表的說明： 共一百八十九頁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;無向圖的結(jié)構(gòu)表示共一百八十九頁V1V2V4V3V501234V1V2V3V4V5012141032324共一百八十九頁 對無

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

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

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

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

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

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

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

42、.vexnum; +v) visitedv = FALSE; / 初始化訪問(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共一百八十九頁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共一百八十九頁7.4 圖的連通性和生成(shn chn)樹1、連通(lintng)圖 從圖中任一頂點(diǎn)出發(fā)，進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，便可遍歷完圖中所有頂點(diǎn)，這個圖就是連通圖。V1V

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

46、 廣度優(yōu)先(yuxin)生成樹1234567812345678共一百八十九頁3、最小代價生成樹 任何具有n個頂點(diǎn)(dngdin)的連通圖，至少有n-1條邊，而且所有具有n-1條邊的連通圖都是樹。若在連通圖的各條邊上賦以權(quán)值即網(wǎng)絡(luò)表示相應(yīng)的代價，那么，則從連通圖中選擇一棵總代價最小的樹，即為最小代價生成樹。 共一百八十九頁 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共一百八十九頁 假設(shè)要在 n 個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個城市只需要修建 n-1條線路，如何在最節(jié)省(jishng)經(jīng)費(fèi)的前提下建立這個通訊網(wǎng)？4、最小代價生成(shn chn)樹的應(yīng)用問題的提出：共一百八十九頁 在每兩個城市之間都可以設(shè)置一條線路，相應(yīng)地都要付出一定的經(jīng)濟(jì)代價。n個城市之間，最多可能設(shè)置 n(n-1)/2 條線路，那么，如何在這些可能的線路中選擇(xunz) n-1 條，以使總的耗費(fèi)最少呢？1245631234555666共一百八十九頁 可以用連通網(wǎng)來表示n個城市以及n個城

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

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

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

52、3共一百八十九頁void MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法從頂點(diǎn)(dngdin)u出發(fā)構(gòu)造網(wǎng)G的最小生成樹 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); / 輸出生成樹上一條邊

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

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

55、多對e條邊各掃描一次，每次選擇最小代價的邊需O(loge)，第一次選擇需要O(e)共一百八十九頁(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共一百八十九頁普里姆算法(sun f)克魯斯卡爾算法(sun f)時間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍（3）比較兩種算法共一百八十九頁7.6 兩點(diǎn)之間的 最短路徑(ljng)問題 求從某個源點(diǎn)到其余(qy)各點(diǎn)的最短路徑 每一對頂點(diǎn)之間的最短路徑共一百八十九頁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共一百八十九頁 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共一百八十九頁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