1、2020/9/9,1,第7章 圖,本章主題：圖的基本概念、圖的存儲(chǔ)結(jié)構(gòu)和圖的常用算法 教學(xué)目的： 教學(xué)重點(diǎn)：圖的各種存儲(chǔ)方式及其運(yùn)算 教學(xué)難點(diǎn)：圖結(jié)構(gòu)存儲(chǔ)方式的選擇，幾種經(jīng)典圖算法的實(shí)現(xiàn) 本章內(nèi)容：圖的基本概念 圖的存儲(chǔ)結(jié)構(gòu) 圖的遍歷 最小生成樹 最短路徑 拓?fù)渑判?關(guān)鍵路徑,2020/9/9,2,本章主要介紹圖的基本概念、圖的存儲(chǔ)結(jié)構(gòu)和有關(guān)圖的一些常用算法。通過本章學(xué)習(xí)，讀者應(yīng)該： 1) 了解圖的定義和術(shù)語 2) 掌握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu) 3) 掌握?qǐng)D的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法 4) 理解最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等圖的常用算法,本章學(xué)習(xí)導(dǎo)讀,2020/9/9,3,圖（G

2、raph）是一種較線性表和樹更為復(fù)雜的非線性結(jié)構(gòu)。是對(duì)結(jié)點(diǎn)的前趨和后繼個(gè)數(shù)不加限制的數(shù)據(jù)結(jié)構(gòu)，用來描述元素之間“多對(duì)多”的關(guān)系。 在線性結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系是線性關(guān)系，除開始結(jié)點(diǎn)和 終端結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)只有一個(gè)直接前趨和直接后繼。 在樹形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系實(shí)質(zhì)上是層次關(guān)系，同層上的每個(gè)結(jié)點(diǎn)可以和下一層的零個(gè)或多個(gè)結(jié)點(diǎn)（即孩子）相關(guān)，但只能和上一層的一個(gè)結(jié)點(diǎn)（即雙親）相關(guān)（根結(jié)點(diǎn)除外）。 在圖結(jié)構(gòu)中，對(duì)結(jié)點(diǎn)（圖中常稱為頂點(diǎn)）的前趨和后繼個(gè)數(shù)不加限制的，即結(jié)點(diǎn)之間的關(guān)系是任意的。 由此，圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計(jì)算機(jī)科學(xué)以及

3、數(shù)學(xué)的其它分支中。,2020/9/9,4,7. 1 .1 圖的定義 圖是由一個(gè)頂點(diǎn)集 V 和一個(gè)弧集 R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)。 Graph = (V, R ) V = x | x 某個(gè)數(shù)據(jù)對(duì)象 ， 是頂點(diǎn)的有窮非空集合； R邊的有限集合 R = (x, y) | x, y V 無向圖 或 R = | x, y V /鄰接矩陣類型 typedef struct VertexType vexsMAX_VERTEX_NUM; /頂點(diǎn)表 AdjMatrix arcs; /鄰接矩陣 int vexnum,arcnum; /圖的頂點(diǎn)數(shù)和弧數(shù) MGraph; 由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀

4、疏矩陣，因此會(huì)造成一定存儲(chǔ)空間的浪費(fèi)。,2020/9/9,23,建立鄰接矩陣算法: void CreateMGraph(MGraph ,j=LocateVex(G,v2); G.arcsij=w; G.arcsji=w; return; ,2020/9/9,24,void PrintMGraph(MGraph G) /輸出 int i,j; printf(Output Vertices:); printf(%s,G.vexs); printf(n); printf(Output AdjMatrix:n); for (i=0;iG.vexnum;i+) for (j=0;jG.vexnum;j+

5、) printf(%4d,G.arcsij); printf(n); return; ,2020/9/9,25,7.2.2 鄰接表 圖的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 1) 為每個(gè)頂點(diǎn)建立一個(gè)單鏈表， 2) 第i個(gè)單鏈表中包含頂點(diǎn)Vi的所有鄰接頂點(diǎn)。 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，用單鏈表中的一個(gè)結(jié)點(diǎn)表示依附于該頂點(diǎn)的一條邊（或表示以該頂點(diǎn)為弧尾的一條?。Q為邊（或?。┙Y(jié)點(diǎn)。,2020/9/9,26,把同一個(gè)頂點(diǎn)發(fā)出的邊鏈接在同一個(gè)邊鏈表中，鏈表的每一個(gè)結(jié)點(diǎn)代表一條邊，叫做表結(jié)點(diǎn)（邊結(jié)點(diǎn)），鄰接點(diǎn)域adjvex保存與該邊相關(guān)聯(lián)的另一頂點(diǎn)的頂點(diǎn)下

6、標(biāo) ， 鏈域nextarc存放指向同一鏈表中下一個(gè)表結(jié)點(diǎn)的指針 ，數(shù)據(jù)域info存放邊的權(quán)。邊鏈表的表頭指針存放在頭結(jié)點(diǎn)中。頭結(jié)點(diǎn)以順序結(jié)構(gòu)存儲(chǔ)，其數(shù)據(jù)域data存放頂點(diǎn)信息，鏈域firstarc指向鏈表中第一個(gè)頂點(diǎn)。,2020/9/9,27,帶權(quán)圖的邊結(jié)點(diǎn)中info保存該邊上的權(quán)值 。 頂點(diǎn) Vi 的邊鏈表的頭結(jié)點(diǎn)存放在下標(biāo)為 i 的頂點(diǎn)數(shù)組中。 在鄰接表的邊鏈表中，各個(gè)邊結(jié)點(diǎn)的鏈入順序任意，視邊結(jié)點(diǎn)輸入次序而定。 設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則用鄰接表表示無向圖時(shí)，需要 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，2e 個(gè)邊結(jié)點(diǎn)；用鄰接表表示有向圖時(shí)，若不考慮逆鄰接表，只需 n 個(gè)頂點(diǎn)結(jié)點(diǎn)，e 個(gè)邊結(jié)點(diǎn)。 建立鄰

7、接表的時(shí)間復(fù)雜度為O(n*e)。若頂點(diǎn)信息即為頂點(diǎn)的下標(biāo)，則時(shí)間復(fù)雜度為O(n+e)。,2020/9/9,28,有向圖的鄰接表和逆鄰接表,在有向圖的鄰接表中，第 i 個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)Vi的出度。 在有向圖的逆鄰接表中，第 i 個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)是頂點(diǎn)Vi 的入度。,2020/9/9,29,圖7-7 為圖7-6 (a)的的鄰接表和逆鄰接表,圖7-7 有向圖的鄰接表和逆鄰接表,7-6 (a),2020/9/9,30,網(wǎng)絡(luò) (帶權(quán)圖) 的鄰接表,2020/9/9,31,存儲(chǔ)表示 typedef struct ArcNode int adjvex; struct ArcNode *nextar

