數(shù)據(jù)結(jié)構(gòu)和算法分析第6講-圖課件

1、Chapter 6Graphs圖的類(lèi)型定義 n(n0)個(gè)元素的有限集合基 本 術(shù) 語(yǔ) 圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集VR構(gòu) 成的數(shù)據(jù)結(jié)構(gòu) Graph = (V , VR )其中:VR| v,wV 且 P(v,w)表示從 v 到 w 的一條弧，并稱(chēng) v 為弧尾，w 為弧頭 謂詞 P(v,w) 定義了弧 的意義或信息 由于“弧”是有方向的，因此稱(chēng)由 頂點(diǎn)集和弧集構(gòu)成的圖為有向圖 AB E C D 例如: G1 = (V1, VR1 )其中:V1=A, B, C, D, EVR1=, , , 若有VR,必有VR,則稱(chēng)(v,w) 為頂點(diǎn)v和頂點(diǎn)w之間存在一條邊 B CA D F E由頂點(diǎn)集和邊集構(gòu)成的圖

2、稱(chēng)作無(wú)向圖例如: G2=(V2,VR2 )V2=A, B, C, D, E, FVR2=, , , , , , 名詞和術(shù)語(yǔ)網(wǎng)、子圖 完全圖、稀疏圖、稠密圖鄰接點(diǎn)、度、入度、出度路徑、路徑長(zhǎng)度、簡(jiǎn)單路徑、簡(jiǎn)單回路連通圖、連通分量、強(qiáng)連通圖、強(qiáng)連通分量生成樹(shù)、生成森林關(guān)節(jié)點(diǎn)、重連通圖重連通分量、連通度AEFBBC設(shè)圖G=( V,VR )和圖G=( V, VR ),且VV, VRVR, 則稱(chēng) G 為 G 的子圖ABECF1597211132弧或邊帶權(quán)的圖分別稱(chēng)作有向網(wǎng)或無(wú)向網(wǎng)假設(shè)圖中有 n 個(gè)頂點(diǎn)，e 條邊，則 含有 e=n(n-1)/2 條邊的無(wú)向圖稱(chēng)作無(wú)向完全圖 含有 e=n(n-1) 條弧的有

3、向圖稱(chēng)作有向完全圖 若邊或弧的個(gè)數(shù) enlogn，則稱(chēng)作稀疏圖，否則稱(chēng)作稠密圖 假若頂點(diǎn)v 和頂點(diǎn)w 之間存在一條邊，則稱(chēng)頂點(diǎn)v和w互為鄰接點(diǎn)，邊(v,w) ID(B) = 3ID(A) = 2和頂點(diǎn)v和w相關(guān)聯(lián) 和頂點(diǎn)v 關(guān)聯(lián)的邊的數(shù)目定義為頂點(diǎn)的度ACDFEB頂點(diǎn)的出度: 以頂點(diǎn)v為弧尾的弧的數(shù)目ABECF有向圖頂點(diǎn)的入度: 以頂點(diǎn)v為弧頭的弧的數(shù)目頂點(diǎn)的度(TD)=出度(OD)+入度(ID)ID(B) = 2OD(B) = 1TD(B) = 3設(shè)圖G=(V,VR)中的一個(gè)頂點(diǎn)序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,則稱(chēng)從頂點(diǎn)u 到頂點(diǎn)w

4、 之間存在一條路徑。路徑上邊的數(shù)目稱(chēng)作路徑長(zhǎng)度ABECF長(zhǎng)度為3的路徑A,B,C,FABECF簡(jiǎn)單路徑:序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑簡(jiǎn)單回路:序列中第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑若圖G中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱(chēng)此圖為連通圖若無(wú)向圖為非連通圖，則圖中各個(gè)極大連通子圖稱(chēng)作此圖的連通分量BACDFEBACDFE 若任意兩個(gè)頂點(diǎn)之間都存在一條有向路徑，則稱(chēng)此有向圖為強(qiáng)連通圖,ABECFABECF對(duì)有向圖， 否則，其各個(gè)強(qiáng)連通子圖稱(chēng)作它的強(qiáng)連通分量假設(shè)一個(gè)連通圖有n個(gè)頂點(diǎn)和e條邊，其中n-1 條邊和n個(gè)頂點(diǎn)構(gòu)成一個(gè)極小連通子圖，稱(chēng)該極小連通子圖為此連通圖的生成樹(shù)對(duì)非連通圖，則稱(chēng)由各個(gè)連通分量