8、c; int info; ArcNode; /邊結(jié)點(diǎn)類型 typedef struct VNode VertexType data; ArcNode *firstarc; VNode,AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices; /鄰接表 int vexnum,arcnum; ALGraph;,2020/9/9,32,int LocateVex(ALGraph G,char u) int i; for (i=0;iG.vexnum;i+) if(u= =G.verticesi.data) return i; if (i= =G.

9、vexnum) printf(Error u!n);exit(1); return 0; ,void CreateALGraph_adjlist(ALGraph ,2020/9/9,33,printf(Input Arcs(v1,v2 ,2020/9/9,34,7.2.3 十字鏈表 十字鏈表 (Orthogonal List)是有向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?？煽醋魇菍⒂邢驁D的鄰接表和逆鄰接表結(jié)合的一種鏈表。 在十字鏈表中，為每個(gè)頂點(diǎn)vi設(shè)置一個(gè)結(jié)點(diǎn)，它包含數(shù)據(jù)域data和兩個(gè)鏈域firstout、firstin，稱為頂點(diǎn)結(jié)點(diǎn)。數(shù)據(jù)域data用于存放頂點(diǎn)vi的有關(guān)信息；鏈域firstin指向以頂點(diǎn)

10、vi為弧頭的第一個(gè)弧結(jié)點(diǎn)；鏈域firstout指向以頂點(diǎn)vi為弧尾的第一個(gè)弧結(jié)點(diǎn)。 弧結(jié)點(diǎn)包括四個(gè)域：尾域tailvex、頭域headvex，鏈域hlink和tlink。 hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條??；data頂點(diǎn)信息，firstin以該頂點(diǎn)為頭的第一個(gè)弧結(jié)點(diǎn)，firstout以該結(jié)點(diǎn)為尾的第一個(gè)弧結(jié)點(diǎn),頂點(diǎn)結(jié)點(diǎn),弧結(jié)點(diǎn),2020/9/9,35,圖7-8 十字鏈表,圖7-8為圖7-6 (a)有向圖的十字鏈表。,采用十字鏈表表示有向圖，很容易找到以頂點(diǎn)vi為弧尾的弧和以頂點(diǎn)vi為弧頭的弧，因此頂點(diǎn)的出度、入度都很容易求得。,2020/9/9,36,十字鏈表的

11、數(shù)據(jù)類型定義如下： #define MAXV typedef struct /弧結(jié)點(diǎn) int tailvex,headvex; /弧尾和弧頭頂點(diǎn)位置 struct ArcNode *hlink,*tlink; /弧頭相同和弧尾相同的弧的鏈域 ArcNode; typedef struct /頂點(diǎn)結(jié)點(diǎn) VertexType data; /頂點(diǎn)信息 ArcNode *firstin,*firstout; /分別指向該頂點(diǎn)的第一條入弧和出弧 VexNode;,2020/9/9,37,7.2.4 鄰接多重表 鄰接多重表是無向圖的另一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。在鄰接多重表中設(shè)置一個(gè)邊結(jié)點(diǎn)表示圖中的一條邊。邊結(jié)點(diǎn)包

12、含五個(gè)域，結(jié)構(gòu)如下所示：,其中：mark 域 標(biāo)志域，用于對(duì)該邊進(jìn)行標(biāo)記； ivex 域 存放該邊依附的一個(gè)頂點(diǎn)vi的位置信息； ilink 域 該鏈域指向依附于頂點(diǎn)vi的另一條邊的邊結(jié)點(diǎn)； jvex 域 存放該邊依附的另一個(gè)頂點(diǎn)vj的位置信息； jlink 域 該鏈域指向依附于頂點(diǎn)vj的另一條邊的邊結(jié)點(diǎn)。 鄰接多重表為每個(gè)頂點(diǎn)設(shè)置一個(gè)結(jié)點(diǎn)，其結(jié)構(gòu)如下：,2020/9/9,38,圖7-9 鄰接多重表,圖7-9為圖7-5 (a)無向圖的鄰接多重表。,由鄰接多重表可以看出，表示邊（vi，vj）的邊結(jié)點(diǎn)通過鏈域ilink和jlink鏈入了頂點(diǎn)vi和頂點(diǎn)vj的兩個(gè)鏈表中，實(shí)現(xiàn)了用一個(gè)邊結(jié)點(diǎn)表示一個(gè)邊的

13、目的，克服了在鄰接表中用兩個(gè)邊結(jié)點(diǎn)表示一個(gè)邊的缺點(diǎn)。因此鄰接多重表是無向圖的一種很有效的存儲(chǔ)結(jié)構(gòu)。,2020/9/9,39,鄰接多重表的結(jié)點(diǎn)數(shù)據(jù)類型定義如下： #define MAXV typedef struct /邊結(jié)點(diǎn)類型 int mark; /訪問標(biāo)識(shí) int ivex,jvex; /該邊的兩個(gè)頂點(diǎn)位置信息 struct Enode *ilink,*jlink; /分別指向依附這兩個(gè)頂點(diǎn)的下一條邊 Enode; typedef struct /頂點(diǎn)結(jié)點(diǎn)類型 VertexType data; /頂點(diǎn)數(shù)據(jù)域 ENode *firstedge; /指向第一條依附該頂點(diǎn)的邊 Vnode;,20

14、20/9/9,40,7.3 圖的遍歷,和樹的遍歷相似，若從圖中某頂點(diǎn)出發(fā)訪遍圖中每個(gè)頂點(diǎn)，且每個(gè)頂點(diǎn)僅訪問一次，此過程稱為圖的遍歷。 (Traversing Graph)。 但是，在圖中有回路，從圖中某一頂點(diǎn)出發(fā)訪問圖中其它頂點(diǎn)時(shí)，可能又會(huì)回到出發(fā)點(diǎn)，而圖中或許還有頂點(diǎn)沒有訪問到，因此，圖的遍歷較樹的遍歷更復(fù)雜。 圖的遍歷算法是求解圖的連通性問題、拓?fù)渑判蚝颓箨P(guān)鍵路徑等算法的基礎(chǔ)。 圖的遍歷順序有兩種：深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）。對(duì)每種搜索順序，訪問各頂點(diǎn)的順序也不是唯一的。,2020/9/9,41,7.3.1 深度優(yōu)先搜索（DFS） 1 深度優(yōu)先搜索思想 深度優(yōu)先搜索遍歷

15、類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遞歸調(diào)用包含以下操作： （1）訪問搜索到的未被訪問的鄰接點(diǎn)； （2）將此頂點(diǎn)的visited數(shù)組元素值置1； （3）搜索該頂點(diǎn)的未被訪問的鄰接點(diǎn)，若該鄰接點(diǎn)存在，則從此鄰接點(diǎn)開始進(jìn)行同樣的訪問和搜索。 深度優(yōu)先搜索DFS可描述為： （1）訪問v0頂點(diǎn)； （2）置 visitedv0=1； （3）搜索v0未被訪問的鄰接點(diǎn)w，若存在鄰接點(diǎn)w，則DFS(w)。,2020/9/9,42,遍歷過程： DFS 在訪問圖中某一起始頂點(diǎn) v 后，由 v 出發(fā)，訪問它的任一鄰接頂點(diǎn) w1；再從 w1

16、 出發(fā)，訪問與 w1鄰 接但還沒有訪問過的頂點(diǎn) w2；然后再從 w2 出發(fā)，進(jìn)行類似的訪問， 如此進(jìn)行下去，直至到達(dá)所有的鄰接頂點(diǎn)都被訪問過的頂點(diǎn) u 為止。 接著，退回一步，退到前一次剛訪問過的頂點(diǎn)，看是否還有其它沒有被訪問的鄰接頂點(diǎn)。如果有，則訪問此頂點(diǎn)，之后再從此頂點(diǎn)出發(fā)，進(jìn)行與前述類似的訪問；如果沒有，就再退回一步進(jìn)行搜索。重復(fù)上述過程，直到連通圖中所有頂點(diǎn)都被訪問過為止。,2020/9/9,43,深度優(yōu)先搜索的示例,圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相通，在訪問完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問過的頂點(diǎn)。 為了避免重復(fù)訪問，可設(shè)置一個(gè)標(biāo)志頂點(diǎn)是否被訪問過的輔

17、助數(shù)組 visited ，它的初始狀態(tài)為 0，在圖的遍歷過程中，一旦某一個(gè)頂點(diǎn) i 被訪問，就立即讓 visited i 為 1，防止它被多次訪問。,2020/9/9,44,對(duì)上圖，深度優(yōu)先搜索遍歷的順序（之一）為： v1 v2v4 v8 v5v6v3v7。,圖7-10 深度優(yōu)先搜索,2020/9/9,45,深度優(yōu)先搜索算法： int visitedMAX_VERTEX_NUM; void DFS(ALGraph G, int v) ArcNode *p; printf(%c,G.verticesv.data); visitedv=1; p=G.verticesv.firstarc; whil

18、e (p) if (!visitedp-adjvex) DFS(G,p-adjvex); p=p-nextarc; /從第v個(gè)頂點(diǎn)出發(fā)DFS,2020/9/9,46,整個(gè)圖的DFS遍歷 void DFSTraverse(ALGraph G) for (int v=0;vG.vexnum;+v) visitedv=0; for (v=0;vG.vexnum;+v) if (!visitedv) DFS(G,v); 對(duì)于連通圖，從一個(gè)頂點(diǎn)出發(fā)，調(diào)用DFS函數(shù)即可將所有頂點(diǎn)都遍歷到。,2020/9/9,47,7.3.2 廣度優(yōu)先搜索（BFS） 1 廣度優(yōu)先搜索思想 廣度優(yōu)先搜索遍歷類似于樹的按層次遍

19、歷。 對(duì)于無向連通圖，廣度優(yōu)先搜索是從圖的某個(gè)頂點(diǎn)v0出發(fā)，在訪問v0之后，依次搜索訪問v0的各個(gè)未被訪問過的鄰接點(diǎn)w1，w2，。然后順序搜索訪問w1的各未被訪問過的鄰接點(diǎn)，w2的各未被訪問過的鄰接點(diǎn)，。即從v0開始，由近至遠(yuǎn)，按層次依次訪問與v0有路徑相通且路徑長度分別為1，2，的頂點(diǎn)，直至連通圖中所有頂點(diǎn)都被訪問一次。 廣度優(yōu)先搜索的順序不是唯一的，例如圖7-10 (a) 連通圖的廣度優(yōu)先搜索遍歷順序可為v1，v2，v3，v4，v5，v6，v7，v8 也可為v1，v3，v2，v7，v6，v5，v4，v8。,2020/9/9,48,1 廣度優(yōu)先搜索思想 設(shè)圖G的初態(tài)是所有頂點(diǎn)均未訪問，在G

20、中任選一頂點(diǎn)i作為初始點(diǎn)，則廣度優(yōu)先搜索的基本思想是： （1）從圖中的某個(gè)頂點(diǎn)V出發(fā)，訪問之；并將其訪問標(biāo)志置為已被訪問，即visitedi=1； （2）依次訪問頂點(diǎn)V的各個(gè)未被訪問過的鄰接 點(diǎn)，將V的全部鄰接點(diǎn)都訪問到； （3）分別從這些鄰接點(diǎn)出發(fā)，依次訪問它們的未被訪問過的鄰接點(diǎn)，并使“先被訪問的頂 點(diǎn)的鄰接點(diǎn)”先于“后被訪問的頂點(diǎn)的鄰接 點(diǎn)”被訪問，直到圖中所有已被訪問過的頂 點(diǎn)的鄰接點(diǎn)都被訪問到。 依此類推，直到圖中所有頂點(diǎn)都被訪問完為止 。,2020/9/9,49,廣度優(yōu)先搜索在搜索訪問一層時(shí)，需要記住已被訪問的頂點(diǎn)，以便在訪問下層頂點(diǎn)時(shí)，從已被訪問的頂點(diǎn)出發(fā)搜索訪問其鄰接點(diǎn)。所以在

21、廣度優(yōu)先搜索中需要設(shè)置一個(gè)隊(duì)列Queue，使已被訪問的頂點(diǎn)順序由隊(duì)尾進(jìn)入隊(duì)列。在搜索訪問下層頂點(diǎn)時(shí)，先從隊(duì)首取出一個(gè)已被訪問的上層頂點(diǎn)，再從該頂點(diǎn)出發(fā)搜索訪問它的各個(gè)鄰接點(diǎn)。,廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹,廣度優(yōu)先搜索的示例,2020/9/9,50,廣度優(yōu)先搜索過程可描述為： （1）f=0;r=0; /隊(duì)列初始化，空隊(duì)列；f-隊(duì)首指針，r-隊(duì)尾指針 （2）訪問v0; （3）visitedv0=1; （4）insert(Queue,f,r,v0); /v0進(jìn)入隊(duì)尾 （5）while f0 do (i)delete(Queue,f,r,x); /隊(duì)首元素出隊(duì)并賦于x (ii)對(duì)所有x的鄰接點(diǎn)w

22、 if visitedw=0 then （a）訪問w; （b）visitedw=1; （c）insert(Queue,f,r,w); /w進(jìn)隊(duì)列,2020/9/9,51,以鄰接表為存儲(chǔ)結(jié)構(gòu)，廣度優(yōu)先搜索遍歷算法如下： #define MAXV void bfs(ALGraph *g,int v) ArcNode *p; int queueMAXV; /定義存放隊(duì)列的數(shù)組 int visitedMAXV； /定義存放結(jié)點(diǎn)的訪問標(biāo)志的數(shù)組 int f=0,r=0,x,i; /隊(duì)列頭尾指針初始化，把隊(duì)列置空 for(i=0,in;i+) /訪問標(biāo)志數(shù)組初始化 visitedi=0; printf(“

23、d”,v); /訪問初始頂點(diǎn)v visitedv=1; /置已訪問標(biāo)記 r=(r+1)MAXV; queuer=v; /v進(jìn)隊(duì) while(f!=r) /若隊(duì)列不空時(shí)循環(huán) f=(f+1)MAXV; x=queuetf; /出隊(duì)并賦給x p=g-adjlistx.firstarc; /找與頂點(diǎn)x鄰接的第一個(gè)頂點(diǎn),2020/9/9,52,p=g-adjlistx.firstarc; /找與頂點(diǎn)x鄰接的第一個(gè)頂點(diǎn) while(p!=NULL) if (visitedp-adjvex=0) /若當(dāng)前鄰接點(diǎn)未被訪問 visitedp-adjvex=l; /置該頂點(diǎn)已被訪問的標(biāo)志 printf(“d”，p

24、-adjvex); /訪問該頂點(diǎn) r=(r+1)MAXV; queuer=p-adjvex; /該頂點(diǎn)進(jìn)隊(duì) p=p-nextarc; /找下一個(gè)鄰接點(diǎn) / w進(jìn)隊(duì)列,2020/9/9,53,算法分析：,如果使用鄰接表表示圖，則循環(huán)的總時(shí)間代價(jià)為 d0 + d1 + + dn-1 = O(e)，其中的 di 是頂點(diǎn) i 的度。 如果使用鄰接矩陣，則對(duì)于每一個(gè)被訪問過的頂點(diǎn)，循環(huán)要檢測(cè)矩陣中的 n 個(gè)元素，總的時(shí)間代價(jià)為O(n2)。,2020/9/9,54,7.4 最小生成樹,1. 生成樹 在一個(gè)無向連通圖G中，其所有頂點(diǎn)和遍歷該圖經(jīng)過的所有邊所構(gòu)成的子圖G 稱做圖G的生成樹。一個(gè)圖可以有多個(gè)生成

25、樹，從不同的頂點(diǎn)出發(fā)，采用不同的遍歷順序，遍歷時(shí)所經(jīng)過的邊也就不同，例如圖7-12的(b) 和(c) 為圖7-12 (a) 的兩棵生成樹。其中 (b) 是通過DFS得到的，稱為深度優(yōu)先生成樹；(c) 是通過BFS得到的，稱為廣度優(yōu)先生成樹。,圖7-12 生成樹,2020/9/9,55,按照生成樹的定義，n 個(gè)頂點(diǎn)的連通網(wǎng)絡(luò)的生成樹有 n 個(gè)頂點(diǎn)、n-1 條邊。而所有包含n-1 條邊及n個(gè)頂點(diǎn)的連通圖都是無回路的樹，所以生成樹是連通圖中的極小連通子圖. 由于使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點(diǎn)出發(fā)，也可能得到不同的生成樹。如深度優(yōu)先生成樹、廣度優(yōu)先生成樹 在圖論中，常常將樹

26、定義為一個(gè)無回路連通圖。 對(duì)于一個(gè)帶權(quán)的無向連通圖，其每個(gè)生成樹所有邊上的權(quán)值之和可能不同，我們把所有邊上權(quán)值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實(shí)際應(yīng)用。例如，通訊線路鋪設(shè)造價(jià)最優(yōu)問題就是一個(gè)最小生成樹問題。,2020/9/9,56,假設(shè)把n個(gè)城市看作圖的n個(gè)頂點(diǎn)，邊表示兩個(gè)城市之間的線路，每條邊上的權(quán)值表示鋪設(shè)該線路所需造價(jià)。鋪設(shè)線路連接n個(gè)城市，但不形成回路，這實(shí)際上就是圖的生成樹，而以最少的線路鋪設(shè)造價(jià)連接各個(gè)城市，即求線路鋪設(shè)造價(jià)最優(yōu)問題，實(shí)際上就是在圖的生成樹中選擇權(quán)值之和最小的生成樹。構(gòu)造最小生成樹的算法有很多，下面分別介紹克魯斯卡爾(Kruskal)算法和

27、普里姆(Prim)算法。,7.4.1 克魯斯卡爾(Kruskal)算法 克魯斯卡爾算法是一種按權(quán)值遞增的次序選擇合適的邊來構(gòu)造最小生成樹的方法。,2020/9/9,57,算法的基本思想： 在圖中任取一個(gè)頂點(diǎn)K作為開始點(diǎn)，令U=k，W=V-U，其中V為圖中所有頂點(diǎn)集，然后找一個(gè)頂點(diǎn)在U中，另一個(gè)頂點(diǎn)在W中的邊中最短的一條，找到后，將該邊作為最小生成樹的樹邊保存起來，并將該邊頂點(diǎn)全部加入U(xiǎn)集合中，并從W中刪去這些頂點(diǎn)，然后重新調(diào)整U中頂點(diǎn)到W中頂點(diǎn)的距離, 使之保持最小，再重復(fù)此過程，直到W為空集止。 假設(shè)G=（V，E）是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向連通圖，T= (U，TE)是G的最小生成樹，其中U

28、是T的頂點(diǎn)集，TE是T的邊集，則構(gòu)造最小生成樹的過程如下： (1) 置U的初值等于V，TE的初值為空集； (2) 按權(quán)值從小到大的順序依次選取圖G中的邊，若選取的邊未使生成樹T形成回路，則加入TE；若選取的邊使生成樹T形成回路，則將其舍棄。循環(huán)執(zhí)行(2)，直到TE中包含(n-1)條邊為止。,2020/9/9,58,應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程:,2020/9/9,59,為實(shí)現(xiàn)克魯斯卡爾算法需要設(shè)置一維輔助數(shù)組E，按權(quán)值從小到大的順序存放圖的邊，數(shù)組的下標(biāo)取值從0到e-1（e為圖G邊的數(shù)目）。 假設(shè)數(shù)組E存放圖G中的所有邊，且邊已按權(quán)值從小到大的順序排列。n為圖G的頂點(diǎn)個(gè)數(shù)，e為圖G的

29、邊數(shù)?？唆斔箍査惴ㄈ缦拢?#define MAXE #define MAXV typedef struct int vex1; /邊的起始頂點(diǎn) int vex2; /邊的終止頂點(diǎn) int weight; /邊的權(quán)值 Edge;,2020/9/9,60,Void kruskal(Edge E,int n,int e) int i,j,m1,m2,sn1,sn2,k; int vsetMAXV; for(i=0;in;i+) /初始化輔助數(shù)組 for(i=0;in;i+) /初始化輔助數(shù)組 vseti=i; k=1; /表示當(dāng)前構(gòu)造最小生成樹的第k條邊，初值為1 j=0; /E中邊的下標(biāo)，初值為

30、0 while(ke) /生成的邊數(shù)小于e時(shí)繼續(xù)循環(huán) ml=Ej.vex1;m2=Ej.vex2;/取一條邊的兩個(gè)鄰接點(diǎn) sn1=vsetm1;sn2=vsetm2; /分別得到兩個(gè)頂點(diǎn)所屬的集合編號(hào) if(sn1!=sn2) /兩頂點(diǎn)分屬于不同的集合，該邊是最小生成樹的一條邊,2020/9/9,61, printf(“(m1，m2)：dn”,Ej.weight); k+; /生成邊數(shù)增l for(i=0;in;i+) /兩個(gè)集合統(tǒng)一編號(hào) if (vseti= /集合編號(hào)為sn2的改為sn1 vseti=sn1; j+; /掃描下一條邊 ,如果給定帶權(quán)無向連通圖G有e條邊，且邊已經(jīng)按權(quán)值遞增的

31、次序存放在數(shù)組E中，則用克魯斯卡爾算法構(gòu)造最小生成樹的時(shí)間復(fù)雜度為O (e)?？唆斔箍査惴ǖ臅r(shí)間復(fù)雜度與邊數(shù)e有關(guān)，該算法適合于求邊數(shù)較少的帶權(quán)無向連通圖的最小生成樹。,2020/9/9,62,7.4.2 普里姆(Prim)算法 普里姆算法的基本思想：普里姆算法是另一種構(gòu)造最小生成樹的算法，它是按逐個(gè)將頂點(diǎn)連通的方式來構(gòu)造最小生成樹的。 從連通網(wǎng)絡(luò) N = V, E 中的某一頂點(diǎn) u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點(diǎn)加入到生成樹的頂點(diǎn)集合U中。以后每一步從一個(gè)頂點(diǎn)在U中，而另一個(gè)頂點(diǎn)不在U中的各條邊中選擇權(quán)值最小的邊(u, v),把該邊加入到生成樹的邊集TE中，

32、把它的頂點(diǎn)加入到集合U中。如此重復(fù)執(zhí)行，直到網(wǎng)絡(luò)中的所有頂點(diǎn)都加入到生成樹頂點(diǎn)集合U中為止。,2020/9/9,63,假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向連通圖，T(U，TE)是G的最小生成樹，其中U是T的頂點(diǎn)集，TE是T的邊集，則構(gòu)造G的最小生成樹T的步驟如下： （1）初始狀態(tài)，TE為空，U=v0，v0V； （2）在所有uU，vV-U的邊(u，v) E中找一條代價(jià)最小的邊(u，v)并入TE，同時(shí)將v并入U(xiǎn)； 重復(fù)執(zhí)行步驟（2）n-1次，直到U=V為止。 在普里姆算法中，為了便于在集合U和(V-U)之間選取權(quán)值最小的邊，需要設(shè)置兩個(gè)輔助數(shù)組closest和lowcost，分別用于存放

33、頂點(diǎn)的序號(hào)和邊的權(quán)值。 對(duì)于每一個(gè)頂點(diǎn)vV-U，closestv為U中距離v最近的一個(gè)鄰接點(diǎn)，即邊 (v，closestv) 是在所有與頂點(diǎn)v相鄰、且其另一頂點(diǎn)jU的邊中具有最小權(quán)值的邊，其最小權(quán)值為lowcostv，即lowcostv=costvclosestv，,2020/9/9,64,采用鄰接表作為存儲(chǔ)結(jié)構(gòu)： 設(shè)置一個(gè)輔助數(shù)組closedge： lowcost域 存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹外各頂點(diǎn)的各邊上的當(dāng)前最小權(quán)值； adjvex域 記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。,設(shè)置一個(gè)輔助數(shù)組closedge： lowcost域：存放在V-U中各個(gè)頂點(diǎn)到集

34、合U中的當(dāng)前最小權(quán)值； adjvex域： 記錄該邊所依附的在U中的頂點(diǎn),2020/9/9,65,若選擇從頂點(diǎn)0出發(fā)，即u0 = 0，則輔助數(shù)組的兩個(gè)域的初始狀態(tài)為： 然后反復(fù)做以下工作： 在 closedge i中選擇 adjvex 0 struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; void MiniSpanTree_PRIM(MGraph G,VertexType u) int k,j,i,minCost; k=LocateVex(G,u); for (j=0;jG.vexnum;+j) if (j!=k)

35、 closedgej.adjvex=u; closedgej.lowcost=G.arcskj; ,2020/9/9,68,closedgek.lowcost=0; for (i=1;iG.vexnum;+i) k=minimum(closedge); minCost=INFINITY; for (j=0;jG.vexnum;+j) if (closedgej.lowcost minCost ,2020/9/9,69,普里姆算法中的第二個(gè)for循環(huán)語句頻度為n-1，其中包含的兩個(gè)內(nèi)循環(huán)頻度也都為n-1，因此普里姆算法的時(shí)間復(fù)雜度為O(n2)。普里姆算法的時(shí)間復(fù)雜度與邊數(shù)e無關(guān)，該算法更適合于求

36、邊數(shù)較多的帶權(quán)無向連通圖的最小生成樹。,2020/9/9,70,7.5 最短路徑,交通網(wǎng)絡(luò)中常常提出這樣的問題：從甲地到乙地之間是否有公路連通? 在有多條通路的情況下，哪一條路最短? 交通網(wǎng)絡(luò)可用帶權(quán)圖來表示。頂點(diǎn)表示城市名稱，邊表示兩個(gè)城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費(fèi)或途中所花費(fèi)的時(shí)間等。求兩個(gè)頂點(diǎn)之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。 另外，若兩個(gè)頂點(diǎn)之間沒有邊，則認(rèn)為兩個(gè)頂點(diǎn)無通路，但有可能有間接通路(從其它頂點(diǎn)達(dá)到)。 路徑上的開始頂點(diǎn)(出發(fā)點(diǎn))稱為源點(diǎn)，路徑上的最后一個(gè)頂點(diǎn)稱為終點(diǎn)，并假定討論的權(quán)值不能為負(fù)數(shù)。,2020/9/9

37、,71,最短路徑： 如果從圖中某一頂點(diǎn)(稱為源點(diǎn))到達(dá)另一頂點(diǎn)(稱為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小。 對(duì)于帶權(quán)的圖，通常把一條路徑上所經(jīng)過邊或弧上的權(quán)值之和定義為該路徑的路徑長度。從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)可能存在著多條路徑，把路徑長度最短的那條路徑稱為最短路徑，其路徑長度稱為最短路徑長度。無權(quán)圖實(shí)際上是有權(quán)圖的一種特例，我們可以把無權(quán)圖的每條邊或弧的權(quán)值看成是l，每條路徑上所經(jīng)過的邊或弧數(shù)即為路徑長度。本章討論兩種最常見的最短路徑問題。,2020/9/9,72,問題解法 邊上權(quán)值非負(fù)情形的單源最短路徑問題 Dijkstra算法 所有頂點(diǎn)之間的最短

38、路徑 Floyd算法 邊上權(quán)值非負(fù)情形的單源最短路徑問題 問題的提法： 給定一個(gè)帶權(quán)有向圖D與源點(diǎn)v，求從v到D中其它頂點(diǎn)的最短路徑。限定各邊上的權(quán)值大于或等于0。 為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點(diǎn)v到其它各頂點(diǎn)的最短路徑全部求出為止。,2020/9/9,73,7.5.1 求一頂點(diǎn)（單源點(diǎn)）到其余頂點(diǎn)的最短路徑 單源點(diǎn)最短路徑是指：給定一個(gè)出發(fā)點(diǎn)(單源點(diǎn))和一個(gè)有向網(wǎng)G=(V，E),求出源點(diǎn)到其它各頂點(diǎn)之間的最短路徑。 迪杰斯特拉(Dijkstra)在做

39、了大量觀察后,首先提出了按路徑長度遞增產(chǎn)生各頂點(diǎn)的最短路徑算法,我們稱之為迪杰斯特拉算法。 算法的基本思想是:設(shè)置并逐步擴(kuò)充一個(gè)集合S，存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S，其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長度遞增的順序逐個(gè)以V-S中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而V-S為空。,2020/9/9,74,具體做法是:設(shè)源點(diǎn)為Vl,則S中只包含頂點(diǎn)Vl，令W=V-S，則W中包含除Vl外圖中所有頂點(diǎn)，Vl對(duì)應(yīng)的距離值為0，W中頂點(diǎn)對(duì)應(yīng)的距離值是這樣規(guī)定的：若圖中有弧則Vj頂點(diǎn)的距離為此弧權(quán)值，否則為(一個(gè)很大的數(shù))，然后每次從W中的頂點(diǎn)中選一個(gè)其距離值為最小的

40、頂點(diǎn)Vm加入到S中，每往S中加入一個(gè)頂點(diǎn)Vm，就要對(duì)W中的各個(gè)頂點(diǎn)的距離值進(jìn)行一次修改。若加進(jìn)Vm做中間頂點(diǎn)，使+的值小于值，則用+代替原來Vj的距離，修改后再在W中選距離值最小的頂點(diǎn)加入到S中，如此進(jìn)行下去，直到S中包含了圖中所有頂點(diǎn)為止。,2020/9/9,75,圖7-16 帶權(quán)有向圖,設(shè)G=(V，E)是一個(gè)帶權(quán)有向圖，指定的頂點(diǎn)v0為源點(diǎn)，求v0到圖的其余各頂點(diǎn)的最短路徑。如圖7-16所示，若以頂點(diǎn)0為v0，它到其余各頂點(diǎn)的最短路徑分別為： 頂點(diǎn)0 頂點(diǎn)1：無路徑 頂點(diǎn)0 頂點(diǎn)2：最短路徑為（0，2），最短路徑長度為10 頂點(diǎn)0 頂點(diǎn)4：最短路徑為（0，4），最短路徑長度為30 頂點(diǎn)0

41、頂點(diǎn)3：最短路徑為（0，4，3），最短路徑長度為50 頂點(diǎn)0 頂點(diǎn)5：最短路徑為（0，4，3，5），最短路徑長度為60,2020/9/9,76,從以上圖7-16的最短路徑可以看出： (1) 最短路徑并不一定是經(jīng)過邊或弧數(shù)最少的路徑。如從頂點(diǎn)0到頂點(diǎn)5的路徑（0，5）長度為100，路徑（0，4，5）長度為90，路徑（0，2，3，5）長度為70，路徑（0，4，3，5）長度為60，其中最短路徑為（0，4，3，5），最短路徑長度為60。 (2) 這些最短路徑中，長度最短的路徑上只有一條弧，且它的權(quán)值在從源點(diǎn)出發(fā)的所有弧的權(quán)值中最小。如從源點(diǎn)0出發(fā)有3條弧，其中以弧的權(quán)值為最小。此時(shí)（0，2）不僅是頂點(diǎn)

42、 0到頂點(diǎn)2 的一條最短路徑，而且它在從源點(diǎn)0到其它各頂點(diǎn)的最短路徑中長度最短。 (3)按照路徑長度遞增的次序產(chǎn)生最短路徑。求得第二條最短路徑（0，4）；之后求得第三條最短路徑（0，4，3），它經(jīng)過已求出的第二條最短路徑（0，4）到達(dá)頂點(diǎn)3；求得的第四條最短路徑（0，4，3，5），經(jīng)過已求出的第三條最短路徑（0，4，3）到達(dá)頂點(diǎn)5。,2020/9/9,77,迪杰斯特拉算法的求解過程：,2020/9/9,78,圖7-17 迪杰斯特拉算法求最短路徑過程及結(jié)果,2020/9/9,79,Dijkstra算法可描述如下：,初始化： S v0 ; Dj arcs0j, j = 1, 2, , n-1; /

43、 n為圖中頂點(diǎn)個(gè)數(shù) 求出最短路徑的長度： Dk min Di , i V- S ; S S U k ; 修改： Di min Di, Dk + arcski , 對(duì)于每一個(gè) i V- S ; 判斷： 若S = V, 則算法結(jié)束，否則轉(zhuǎn)。,2020/9/9,80,狄杰斯特拉算法dijkstra，其中n為圖G的頂點(diǎn)數(shù)，v0為源點(diǎn)。 #define INF 32767 /INF表示 #define MAXV void dijkstra(int costMAXV，int n，int vO) int distMAXV，pathMAXV； int sMAXV； int mindis； int i，j，k；

44、 for(i=0;in;i+) disti=costvOi; /距離初始化 si=0; /s初始化 if (costvOiINF) /路徑初始化 pathi=vO; else pathi=-1; svO=1; /源點(diǎn)v0放入S中 for(i=1;in;i+) /重復(fù)，直到求出v0到其余所有頂點(diǎn)的最短路徑,2020/9/9,81,for(i=1;in;i+) /重復(fù)，直到求出v0到其余所有頂點(diǎn)的最短路徑 mindis=INF; k=vO; for(j=1;jn;j+) /從V-S中選取具有最小距離的頂點(diǎn)v k if(sj=0 /輸出最短路徑,2020/9/9,82,通過pathi向前回推直到v0

45、為止，可以找出從v 0到頂點(diǎn)v i的最短路徑。輸出最短路徑的算法dispath如下： void dispath(int dist,int path,int s,int n,int vO) int i,k; for(i=0;in;i+) if(si=1) /S中頂點(diǎn) k=i; printf(“d 到 d的最短路徑為:”, v0,i); while(k!=v0) printf(“d-”,k); k=pathk; printf(“d 路徑長度為:dn”,v0,disti); else printf(“d-d不存在路徑n”,i,v0); ,2020/9/9,83,在狄克斯特拉算法中，求一條最短路徑所花

46、費(fèi)的時(shí)間：從V-S中選取具有最小距離的頂點(diǎn)v k花費(fèi)時(shí)間O(n)；修改V-S中頂點(diǎn)的距離花費(fèi)時(shí)間O(n)；輸出最短路徑花費(fèi)時(shí)間O(n)。因此求出n-1條最短路徑的時(shí)間復(fù)雜度為O(n2)。,2020/9/9,84,7.5.2 每對(duì)頂點(diǎn)之間的最短路徑 頂點(diǎn)對(duì)之間的最短路徑是指：對(duì)于給定的有向網(wǎng)G=(V,E),要對(duì)G中任意一對(duì)頂點(diǎn)有序?qū)、W(VW),找出V到W的最短距離和W到V的最短距離。 解決此問題的一個(gè)有效方法是:輪流以每一個(gè)頂點(diǎn)為源點(diǎn),重復(fù)執(zhí)行迪杰斯特拉算法n次,即可求得每一對(duì)頂點(diǎn)之間的最短路徑,總的時(shí)間復(fù)雜度為O(n3)。 弗洛伊德提出了另外一個(gè)求圖中任意兩頂點(diǎn)之間最短路徑的算法，雖然其時(shí)

47、間復(fù)雜度也是 O(n3)，但其算法的形式更簡(jiǎn)單，易于理解和編程。,2020/9/9,85,弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣arcsn+1n+1來存儲(chǔ)帶權(quán)有向圖。算法的基本思想是:設(shè)置一個(gè)nxn的矩陣A(k)，其中除對(duì)角線的元素都等于0外，其它元素a(k)ij表示頂點(diǎn)i到頂點(diǎn)j的路徑長度，K表示運(yùn)算步驟。開始時(shí)，以任意兩個(gè)頂點(diǎn)之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時(shí)，路徑長度為，當(dāng)K=O時(shí), A (0)ij=arcsij 以后逐步嘗試在原路徑中加入其它頂點(diǎn)作為中間頂點(diǎn)，如果增加中間頂點(diǎn)后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：,2020

48、/9/9,86,第一步，讓所有邊上加入中間頂點(diǎn)1，取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1)， 第二步，讓所有邊上加入中間頂點(diǎn)2，取Aij與Ai2+A2j中較小的值，完成后得到A(2)，如此進(jìn)行下去，當(dāng)?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果,A(n)ij表示頂點(diǎn)i到頂點(diǎn)j的最短距離。,因此，弗洛伊德算法可以描述為: A(0)ij=arcsij; /arcs為圖的鄰接矩陣 A(k)ij=minA(k-1) ij,A(k-1) ik+A(k-1) kj 其中 k=1,2,n,2020/9/9,87,Floyd算法的基本思想： 定義一個(gè)n階方陣序列： D(-1)

49、, D(0), , D(n-1). 其中 D(-1) ij = G.arcsij； D(k) ij = min D(k-1)ij， D(k-1)ik + D(k-1)kj , k = 0,1, n-1 D(0) ij是從頂點(diǎn)vi 到vj , 中間頂點(diǎn)是v0的最短路徑的長度, D(k) ij是從頂點(diǎn)vi 到vj , 中間頂點(diǎn)的序號(hào)不大于k的最短路徑長度, D(n-1)ij是從頂點(diǎn)vi 到vj 的最短路徑長度。,2020/9/9,88,Floyd算法允許圖中有帶負(fù)權(quán)值的邊，但不許有包含帶負(fù)權(quán)值的邊組成的回路。 本章給出的求解最短路徑的算法不僅適用于帶權(quán)有向圖，對(duì)帶權(quán)無向圖也可以適用。因?yàn)閹?quán)無向圖

50、可以看作是有往返二重邊的有向圖，只要在頂點(diǎn)vi 與vj 之間存在無向邊(vi , vj )，就可以看成是在這兩個(gè)頂點(diǎn)之間存在權(quán)值相同的兩條有向邊和。,2020/9/9,89,弗洛伊德算法floyd如下： #define INF 32767 /INF表示 #define MAXV void floyd(int costMAXV，int n) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for(i=0;i(Aik+Akj),2020/9/9,90,if(Aij(Aik+Akj) Aij=Aik+Akj; pathij=k; dispath(A,path,n); /

51、輸出最短路徑 以下是輸出最短路徑的算法dispath，其中ppath（）函數(shù)在path中遞歸輸出從頂點(diǎn)vi到vj的最短路徑。 void ppath(int pathMAXV,int i,int j) int k; k=pathij; if(k=-1) /pathij=-1時(shí),頂點(diǎn)vi和vj之間無中間頂點(diǎn) return; ppath(path,i,k); printf(“d,”,k); ppath(path,k,j); ,2020/9/9,91,void dispath(int AMAXV,int pathMAXV,int n) int i,j; for(i=0;in;i+) for(j=0;j

52、n;j+) if(Aij=INF) if(i!=j) printf(“從頂點(diǎn)d到頂點(diǎn)d沒有路徑n”,i,j); else printf(“從頂點(diǎn)d到頂點(diǎn)d路徑為:”,i,j);； printf(“d ,”,i); ppath(path,i,j); printf(“d”,j); printf(“路徑長度為:dn”,Aij); 弗洛伊德算法包含一個(gè)三重循環(huán)，其時(shí)間復(fù)雜度為O(n3)。,2020/9/9,92,1.拓?fù)渑判?通常我們把計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都當(dāng)成一個(gè)工程，一個(gè)大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動(dòng)。這些活動(dòng)完成時(shí)，整個(gè)工程也就完成了。 例如，計(jì)算機(jī)專業(yè)