5、的生成樹(shù)的集合為此非連通圖的生成森林BACDFE 沒(méi)有關(guān)節(jié)點(diǎn)的連通圖被稱(chēng)為重連通圖 若連通圖中的某個(gè)頂點(diǎn)和其相關(guān)聯(lián)的邊被刪去之后，該連通圖被分割成兩個(gè)或兩個(gè)以上的連通分量，則稱(chēng)此頂點(diǎn)為關(guān)節(jié)點(diǎn) 一個(gè)連通圖G如果不是重連通圖，那么它可以包括幾個(gè)重連通分量 若依次刪除一個(gè)連通圖中的 1, 2, , k-1個(gè)頂點(diǎn)后,該圖仍連通,刪除第k個(gè)頂點(diǎn)后該圖成為不連通的,則稱(chēng)該圖的連通度為k結(jié)構(gòu)的建立和銷(xiāo)毀插入或刪除頂點(diǎn)對(duì)鄰接點(diǎn)的操作對(duì)頂點(diǎn)的訪(fǎng)問(wèn)操作頂點(diǎn)的遍歷插入和刪除弧基本操作CreatGraph(&G, V, VR): /按定義(V, VR) 構(gòu)造圖DestroyGraph(&G): /銷(xiāo)毀圖結(jié)構(gòu)的建立和銷(xiāo)

6、毀對(duì)頂點(diǎn)的訪(fǎng)問(wèn)操作LocateVex(G, u); /若G中存在頂點(diǎn)u，則返回該頂點(diǎn)在 /圖中“位置”；否則返回其它信息GetVex(G, v); /返回 v 的值PutVex(&G, v, value); /對(duì) v 賦值value對(duì)鄰接點(diǎn)的操作FirstAdjVex(G, v); /返回v的“第一個(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)，則 /返回“空”插入或刪除頂點(diǎn)InsertVex(&G, v); /在圖G中增添新頂點(diǎn)vDeleteVex(&G, v); /刪除G

7、中頂點(diǎn)v及其相關(guān)的弧插入和刪除弧InsertArc(&G, v, w); /在G中增添弧，若G是無(wú)向的， /則還增添對(duì)稱(chēng)弧DeleteArc(&G, v, w); /在G中刪除弧，若G是無(wú)向的， /則還刪除對(duì)稱(chēng)弧遍 歷DFSTraverse(G, v, Visit(); /從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每 /個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次BFSTraverse(G, v, Visit(); /從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每 /個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次圖的存儲(chǔ)表示一、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示二、圖的鄰接表存儲(chǔ)表示四、有向圖的十字鏈表存儲(chǔ)表示 五、無(wú)向圖的鄰接多重表存儲(chǔ)

8、表示三、圖的逆鄰接表存儲(chǔ)表示Aij=0 (i,j)VR1 (i,j)VR圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示BACDFE定義:矩陣的元素為無(wú)向圖的鄰接矩陣是對(duì)稱(chēng)矩陣有向圖的鄰接矩陣為非對(duì)稱(chēng)矩陣ABECD在有向圖中, 統(tǒng)計(jì)第 i 行 1 的個(gè)數(shù)可得頂點(diǎn) i 的出度，統(tǒng)計(jì)第 j 列 1 的個(gè)數(shù)可得頂點(diǎn) j 的入度在無(wú)向圖中, 統(tǒng)計(jì)第 i 行 (列) 1 的個(gè)數(shù)可得頂點(diǎn)i 的度網(wǎng)（邊或弧帶權(quán)值的圖）的數(shù)組(鄰接矩陣)存儲(chǔ)表示如下0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE圖的鄰接表存儲(chǔ)表示 0 1 2 3 4有向圖的鄰接表1 4230 12 A B

9、 C D EABECD可見(jiàn)，在有向圖的鄰接表中不易找到指向該頂點(diǎn)的弧ABECD在有向圖的鄰接表中，對(duì)每個(gè)頂點(diǎn)，鏈接的是指向該頂點(diǎn)的弧圖的逆鄰接表存儲(chǔ)表示 A B C D E 033420012341有向圖的十字鏈表存儲(chǔ)表示 弧的結(jié)點(diǎn)結(jié)構(gòu)弧尾頂點(diǎn)位置 弧頭頂點(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 *hlink, *tlink; VexNode;頂點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)頂點(diǎn)信息數(shù)據(jù) 指向該頂點(diǎn)的第一條入弧指向該頂

10、點(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)(表頭向量) int vexnum, arcnum; /有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph;有向圖的結(jié)構(gòu)表示(十字鏈表)對(duì)右邊所示的有向圖G,十字鏈表表示如下:無(wú)向圖的鄰接多重表存儲(chǔ)表示typedef struct Ebox VisitIf mark; / 訪(fǎng)問(wèn)標(biāo)記 int ivex, jvex; /該邊依

11、附的兩個(gè)頂點(diǎn)的位置 struct EBox *ilink, *jlink; InfoType *info; / 該邊信息指針 EBox;邊的結(jié)構(gòu)表示typedef struct / 鄰接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;頂點(diǎn)的結(jié)構(gòu)表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一條依附該頂點(diǎn)的邊 VexBox;無(wú)向圖的結(jié)構(gòu)表示對(duì)右邊所示的無(wú)向圖G,鄰接多重表表示如下:圖的遍歷深度優(yōu)先遍歷DFS (Depth First

12、Search)廣度優(yōu)先遍歷BFS (Breadth First Search)深度優(yōu)先遍歷DFS(Depth First Search)深度優(yōu)先遍歷的示例前進(jìn)回退ACDEGBFIHACDEGBFIH123456789123456789深度優(yōu)先遍歷過(guò)程 深度優(yōu)先生成樹(shù)廣度優(yōu)先遍歷BFS(Breadth First Search)廣度優(yōu)先遍歷的示例ACDEGBFIHACDEGBFH123456789123456789廣度優(yōu)先遍歷過(guò)程 廣度優(yōu)先生成樹(shù)Ivoid traverse ( int n, Graph g ) for ( v = 0; v n; v+ ) visitedv = false; f

13、or ( v = 0; v n; v+ ) if ( !visitedv ) dfs (v, g ) 或 bfs (v ,g );void dfs ( int v, Graph g ) cout =0; w=NextAdjVex(g,v,w)if(!visitedw)dfs(w,g) void bfs ( int v, Graph g ) cout =0; w=NextAdjVex(g,v,w) if ( !visitedw ) cout GetVex(g, w); EnQueue ( q, w); visitedw = true; ;最小代價(jià)生成樹(shù)(minimum cost spanning

14、 tree) 假設(shè)要在 n 個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通 n 個(gè)城市只需要修建 n-1 條線(xiàn)路，如何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？問(wèn)題 構(gòu)造網(wǎng)的一棵最小生成樹(shù)，即： 在 e 條帶權(quán)的邊中選取n-1條邊（不構(gòu)成回路），使“權(quán)值之和”為最小該問(wèn)題等價(jià)于構(gòu)造最小生成樹(shù)的準(zhǔn)則必須使用且僅使用該網(wǎng)絡(luò)中的n-1 條邊來(lái)聯(lián)結(jié)網(wǎng)絡(luò)中的 n 個(gè)頂點(diǎn)不能使用產(chǎn)生回路的邊各邊上的權(quán)值的總和達(dá)到最小算法二：克魯斯卡爾算法 (Kruskal) 算法一：普里姆算法 (Prim)普里姆算法的基本思想 1.取圖中任意一個(gè)頂點(diǎn) v 作為 生成樹(shù)的根，之后往生成樹(shù) 上添加新的頂點(diǎn) w 2.在生成樹(shù)的構(gòu)造過(guò)程中，圖中 n

15、 個(gè)頂點(diǎn)分屬兩個(gè)集合：已落在生成樹(shù)上的頂點(diǎn)集 U 和尚未落在生成樹(shù)上的頂點(diǎn)集V-U ，則應(yīng)在所有連通U中頂點(diǎn)和V-U中頂點(diǎn)的邊中選取權(quán)值最小的邊(v,w)這里v屬于V-U，w屬于UUV-U 3.之后繼續(xù)往生成樹(shù)上添加頂 點(diǎn)，直至生成樹(shù)上含有 n-1 個(gè)頂點(diǎn)為止abcdegf195141827168213ae12dcbgf7148531621所得生成樹(shù)權(quán)值和= 14+8+3+5+16+21 = 67Template int MinVerTex(const Algraph&g,int *adjVex) /返回W,邊為連接V-U到U的最小權(quán)值的邊 int w=-1; int v; for(v=0;

16、v0 w=v; break; for(v+; v0 & g.GetWeight(v,adjVerv g.GetWeight(w,adjVerw) w=v; return w; Template void MinSpanTreeprim(const Algraph&g,int u0) /從u0出發(fā)構(gòu)造網(wǎng)G的最小代價(jià)生成樹(shù) assert(u0)=0&u0g.NumVex(); int *adjVex; int u, v,w; adjVex=new intg.NumVex() for(v=0; vg.NumVer(); v+) if (v!=u0) adjVexv=u0; g.SetTag(v,UN

17、VISITED); else g.SetTag(v,VISITED); adjVexv=u0; /初始化輔助數(shù)組adjVex,并對(duì)頂點(diǎn)作標(biāo)志 for(u=1; ug.NumVer(); v+) /選擇生成樹(shù)的其余g.NumVex()-1個(gè)頂點(diǎn) w= MinVerTex(g,*adjVex); if ( w=-1) return countadjVexw=0;v=g.NumAdjVex(w,v) /新頂點(diǎn)并入U(xiǎn)后從新選擇最小邊 if (g.Tag(v)=UNVISITED& (g.GetWeight(v,w) g.GetWeight(v,adjVerv) g.GetWeight(v,adjVer

18、v )=0) adjVexv=w; ;/為新最小的邊 Delete adjVex; 252510504613228102514242216185046132504613210原圖 (a) (b)504613210(c) (d) (e) (f)50461321022125046121025142216123252212克魯斯卡爾算法的基本思想具體做法: 先構(gòu)造一個(gè)只含 n 個(gè)頂點(diǎn)的子圖 SG，然后從權(quán)值最小的邊開(kāi)始，若它的添加不使SG 中產(chǎn)生回路，則在 SG 上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止考慮問(wèn)題的出發(fā)點(diǎn): 為使生成樹(shù)上邊的權(quán)值之和達(dá)到最小，則應(yīng)使生成樹(shù)中每一條邊的權(quán)值盡可能

19、地小abcdegf195141827168213ae12dcbgf7148531621712181910504613228102514242216181250461325046132原圖 (a) (b)1012504613228102514242216181250461325046132101412原圖 (c) (d)504613210141612(e) (f) (g)504613210142216125046121025142216123活動(dòng)網(wǎng)絡(luò) ( Activity Network )用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)( AOV網(wǎng)絡(luò) )( Activity On Vertices )用邊表示活動(dòng)的網(wǎng)絡(luò)(

20、 AOE網(wǎng)絡(luò) )( Activity On Edges )有向無(wú)環(huán)圖 C1 高等數(shù)學(xué) C2 程序設(shè)計(jì)基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)據(jù)結(jié)構(gòu) C3, C2 C5 高級(jí)語(yǔ)言程序設(shè)計(jì) C2 C6 編譯方法 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計(jì)算機(jī)原理 C8 課程代號(hào)課程名稱(chēng)先修課程學(xué)生課程學(xué)習(xí)工程圖C8C3C5C4C9C6C7C1C2拓?fù)渑判?TopologicalSort) 按照有向圖給出的次序關(guān)系，將圖中頂點(diǎn)排成一個(gè)線(xiàn)性序列，對(duì)于有向圖中沒(méi)有限定次序關(guān)系的頂點(diǎn)，則可以人為加上任意的次序關(guān)系 由此所得頂點(diǎn)的線(xiàn)性序列稱(chēng)之為拓?fù)溆行蛐蛄欣纾簩?duì)于下列有