53、學(xué)生的課程開設(shè)可看成是一個(gè)工程，每一門課程就是工程中的活動(dòng)，圖7-21給出了若干門所開設(shè)的課程，其中有些課程的開設(shè)有先后關(guān)系，有些則沒有先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設(shè)，如開設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學(xué)完程序設(shè)計(jì)基礎(chǔ)及離散數(shù)學(xué)，而開設(shè)離散數(shù)學(xué)則必須先并行學(xué)完高等數(shù)學(xué)、程序設(shè)計(jì)基礎(chǔ)課程。,7.6 拓?fù)渑判?2020/9/9,93,圖7-21 課程名稱及相應(yīng)的課程安排次序,圖7-22 課程安排的AOV網(wǎng),在圖7-22中，我們用一種有向圖來表示課程開設(shè)，在這種有向圖中，頂點(diǎn)表示活動(dòng)，有向邊表示活動(dòng)的優(yōu)先關(guān)系，這有向圖叫做頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)(Actire On Vertices)簡(jiǎn)稱為AOV

54、網(wǎng)。,2020/9/9,94,AOV網(wǎng)Activity On Vertex Network 用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間 的優(yōu)先關(guān)系的有向圖，稱為頂點(diǎn)表 示活動(dòng)的網(wǎng)。 AOV 網(wǎng)中不能有回路 拓?fù)渑判颍?假設(shè)G=(V，E)是一個(gè)具有n個(gè)頂點(diǎn)的有向圖，V中頂點(diǎn)序列vl，v2，vn稱做一個(gè)拓?fù)湫蛄?Topological Order)，當(dāng)且僅當(dāng)該頂點(diǎn)序列滿足下列條件：若在有向圖G中存在從頂點(diǎn)vi到vj的一條路徑，則在頂點(diǎn)序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。通常，在AOV網(wǎng)中，將所有活動(dòng)排列成一個(gè)拓?fù)湫蛄械倪^程叫做拓?fù)渑判?Topological Sort)。,2020/9/9,95,由于AOV網(wǎng)

55、中有些活動(dòng)之間沒有次序要求，它們?cè)谕負(fù)湫蛄械奈恢每梢允侨我獾?，因此拓?fù)渑判虻慕Y(jié)果不唯一。 對(duì)圖7-22進(jìn)行拓?fù)渑判?，可得一個(gè)拓?fù)湫蛄校?C1，C3，C2，C4，C7，C6，C5 也可得到另一個(gè)拓?fù)湫蛄校?C2，C7，C1，C3，C4，C5，C6 還可以得到其它的拓?fù)湫蛄?。學(xué)生按照任何一個(gè)拓?fù)湫蛄卸伎梢酝瓿伤蟮娜空n程學(xué)習(xí)。 在AOV網(wǎng)中不應(yīng)該出現(xiàn)有向環(huán)。因?yàn)榄h(huán)的存在意味著某項(xiàng)活動(dòng)將以自己為先決條件，顯然無法形成拓?fù)湫蛄小?判定網(wǎng)中是否存在環(huán)的方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點(diǎn)都出現(xiàn)在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)中一定不存在環(huán)。,2020/9/9,96,進(jìn)行拓?fù)渑判虻?/p>

56、方法： 輸入AOV網(wǎng)絡(luò)。令 n 為頂點(diǎn)個(gè)數(shù)。 在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn), 并輸出之; 從圖中刪去該頂點(diǎn), 同時(shí)刪去所有它發(fā)出的有向邊; 重復(fù)以上 、 步, 直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬?，拓?fù)渑判蛲瓿桑换驁D中還有未輸出的頂點(diǎn)，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。,2020/9/9,97,拓?fù)渑判虻倪^程,2020/9/9,98,最后得到的拓?fù)溆行蛐蛄袨?C4 , C0 , C3 , C2 , C1 , C5 。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對(duì)于本來沒有這種關(guān)系的頂點(diǎn)，如C4和C2，也