21、向圖BDAC可求得拓?fù)溆行蛐蛄校?A B C D 或 A C B DBDAC反之，對(duì)于下列有向圖不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個(gè)回路 B, C, D進(jìn)行拓?fù)渑判虻牟襟E一、從有向圖中選取一個(gè)沒(méi)有前驅(qū) 的頂點(diǎn)，并輸出之 重復(fù)上述兩步，直至圖空，或者圖不空但找不到無(wú)前驅(qū)的頂點(diǎn)為止二、從有向圖中刪去此頂點(diǎn)以及所 有以它為尾的弧abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念 沒(méi)有前驅(qū)的頂點(diǎn) 入度為零的頂點(diǎn) 刪除頂點(diǎn)及以它為尾的弧 弧頭頂點(diǎn)的入度減1 對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判? 得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 ,

22、 C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6C8C3C5C4C9C6C7C1C2C0C1C2C3C4C5(a) 有向無(wú)環(huán)圖C2C5C1C0C3(b) 輸出頂點(diǎn)C4C1C2C5C3(c) 輸出頂點(diǎn)C0C4C0C2C5C1C3(d) 輸出頂點(diǎn)C3C4 , C0 , C3 , C2 , C1 , C5 C1C2C5(e) 輸出頂點(diǎn)C2C5C1(f) 輸出頂點(diǎn)C1C5(g) 輸出頂點(diǎn)C5(h) 拓?fù)渑判蛲瓿?在算法中, 使用一個(gè)堆?；蜿?duì)列存放入度為零的頂點(diǎn), 供選擇和輸出無(wú)前驅(qū)的頂點(diǎn)AOV網(wǎng)鄰接表表示012345C0C1C2C3C4C5 C0

23、 C1 C2 C3 0 C4 C5 0count data adj 130103 1 dest link 3 0 5 1 5 0 0 1 5 0拓?fù)渑判蛩惴枋鼋⑷攵葹榱愕捻旤c(diǎn)棧當(dāng)入度為零的棧不空時(shí), 重復(fù)執(zhí)行 從棧中退出一個(gè)頂點(diǎn), 并輸出之 從AOV網(wǎng)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊, 邊的終點(diǎn)入度減一 如果邊的終點(diǎn)入度減至0, 則該頂點(diǎn)進(jìn)入入度為零的頂點(diǎn)棧 如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)的頂點(diǎn)個(gè)數(shù), 則報(bào)告網(wǎng)絡(luò)中存在有向環(huán)建立入度為零的頂點(diǎn)隊(duì)當(dāng)入度為零的隊(duì)不空時(shí), 重復(fù)執(zhí)行 從隊(duì)中退出一個(gè)頂點(diǎn), 并輸出之 從AOV網(wǎng)中刪去這個(gè)頂點(diǎn)和它發(fā)出的邊, 邊的終點(diǎn)入度減一 如果邊的終點(diǎn)入度減至0, 則該頂

24、點(diǎn)進(jìn)入入度為零的頂點(diǎn)隊(duì) 如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)的頂點(diǎn)個(gè)數(shù), 則報(bào)告網(wǎng)絡(luò)中存在有向環(huán) 在算法實(shí)現(xiàn)時(shí), 為了建立入度為零的頂點(diǎn)棧,可以不另外分配存儲(chǔ)空間, 直接利用入度為零的頂點(diǎn)的count 數(shù)組元素。設(shè)立一個(gè)棧頂指針 top, 指示當(dāng)前棧頂位置, 即某一個(gè)入度為零的頂點(diǎn)。棧初始化時(shí)置top = -1將頂點(diǎn)i 進(jìn)棧時(shí)執(zhí)行以下指針的修改： counti = top; top = i ; / top指向新棧頂i, 原棧頂元素在counti中退棧操作可以寫(xiě)成： j = top; top = counttop; /位于棧頂?shù)捻旤c(diǎn)記于 j, top退到次 棧頂拓?fù)渑判驎r(shí)入度為零的頂點(diǎn)棧在count中的