57、排出了先后次序關(guān)系。,2020/9/9,99,在實(shí)現(xiàn)拓?fù)渑判虻乃惴ㄖ校捎绵徑颖碜鳛橛邢驁D的存儲(chǔ)結(jié)構(gòu)，每個(gè)頂點(diǎn)設(shè)置一個(gè)單鏈表，每個(gè)單鏈表有一個(gè)表頭結(jié)點(diǎn)，在表頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域count，這些表頭結(jié)點(diǎn)構(gòu)成一個(gè)數(shù)組，表頭結(jié)點(diǎn)定義如下： typedef struct /表頭結(jié)點(diǎn) Vertex data; /頂點(diǎn)信息 int count; /存放頂點(diǎn)入度 ArcNode *firstarc; /指向第一條弧 Vnode;,在執(zhí)行拓?fù)渑判虻倪^程中，當(dāng)某個(gè)頂點(diǎn)的入度為零(沒有前驅(qū)頂點(diǎn))時(shí)，就將此頂點(diǎn)輸出，同時(shí)將該頂點(diǎn)的所有后繼頂點(diǎn)的入度減1，相當(dāng)于刪除所有以該頂點(diǎn)為尾的弧。為了避免重復(fù)檢測(cè)頂點(diǎn)的入度是否為零，需要設(shè)立一個(gè)棧來存放入度為零的頂點(diǎn)。執(zhí)行拓?fù)渑判虻乃惴ㄈ缦拢?2020/9/9,100,void topsort(VNode adj,int n) int i,j; int stackMAXV,top=0; /棧stack的指針為top ArcNode *p; for(i=0;i0) /棧不為空 i=stacktop; top-; /頂點(diǎn)vi出棧 printf(“d”,i); /輸出vi p=adji.firstarc; /指向以vi為弧尾的第一條弧 while(p!=