25、變化C0C1C2C3C4C513010313-112322-112221-1222012345012345012345012345toptoptoptop建棧toptop頂點(diǎn)4出棧toptop頂點(diǎn)0出棧頂點(diǎn)3出棧拓?fù)渑判驎r(shí)入度為零的頂點(diǎn)棧在count中的變化C0C1C2C3C4C521-12222-1-12212-1-122-12-1-122-1012345012345012345012345toptoptoptoptop頂點(diǎn)1出棧top頂點(diǎn)5出棧頂點(diǎn)2出棧拓?fù)渑判虻乃惴╲oid Graph : TopologicalSort ( ) int top=-1; /入度為零的頂點(diǎn)棧初始化 for

26、( int i=0; in; i+ ) /入度為零頂點(diǎn) if ( counti=0 ) /進(jìn)棧 counti=top; top=i; for ( i=0; in; i+ ) /期望輸出n個(gè)頂點(diǎn) if ( top=-1 ) /中途?？?轉(zhuǎn)出 cout“網(wǎng)絡(luò)中有回路！endl; return; ; else /繼續(xù)拓?fù)渑判?int j=top; top=counttop; /退棧 coutjdest; /另一頂點(diǎn) if ( -countk=0 ) /頂點(diǎn)入度減一 countk=top; top=k; /頂點(diǎn)的入度減至零, 進(jìn)棧 p = p-link; 分析此拓?fù)渑判蛩惴芍?，如果AOV網(wǎng)絡(luò)有n 個(gè)

27、頂點(diǎn)，e 條邊，在拓?fù)渑判虻倪^(guò)程中，搜索入度為零的頂點(diǎn)，建立鏈?zhǔn)綏Ｋ枰臅r(shí)間是O(n)。在正常的情況下，有向圖有 n 個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)進(jìn)一次棧，出一次棧，共輸出 n 次。頂點(diǎn)入度減一的運(yùn)算共執(zhí)行了 e 次。所以總的時(shí)間復(fù)雜度為O(n+e)關(guān)鍵路徑(Critical Path)問(wèn)題:假設(shè)以有向網(wǎng)表示一個(gè)施工流程 圖，弧上的權(quán)值表示完成該項(xiàng)子 工程所需時(shí)間。 問(wèn)：哪些子工程項(xiàng)是“關(guān)鍵工程”？ 即：哪些子工程項(xiàng)將影響整個(gè)工程的 完成期限abcdefghk64521187244例如:整個(gè)工程完成的時(shí)間為：從有向圖的源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑源點(diǎn)匯點(diǎn)6174 用有向邊表示一個(gè)工程中的活動(dòng) (Activity

28、), 用邊上權(quán)值表示活動(dòng)持續(xù)時(shí)間 (Duration), 用頂點(diǎn)表示事件 (Event) “關(guān)鍵活動(dòng)”指的是： 該弧上的權(quán)值增加 將使有向圖上的最長(zhǎng)路徑的長(zhǎng)度增加 完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度, 即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑 如何求關(guān)鍵活動(dòng)？假設(shè)第 i 條弧為 對(duì)第 j 個(gè)頂點(diǎn)而言“事件(頂點(diǎn))”的最早發(fā)生時(shí)間 ve(j)“事件(頂點(diǎn))”的最遲發(fā)生時(shí)間 vl(j)對(duì)第 i 項(xiàng)活動(dòng)而言 “活動(dòng)(弧)”的最早開(kāi)始時(shí)間 ee(i) “活動(dòng)(弧)”的最遲開(kāi)始時(shí)間 el(i) ve(源點(diǎn)) = 0；ve(k) = Maxve(j)

29、+ dut()(2=k=n, 屬于所有以k為 頭的弧的集合)vl(匯點(diǎn)) = ve(匯點(diǎn))；vl(j) = Minvl(k) dut()(1=j=n-1, 屬于所有以j為 尾的弧的集合)附注“事件(頂點(diǎn))” 的 最早發(fā)生時(shí)間 ve(j)ve(j) = 從源點(diǎn)到頂點(diǎn)j的最長(zhǎng)路徑長(zhǎng)度；“事件(頂點(diǎn))” 的 最遲發(fā)生時(shí)間 vl(k) vl(k) =從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度- 從頂點(diǎn)k到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度。ee(i) = ve(j)el(i) = vl(k) dut()ve(源點(diǎn)) = vl(源點(diǎn)) = 0vl(匯點(diǎn)) = ve(匯點(diǎn))關(guān)鍵活動(dòng):el(i) = ee(i) 這兩個(gè)遞推公式的計(jì)算必須分

30、別在拓?fù)溆行蚣澳嫱負(fù)溆行虻那疤嵯逻M(jìn)行abcdefghk6452118724400000000064571157151418181818181818181818161486610807拓?fù)溆行蛐蛄? a - d - f - c - b - e - h - g - k0645771514181814161078660000645777151414160236688710顯然 求ve的順序應(yīng)該是按拓?fù)溆行虻?次序 而 求vl的順序應(yīng)該是按拓?fù)淠嫘虻?次序因?yàn)?拓?fù)淠嫘蛐蛄屑礊橥負(fù)溆行蛐蛄?的逆序列因此 應(yīng)該在拓?fù)渑判虻倪^(guò)程中， 另設(shè)一個(gè)“?！庇浵峦?fù)溆行蛐蛄?要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng), 即不

31、按期完成就會(huì)影響整個(gè)工程完成的活動(dòng)關(guān)鍵路徑上的所有活動(dòng)都是關(guān)鍵活動(dòng) 因此, 只要找到了關(guān)鍵活動(dòng), 就可以找到關(guān)鍵路徑求關(guān)鍵路徑算法Status Topologicalorder(ALGraph G, Stack &T)/求各頂點(diǎn)的最早發(fā)生時(shí)間veFindInDegree(G,indegree);/求各頂點(diǎn)入度); 建零入度頂點(diǎn)棧S;Initstack(S); count=0;Ve0.G.vexnum-1=0;/初始化While (!StackEmpty(S) Pop(S,j); Push(T,j); +count; for (p=G.verticesj.firstarc; p; p=p-nesyarc) k=p-adjvex; if (-indegreek=0) Push(S,k); if(vej+*(p-info)vek) vek=vej+*(p-info); /for *(p-info)=dut() /while if (countG.vexnum) return ERROR; else return OK /最短路徑 (Shortest Path)最短路徑問(wèn)題 如果從圖中某一頂點(diǎn)(稱(chēng)為源點(diǎn))到達(dá)另一頂點(diǎn)(稱(chēng)為終點(diǎn))的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達(dá)到最小問(wèn)題解法 邊上權(quán)值非負(fù)情形的單源最短路徑 問(wèn)題 Dijkstra算法 所有頂點(diǎn)之