第七章圖無答案

1、上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束第七章第七章 圖圖圖的定義和術(shù)語圖的定義和術(shù)語圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)圖的基本操作圖的基本操作-遍歷遍歷應(yīng)用應(yīng)用最小生成樹最小生成樹 拓?fù)渑判蛲負(fù)渑判?關(guān)鍵路徑關(guān)鍵路徑 最短路最短路上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束7.17.1圖的定義和圖的定義和術(shù)語術(shù)語l線性表、樹和圖：從關(guān)系、結(jié)構(gòu)兩個(gè)角度區(qū)分線性表、樹和圖：從關(guān)系、結(jié)構(gòu)兩個(gè)角度區(qū)分 ab e c d b ca d f el圖圖graph;頂點(diǎn)頂點(diǎn)vertex;序偶序偶;弧弧arc;弧頭弧頭b/弧尾弧尾aldigraph;undigraph;無序?qū)o序?qū)?a,b):;edgel網(wǎng)網(wǎng)network:弧

2、或邊含權(quán)的圖弧或邊含權(quán)的圖,分分有向網(wǎng)有向網(wǎng)dn、無向網(wǎng)無向網(wǎng)udnl(無向無向)完全圖完全圖:邊數(shù)最大的無向簡單圖邊數(shù)最大的無向簡單圖,滿足滿足e=n*(n-1)/2l有向完全圖有向完全圖:弧數(shù)最大的有向簡單圖弧數(shù)最大的有向簡單圖, e=n*(n-1)l稀疏圖稀疏圖(如如enlogn) 稠密圖稠密圖abecf1597211132上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束becbbc子圖subgraph 鄰接點(diǎn):無向圖如a與b互為鄰接點(diǎn),有向圖如a鄰接到b無向圖頂點(diǎn)的度,如td(a)=2；有向圖分入/出度,度為兩者之和 id(a)=1,od(a)=2,td(a)=3路徑、簡單路徑、回路(環(huán))、路徑

3、長度術(shù)語術(shù)語 b ca d f eabecf上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束若無向圖g中任意兩個(gè)頂點(diǎn)之間都有路徑相通，則稱此圖為連通圖。連通圖。如能找到一條含全部頂點(diǎn)如能找到一條含全部頂點(diǎn)的路徑則說明是連通圖的路徑則說明是連通圖無向圖中的極大連通子圖稱作此圖的連通分量。連通分量。極大指頂點(diǎn)盡量多,頂點(diǎn)連同其關(guān)聯(lián)的邊構(gòu)成連通分量.圖本身連通則連通分量唯一,是自身bacdfebacdfe連通圖連通圖,連通分量連通分量 (無向圖)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束若任意兩頂點(diǎn)間都存在一條有向路徑，則稱此有向圖為強(qiáng)連通圖強(qiáng)連通圖。abecfabecf有向圖的極大強(qiáng)連通子圖稱作它的強(qiáng)連通分量強(qiáng)

4、連通分量。強(qiáng)連通圖、強(qiáng)連通分量強(qiáng)連通圖、強(qiáng)連通分量( (有向圖)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束連通圖的一個(gè)含有全部頂點(diǎn)的子圖,如果連通且極小極小，則它必是一顆樹(邊數(shù)為n-1)，稱該樹為原連通圖的生成樹。破圈法可得生成樹 對非連通圖，由各個(gè)連通分量的生成樹組成的集合稱為此非連通圖的生成森林生成森林。bacdfe生成樹與生成森林（無向圖）生成樹與生成森林（無向圖）注注: :樹是含邊數(shù)最小的連通圖樹是含邊數(shù)最小的連通圖(n-1);(n-1);圖中圖中若邊少于若邊少于n-1n-1則必不連通；若圖連通則至則必不連通；若圖連通則至少含少含n-1n-1條邊；若圖中多于條邊；若圖中多于n-1n-1條

5、邊則必然條邊則必然含有回路。含含有回路。含n-1n-1條邊的連通圖必然是樹條邊的連通圖必然是樹上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束adt graph 數(shù)據(jù)對象數(shù)據(jù)對象v：若干頂點(diǎn)組成的集合：若干頂點(diǎn)組成的集合 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系r：r=vr vr| v,wv 且 表示從 v 到 w 有一條弧，可代表v認(rèn)識(shí)w 或 v到w有路等) 基本操作基本操作 圖的抽象數(shù)據(jù)類型定義圖的抽象數(shù)據(jù)類型定義邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束creatgraph(&gcreatgraph(&g, v, vr);, v, vr); / 按定義(v, vr) 構(gòu)造圖gdestroygraph(&gde

6、stroygraph(&g);); / 銷毀圖g結(jié)構(gòu)的建立和銷毀結(jié)構(gòu)的建立和銷毀上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束插入或刪除頂點(diǎn)、弧插入或刪除頂點(diǎn)、弧insertvex(&g, v); /在圖在圖g g中增添新頂點(diǎn)中增添新頂點(diǎn)v v。deletevex(&g, v);/ / 刪除刪除g g中頂點(diǎn)中頂點(diǎn)v v及其相關(guān)的弧。及其相關(guān)的弧。insertarc(&g, v, w); /在在g g中增添弧中增添弧，若，若g g是無是無向的，則還增添對稱弧向的，則還增添對稱弧deletearc(&g, v, w); /在在g g中刪除弧中刪除弧，若，若g g是無是無向的，則還刪除對稱弧向的，則還刪除對

7、稱弧上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束遍遍 歷歷dfstraverse(g, v, visit(); /從頂點(diǎn)v起深度優(yōu)先深度優(yōu)先遍歷圖g,對每個(gè)頂點(diǎn)執(zhí)行一次visitbfstraverse(g, v, visit(); /從v起廣度優(yōu)先廣度優(yōu)先遍歷圖g，每個(gè)頂點(diǎn)調(diào)用一次函數(shù)visit規(guī)則規(guī)則: :訪問起始頂點(diǎn)訪問起始頂點(diǎn)v,v,然后選取與然后選取與v v鄰接的未訪問的第一個(gè)頂點(diǎn)鄰接的未訪問的第一個(gè)頂點(diǎn)w,w,訪問之，再選取與訪問之，再選取與w w鄰接的未訪問的第一個(gè)頂點(diǎn)，訪問之。重復(fù)進(jìn)鄰接的未訪問的第一個(gè)頂點(diǎn)，訪問之。重復(fù)進(jìn)行至當(dāng)前節(jié)點(diǎn)的所有鄰接點(diǎn)都被訪問過，此時(shí)后退到最近訪問過行至當(dāng)前

8、節(jié)點(diǎn)的所有鄰接點(diǎn)都被訪問過，此時(shí)后退到最近訪問過的定點(diǎn)，找其下一個(gè)未訪問的鄰接點(diǎn)訪問，依次類推。如的定點(diǎn)，找其下一個(gè)未訪問的鄰接點(diǎn)訪問，依次類推。如abe abe fcd fcd h h說明說明: :一次可遍歷所有與一次可遍歷所有與v v連通的頂點(diǎn)。若尚有頂點(diǎn)未訪問連通的頂點(diǎn)。若尚有頂點(diǎn)未訪問( (非連通非連通圖圖),),則從其開始重復(fù)上述過程則從其開始重復(fù)上述過程. .對應(yīng)樹的先根遍歷?？傻蒙疃葍?yōu)先對應(yīng)樹的先根遍歷。可得深度優(yōu)先生成樹或森林以及連通分量生成樹或森林以及連通分量遞歸描述遞歸描述：訪問：訪問v, v, 逐個(gè)從逐個(gè)從v v未訪問的鄰接點(diǎn)出發(fā)遞歸遍歷未訪問的鄰接點(diǎn)出發(fā)遞歸遍歷. .規(guī)

9、則規(guī)則: :訪問訪問v,v,訪問訪問v v的全部未訪問的鄰接點(diǎn)的全部未訪問的鄰接點(diǎn), ,再逐個(gè)從這些鄰接點(diǎn)出再逐個(gè)從這些鄰接點(diǎn)出發(fā)重復(fù)發(fā)重復(fù). .一次可遍歷所有與一次可遍歷所有與v v連通的頂點(diǎn)連通的頂點(diǎn), ,若尚有頂點(diǎn)未訪問則從其若尚有頂點(diǎn)未訪問則從其開始重復(fù)開始上述過程開始重復(fù)開始上述過程. .如如abehfcdabehfcd對應(yīng)樹層序遍歷對應(yīng)樹層序遍歷, ,可得廣度優(yōu)先生成樹可得廣度優(yōu)先生成樹/ /森林森林, ,可得連通分量可得連通分量, ,實(shí)現(xiàn)實(shí)現(xiàn)? ? b ca d f eh上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束對頂點(diǎn)的訪問操作對頂點(diǎn)的訪問操作locatevex(g, u); / 若

10、g中存在頂點(diǎn)與u”相等”，則返回該頂點(diǎn)在圖中“位置位置”(下標(biāo)或指針)getvex(g, v); / 返回g中頂點(diǎn)v的值。putvex(&g, v, value);/為g中頂點(diǎn)v賦值value。上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束對鄰接點(diǎn)的操作對鄰接點(diǎn)的操作firstadjvex(g, v); /返回返回g g中頂點(diǎn)中頂點(diǎn)v v的的“第一個(gè)鄰接點(diǎn)第一個(gè)鄰接點(diǎn)”。若該頂點(diǎn)。若該頂點(diǎn)/在在 g g 中沒有鄰接點(diǎn)，則返回中沒有鄰接點(diǎn)，則返回“空空”。nextadjvex(g, v, w); / w/ w是是v v的一個(gè)鄰接點(diǎn)的一個(gè)鄰接點(diǎn), ,返回返回v v的的“下一個(gè)鄰接點(diǎn)下一個(gè)鄰接點(diǎn)”。/若若w

11、 w是是v v的最后一個(gè)鄰接點(diǎn)，則返回的最后一個(gè)鄰接點(diǎn)，則返回“-1”-1”。上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束圖的圖的數(shù)組數(shù)組表示表示(p161)( (鄰接矩陣鄰接矩陣) )圖的圖的鄰接表鄰接表表示表示(p163)有向圖的有向圖的十字鏈表十字鏈表表示表示(p164) 無向圖的無向圖的鄰接多重表鄰接多重表表示表示(p166)7.2 7.2 圖的存儲(chǔ)結(jié)構(gòu)圖的存儲(chǔ)結(jié)構(gòu)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束bacdfe鄰接矩陣鄰接矩陣: :行、列各對應(yīng)一個(gè)頂點(diǎn)行、列各對應(yīng)一個(gè)頂點(diǎn), ,若第若第i i行對應(yīng)的頂點(diǎn)到行對應(yīng)的頂點(diǎn)到第第j j列對應(yīng)的頂點(diǎn)有弧相連則列對應(yīng)的頂點(diǎn)有弧相連則aijaij=1

12、,=1,否則為否則為0 0。n n* *n n階階 a b c d e f abcdef1 1、圖的數(shù)組表示、圖的數(shù)組表示-鄰接矩陣鄰接矩陣adjacency matrixadjacency matrix上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束0 1 0 0 1 0 0 1 0 0 0 0 0 1 0 1 1 0 0 0 0 0 1 0 0 abecd無向圖的鄰接矩陣必為對稱陣網(wǎng)的鄰接矩陣aij=waij=wijij或或上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束 a b c d e fabcdef/-圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存儲(chǔ)表示存儲(chǔ)表示-typedef char vertextype

13、;#define infinity 10000 /最大值最大值 #define max_vertex_num 20 /最大頂點(diǎn)個(gè)數(shù)最大頂點(diǎn)個(gè)數(shù)typedef enumdg, dn, udg, udn graphkind;/圖類型圖類型 typedef struct arccell / 弧的定義弧的定義 vrtype adj; /鄰接數(shù)鄰接數(shù),0/1或或w/。vrtypevrtype為為int/doubleint/double infotype *info; /弧的附加信息數(shù)組弧的附加信息數(shù)組arccell,arccell,adjmatrixadjmatrixmax_vertex_nummax_

14、vertex_nummax_vertex_nummax_vertex_num;typedef struct / 圖的定義圖的定義 vertextype vexsmax_vertex_num; /頂點(diǎn)信息頂點(diǎn)信息 adjmatrix arcs; / 鄰接矩陣鄰接矩陣,存儲(chǔ)弧信息存儲(chǔ)弧信息,靜態(tài)數(shù)組靜態(tài)數(shù)組 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù)頂點(diǎn)數(shù)，弧數(shù) graphkind kind; / 圖的類型標(biāo)記圖的類型標(biāo)記 mgraph; /矩陣圖矩陣圖上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束status creategraph(mgraph &g) /輸入圖的種類及頂點(diǎn)和邊信息構(gòu)造圖

15、輸入圖的種類及頂點(diǎn)和邊信息構(gòu)造圖g(鄰接矩陣表示鄰接矩陣表示) scanf(“%d”,&g.kind);/枚舉值枚舉值dg,dn實(shí)輸入實(shí)輸入0 1 switch (g.kind) case dg : return createdg(g); case dn : return createdn(g); case udg : return createudg(g); case udn : return createudn(g); default : return error;圖的創(chuàng)建圖的創(chuàng)建上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束status createudn(mgraph &g) /建立無向網(wǎng)建立

16、無向網(wǎng)g 輸入輸入g.vexnum,g.arcnum, incinfo;/incinfo為為0 0表各弧無附加信息表各弧無附加信息 for (i=0 ; i g.vexnum; +i) scanf(“%c”,g.vexsi); for (i=0 ; i g.vexnum; +i) for(j=0 ; jvexnum; +j) g.arcsij=infnity,null; /各弧初始化各弧初始化 for (k=0;k g.arcnum;+k) scanf(“%c %c %lf”,&v1,&v2,&w); /輸入一條輸入一條“邊邊”及其權(quán)及其權(quán)值值 i=locatevex(g,v1);j= loc

17、atevex(g,v2) ;/確定頂點(diǎn)下標(biāo)確定頂點(diǎn)下標(biāo) g.arcsij.adj = w; if (incinfo) 輸入輸入g.; g.arcsji= g.arcsij; /無向網(wǎng)需將對稱弧加入無向網(wǎng)需將對稱弧加入 /endabecf1597211132上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束bacdfe abcdef鄰接矩陣優(yōu)缺點(diǎn)：鄰接矩陣優(yōu)缺點(diǎn)：易于求頂點(diǎn)度易于求頂點(diǎn)度( (區(qū)分有區(qū)分有/ /無向圖無向圖) )、求鄰接點(diǎn)，易判斷兩點(diǎn)間是否有、求鄰接點(diǎn)，易判斷兩點(diǎn)間是否有弧或邊相連弧或邊相連, ,但不利于稀疏圖的存儲(chǔ)，因弧不存在時(shí)也要存儲(chǔ)相應(yīng)但不利于稀疏圖的存儲(chǔ)，因弧不

18、存在時(shí)也要存儲(chǔ)相應(yīng)信息，且要預(yù)先分配足夠大空間信息，且要預(yù)先分配足夠大空間上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束小結(jié)：小結(jié)：u掌握圖的概念和基本術(shù)語掌握圖的概念和基本術(shù)語u掌握圖的掌握圖的鄰接矩陣存鄰接矩陣存儲(chǔ)，理解優(yōu)缺點(diǎn)儲(chǔ)，理解優(yōu)缺點(diǎn)u掌握圖的掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的規(guī)則規(guī)則u會(huì)通過遍歷求圖的連通分量和深度優(yōu)先、會(huì)通過遍歷求圖的連通分量和深度優(yōu)先、廣度優(yōu)先生成樹、生成森林廣度優(yōu)先生成樹、生成森林u作業(yè)：作業(yè)：1 5 b ca d f eh上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束 a b c d e fabcdef/-圖的數(shù)組圖的數(shù)組(鄰接矩陣鄰接矩陣)存

19、儲(chǔ)表示存儲(chǔ)表示-typedef char vertextype;#define infinity 10000 /最大值最大值 #define max_vertex_num 20 /最大頂點(diǎn)個(gè)數(shù)最大頂點(diǎn)個(gè)數(shù)typedef enumdg, dn, udg, udn graphkind;/圖類型圖類型 typedef struct arccell / 弧的定義弧的定義 vrtype adj; /鄰接數(shù)鄰接數(shù),0/1或或w/。vrtypevrtype為為int/doubleint/double infotype *info; /弧的附加信息數(shù)組弧的附加信息數(shù)組arccell,arccell,adjma

20、trixadjmatrixmax_vertex_nummax_vertex_nummax_vertex_nummax_vertex_num;typedef struct / 圖的定義圖的定義 vertextype vexsmax_vertex_num; /頂點(diǎn)信息頂點(diǎn)信息 adjmatrix arcs; / 鄰接矩陣鄰接矩陣,存儲(chǔ)弧信息存儲(chǔ)弧信息,靜態(tài)數(shù)組靜態(tài)數(shù)組 int vexnum, arcnum; / 頂點(diǎn)數(shù)，弧數(shù)頂點(diǎn)數(shù)，弧數(shù) graphkind kind; / 圖的類型標(biāo)記圖的類型標(biāo)記 mgraph; /矩陣圖矩陣圖上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束0 a 1 41 b 0 4 5

21、2 c 3 53 d 2 54 e 0 15 f 1 2 3 bacdfe頂點(diǎn)數(shù)組(頭結(jié)點(diǎn)) 鄰接點(diǎn)鏈表無向圖中每條邊出現(xiàn)兩次無向圖中每條邊出現(xiàn)兩次,n,n個(gè)個(gè)頂點(diǎn)頂點(diǎn)e e條邊需條邊需n n個(gè)頭結(jié)點(diǎn)和個(gè)頭結(jié)點(diǎn)和2e2e個(gè)個(gè)表結(jié)點(diǎn)表結(jié)點(diǎn)2 2、鄰接表存儲(chǔ)表示、鄰接表存儲(chǔ)表示上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1 4230 120 1 2 3 4 a b c d e鄰接表舉例鄰接表舉例abecdtypedef struct arcnode int adjvex; struct arcnode *nextarc; infotype *info; arcnode;data firstarcadjv

22、ex nextarc infotypedef struct vnode vertextype data; arcnode *firstarc; vnode, adjlistmax_vertex_num;typedef struct adjlist vertices; int vexnum, arcnum; graphkind kind; algraph; /鄰接表圖上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束status creategraph(algraph &g) /建立圖的鄰接表的結(jié)構(gòu)建立圖的鄰接表的結(jié)構(gòu) scanf(“%d”, &g.kind); switch (g.kind) case d

23、g : return createdg(g); case dn : return createdn(g); case udg : return createudg(g); case udn : return createudn(g); default : return error;鄰接表圖的創(chuàng)建鄰接表圖的創(chuàng)建【補(bǔ)充【補(bǔ)充】上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束status createdn(algraph &g) /建立有向網(wǎng)建立有向網(wǎng) scanf(“%d%d%d”,&g.vexnum,&g.arcnum,&incinfo); for (i=0 ; i g.vexnum; +i) scanf(

24、g.verticesi.data); g.verticesi.firstarc=null; for (k=0;kadjvex=j; if (incinf) 輸入輸入(arcn(arcn-info);-info); arc-nextarc = g.verticesi.firstarc; g.verticesi.firstarc=arcn;/鄰接點(diǎn)與輸入逆序排列p164,正序? /鄰接點(diǎn)順序依賴輸入順序和創(chuàng)建程序，鄰接點(diǎn)順序依賴輸入順序和創(chuàng)建程序，“不給不給”默認(rèn)正默認(rèn)正序序 return ok； /思考無向網(wǎng)的創(chuàng)建有何不同？思考無向網(wǎng)的創(chuàng)建有何不同？上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束1 42

25、30 120 1 2 3 4 a b c d e鄰接表說明：鄰接表說明：abecd稀疏圖用鄰接表存儲(chǔ)相對節(jié)省空間稀疏圖用鄰接表存儲(chǔ)相對節(jié)省空間對有向圖易求頂點(diǎn)出度與鄰接點(diǎn)對有向圖易求頂點(diǎn)出度與鄰接點(diǎn), ,但求入但求入度難度難. .若只求入度可引入逆鄰接表若只求入度可引入逆鄰接表, ,也可結(jié)也可結(jié)合鄰接表與逆鄰接表引入合鄰接表與逆鄰接表引入十字鏈表十字鏈表對無向圖易求度對無向圖易求度, ,但邊出現(xiàn)兩次但邊出現(xiàn)兩次, ,為方便邊為方便邊操作可借助操作可借助多重鏈表多重鏈表a b c d e 303420 01234上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束3、“有向圖有向圖”的十字鏈表存儲(chǔ)表示【選的十

26、字鏈表存儲(chǔ)表示【選】 abdce0 10 a1 b2 c3 d4 e.tailv headv hlink tlinkinfodatafirstinfirstout0 3 vexnodevexnode: :arcboxarcbox: :1 22 4 3 2 4 0 4 1 具體鄰接點(diǎn)順序依賴輸入順具體鄰接點(diǎn)順序依賴輸入順序和圖的創(chuàng)建程序，如逆序序和圖的創(chuàng)建程序，如逆序上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束3、“有向圖有向圖”的十字鏈表存儲(chǔ)表示【選的十字鏈表存儲(chǔ)表示【選】 typedef struct arcbox int tailvex, headvex; infotype *info; str

27、uct arcbox *hlink,*tlink;/指向同弧頭/尾的下一弧 arcbox;typedef struct vexnode / 頂點(diǎn)的結(jié)構(gòu)表示頂點(diǎn)的結(jié)構(gòu)表示 vertextype data; arcbox *firstin, *firstout; vexnode;typedef struct vexnode xlistmax_vertex_num; int vexnum, arcnum; olgraph;上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束status createdg(olgraph g) scanf(&g.vexnum, &g.arcnum, &incinf); for(i=

28、0;i g.vexnum; +i) scanf(&g.xlisti.data); g.xlisti.firstin=null;g.xlisti.firstout=null; for(k=0;kinfo); /end 上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束4、“無向圖無向圖”的鄰接多重表存儲(chǔ)表示【選的鄰接多重表存儲(chǔ)表示【選】無向圖的鄰接表存儲(chǔ)中，一條邊出現(xiàn)兩次，分別在兩個(gè)無向圖的鄰接表存儲(chǔ)中，一條邊出現(xiàn)兩次，分別在兩個(gè)頂點(diǎn)對應(yīng)的鏈表中，對邊的操作復(fù)雜。為此，將每條邊頂點(diǎn)對應(yīng)的鏈表中，對邊的操作復(fù)雜。為此，將每條邊(vi,vj)只用一個(gè)如下結(jié)點(diǎn)表示只用一個(gè)如下結(jié)點(diǎn)表示:頂點(diǎn)表示為：頂點(diǎn)表示為：ma

29、rk ivexilink jvexjlinkinfodata firstedge0 1 2 3 a b c dabdc01 031 2 2 3 e1e2e3 e4 將邊看作有向的，將邊看作有向的，如如a-ba-b上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束typedef struct ebox visitif mark; / 訪問標(biāo)記訪問標(biāo)記 int ivex, jvex; /該邊依附的兩個(gè)頂點(diǎn)的位置該邊依附的兩個(gè)頂點(diǎn)的位置 struct ebox *ilink,*jlink;/指向?qū)?yīng)頂點(diǎn)為指向?qū)?yīng)頂點(diǎn)為i,j的下一邊的下一邊 infotype *info; ebox;4、“無向圖無向圖”的鄰接多

30、重表存儲(chǔ)表示【選的鄰接多重表存儲(chǔ)表示【選】typedef struct vexbox adjmulistmax_vertex_num; int vexnum, edgenum; amlgraph; / 鄰接多重表鄰接多重表typedef struct vexbox vertextype data; ebox *firstedge; / 指向第一條依附該頂點(diǎn)的邊指向第一條依附該頂點(diǎn)的邊 vexbox;上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束7.37.3圖的遍歷圖的遍歷深度優(yōu)先遍歷深度優(yōu)先遍歷規(guī)則規(guī)則: :訪問訪問v,v,逐個(gè)從逐個(gè)從v v未訪問的鄰接點(diǎn)出發(fā)遞歸未訪問的鄰接點(diǎn)出發(fā)遞歸遍歷，如此可遍歷

31、所有與遍歷，如此可遍歷所有與v v連通的頂點(diǎn)連通的頂點(diǎn). .若尚有若尚有頂點(diǎn)未訪問頂點(diǎn)未訪問( (不連通不連通),),則從其開始重復(fù)上述過程則從其開始重復(fù)上述過程. .如如abefcdh.abefcdh.void dfs(g，v) visitfunc(v); visitedv visitfunc(v); visitedv=true;=true; for(w=firstadjvex(g,v);w=0;w=nextadjvex(g,v,wfor(w=firstadjvex(g,v);w=0;w=nextadjvex(g,v,w) if（!visitedw）dfs(g，w)；void dfstrav

32、erse(graph g, status (*visit)(int v) visitfunc = visit; for (v=0; vg.vexnum; +v) visitedv = false; for (v=0; vg.vexnum; +v) if (!visitedv) dfs(g, v);/visited數(shù)組和數(shù)組和visitfunc函數(shù)為全局函數(shù)為全局每個(gè)頂點(diǎn)調(diào)用一次每個(gè)頂點(diǎn)調(diào)用一次dfs,dfsdfs,dfs主要操主要操作是查找鄰接點(diǎn)作是查找鄰接點(diǎn), ,當(dāng)用鄰接矩陣存當(dāng)用鄰接矩陣存儲(chǔ)時(shí)查找某頂點(diǎn)的鄰接點(diǎn)復(fù)雜度為儲(chǔ)時(shí)查找某頂點(diǎn)的鄰接點(diǎn)復(fù)雜度為o(no(n),),總復(fù)雜度總復(fù)雜度o(n

33、o(n2 2););當(dāng)鄰接表存當(dāng)鄰接表存儲(chǔ)時(shí)查找鄰接點(diǎn)總復(fù)雜度為儲(chǔ)時(shí)查找鄰接點(diǎn)總復(fù)雜度為o(eo(e),),總復(fù)雜度為總復(fù)雜度為o(n+eo(n+e) )dfstraversedfstraverse每調(diào)用一次每調(diào)用一次dfsdfs所訪所訪問的頂點(diǎn)連通這些頂點(diǎn)關(guān)聯(lián)的邊構(gòu)問的頂點(diǎn)連通這些頂點(diǎn)關(guān)聯(lián)的邊構(gòu)成一個(gè)連通分量成一個(gè)連通分量. .只保留走過的邊只保留走過的邊得生成樹或生成森林得生成樹或生成森林 b ca d f eh上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束abchdekfgachkfedbgabcdefghk2345607070807812385547注意鄰接點(diǎn)的順序作題時(shí)若未給出則默認(rèn)為正序注

34、意鄰接點(diǎn)的順序作題時(shí)若未給出則默認(rèn)為正序, ,實(shí)際上應(yīng)依賴實(shí)際上應(yīng)依賴創(chuàng)建程序和輸入順序。若給出存儲(chǔ)結(jié)構(gòu)則以所給為準(zhǔn)。如上例創(chuàng)建程序和輸入順序。若給出存儲(chǔ)結(jié)構(gòu)則以所給為準(zhǔn)。如上例既非正序也非逆序既非正序也非逆序, ,如如h h、k k頂點(diǎn)對應(yīng)的鏈表，畫生成樹時(shí)注意頂點(diǎn)對應(yīng)的鏈表，畫生成樹時(shí)注意求圖的連通分量、深度優(yōu)先生成樹或生成森林求圖的連通分量、深度優(yōu)先生成樹或生成森林p171p171dfstraversedfstraverse每調(diào)用一次每調(diào)用一次dfsdfs所訪問的頂點(diǎn)連同這些頂點(diǎn)關(guān)聯(lián)的所訪問的頂點(diǎn)連同這些頂點(diǎn)關(guān)聯(lián)的邊構(gòu)成一個(gè)連通分量邊構(gòu)成一個(gè)連通分量. .只保留走過的邊得生成樹或生成森林

35、只保留走過的邊得生成樹或生成森林上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束7.3 7.3 圖的遍歷圖的遍歷廣度優(yōu)先遍歷廣度優(yōu)先遍歷bfstraverse(g, v, visit(); 規(guī)則規(guī)則: :訪問訪問v, v, 訪問訪問v v的各未訪問的鄰接點(diǎn)的各未訪問的鄰接點(diǎn), ,之后逐個(gè)從這些鄰接之后逐個(gè)從這些鄰接點(diǎn)出發(fā)重復(fù)上述操作點(diǎn)出發(fā)重復(fù)上述操作。待與待與v v連通的頂點(diǎn)訪問畢再從另一頂點(diǎn)出連通的頂點(diǎn)訪問畢再從另一頂點(diǎn)出發(fā)發(fā). . 如如abehfcdabehfcd實(shí)現(xiàn)：實(shí)現(xiàn)：對各個(gè)頂點(diǎn)對各個(gè)頂點(diǎn)v v： 若其尚未訪問則訪問若其尚未訪問則訪問v,v,之后之后v v入隊(duì)。入隊(duì)。 【隊(duì)頂元素出隊(duì)，逐個(gè)訪問

36、其尚未訪問的鄰接點(diǎn)，沒訪問完一【隊(duì)頂元素出隊(duì)，逐個(gè)訪問其尚未訪問的鄰接點(diǎn)，沒訪問完一個(gè)便入隊(duì)】。重復(fù)【】中內(nèi)容到隊(duì)空個(gè)便入隊(duì)】。重復(fù)【】中內(nèi)容到隊(duì)空 b ca d f eh上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束void bfstraverse(graph g, status (*visit)(int v) for (v=0; vg.vexnum; +v)visitedv = false; initqueue(q); for ( v=0; v=0;w=nextadjvex(g,v,w) if ( ! visitedw ) /注意注意nextadjvex返回值約定返回值約定 visit(w); v

37、isitedw=true; enqueue(q, w); 對各個(gè)頂點(diǎn)對各個(gè)頂點(diǎn)v v： 若其尚未訪問則訪問若其尚未訪問則訪問v,v,之后之后v v入隊(duì)?！娟?duì)頂元素出隊(duì)，逐個(gè)入隊(duì)。【隊(duì)頂元素出隊(duì)，逐個(gè)訪問其尚未訪問的鄰接點(diǎn)，每訪問完一個(gè)便入隊(duì)】。重復(fù)【】中內(nèi)容到隊(duì)空訪問其尚未訪問的鄰接點(diǎn)，每訪問完一個(gè)便入隊(duì)】。重復(fù)【】中內(nèi)容到隊(duì)空每個(gè)頂點(diǎn)進(jìn)一次隊(duì)每個(gè)頂點(diǎn)進(jìn)一次隊(duì), ,出隊(duì)時(shí)主要操作是查找鄰接點(diǎn)出隊(duì)時(shí)主要操作是查找鄰接點(diǎn), ,當(dāng)用鄰接矩陣存儲(chǔ)時(shí)查找某頂點(diǎn)的各鄰接點(diǎn)復(fù)雜度當(dāng)用鄰接矩陣存儲(chǔ)時(shí)查找某頂點(diǎn)的各鄰接點(diǎn)復(fù)雜度的為的為o(n),o(n),總復(fù)雜度總復(fù)雜度o(no(n2 2); ); 當(dāng)用鄰接表存

38、儲(chǔ)時(shí)查找當(dāng)用鄰接表存儲(chǔ)時(shí)查找鄰接點(diǎn)復(fù)雜度為鄰接點(diǎn)復(fù)雜度為o(e),o(e),總復(fù)雜度為總復(fù)雜度為o(n+e)o(n+e)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束7.4.3 7.4.3 最小生成樹最小生成樹p173p173假設(shè)要在假設(shè)要在 n 個(gè)城市之個(gè)城市之間建立通訊聯(lián)絡(luò)網(wǎng)，間建立通訊聯(lián)絡(luò)網(wǎng)，不同城市間建立通訊不同城市間建立通訊設(shè)施的代價(jià)設(shè)施的代價(jià)不同不同，如，如何在最節(jié)省經(jīng)費(fèi)的前何在最節(jié)省經(jīng)費(fèi)的前提下建立這個(gè)通訊網(wǎng)？提下建立這個(gè)通訊網(wǎng)？即找權(quán)值之和最小的即找權(quán)值之和最小的極小連通子網(wǎng)，問題極小連通子網(wǎng)，問題轉(zhuǎn)換為轉(zhuǎn)換為在連通網(wǎng)中找在連通網(wǎng)中找一顆生成樹，最小生一顆生成樹，最小生成樹成樹abcd

39、egf195141827168213ae12dcbgf7148531621上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束ukuaskal算法算法直接找權(quán)值最小的邊直接找權(quán)值最小的邊,若并入后構(gòu)成回路則舍若并入后構(gòu)成回路則舍棄棄kruskalkruskal算法求最小生成樹：算法求最小生成樹：設(shè)設(shè)n=(v,e)是連通網(wǎng)是連通網(wǎng),求最小生成樹求最小生成樹令令t=(v,),t=(v,),各頂點(diǎn)自各頂點(diǎn)自成一連通分量成一連通分量在在e e中找代價(jià)最小的邊中找代價(jià)最小的邊, ,若該邊的頂點(diǎn)落在若該邊的頂點(diǎn)落在不同不同連通分量連通分量上，則將其并上，則將其并入入, ,依次類推至所有頂依次類推至所有頂點(diǎn)到一個(gè)連通分量

40、上點(diǎn)到一個(gè)連通分量上總總o(eloge)o(eloge)，與，與n n無關(guān)，無關(guān)，適合稀疏圖適合稀疏圖abcdegf195141827168213ae12dcbgf71485316217121819primprim算法是逐個(gè)頂點(diǎn)并入，再據(jù)頂點(diǎn)找最小邊；算法是逐個(gè)頂點(diǎn)并入，再據(jù)頂點(diǎn)找最小邊；上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束普里姆普里姆primprim算法求最小生成樹：算法求最小生成樹：abcdegf195141827168213ae12dcb7aaa1914180e12ee8160d3dd7210c5 0e0gd0f0設(shè)設(shè)u u代表已并入最小生成樹中的頂點(diǎn)的集合，最初任選一點(diǎn)放代表已并入最

41、小生成樹中的頂點(diǎn)的集合，最初任選一點(diǎn)放入入u u。之后找。之后找u u到到u u最小邊，將對應(yīng)新頂點(diǎn)并入，共最小邊，將對應(yīng)新頂點(diǎn)并入，共n-1n-1輪即可輪即可從頂點(diǎn)從頂點(diǎn)u u0 0開始開始, ,令令u=uu=u0 0, , 初始化初始化u0u0到其余各頂點(diǎn)距離到其余各頂點(diǎn)距離 找最小的邊輸出找最小的邊輸出, ,并入新頂點(diǎn)并入新頂點(diǎn), ,賦賦0+0+更新表更新表使使u u到非到非u u距離更小距離更小 。如上重復(fù)如上重復(fù)n-1n-1次次上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束構(gòu)造下表對應(yīng)的數(shù)組構(gòu)造下表對應(yīng)的數(shù)組,每個(gè)元素對應(yīng)一個(gè)頂點(diǎn)每個(gè)元素對應(yīng)一個(gè)頂點(diǎn),元素取值是當(dāng)前輪從元素取值是當(dāng)前輪從u到

42、該點(diǎn)最小邊的信息到該點(diǎn)最小邊的信息(出發(fā)點(diǎn)下標(biāo)和代價(jià)出發(fā)點(diǎn)下標(biāo)和代價(jià)),頂點(diǎn)被并入頂點(diǎn)被并入u后代價(jià)置后代價(jià)置0struct vertextype adjvex; /出發(fā)點(diǎn)名稱出發(fā)點(diǎn)名稱 vrtype lowcost; /代價(jià)代價(jià)closedgemax_vertex_num;aaa1914180e12ee8160d3dd7210c5 0e0d0上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束void minispantree_prim(mgraph g, vertextype u) /用普里姆算法從用普里姆算法從u出發(fā)求網(wǎng)出發(fā)求網(wǎng)g(鄰接矩陣表示鄰接矩陣表示) 最小生成樹最小生成樹,輸出各邊輸出各邊 k

43、=locatevex (g, u); closedgek.lowcost = 0; /將將u并入并入u,賦賦0 for ( j=0; jg.vexnum;+j ) /據(jù)據(jù)u更新數(shù)組元素代價(jià)更新數(shù)組元素代價(jià) if (j!=k)closedgej = u, g.arcskj.adj ; for (i=1; ik closedgek.lowcost=0; /將將k號(hào)結(jié)點(diǎn)并入號(hào)結(jié)點(diǎn)并入u，賦，賦0 for(j=0;jg.vexnum;+j)/據(jù)據(jù)k號(hào)結(jié)點(diǎn)更新數(shù)組元素代價(jià)號(hào)結(jié)點(diǎn)更新數(shù)組元素代價(jià) if (g.arcskj).adjclosedgej.lowcost closedgej=g.vexsk,g.

44、arcskj.adj; 將初始點(diǎn)將初始點(diǎn)u u并入并入u,u,初始化表初始化表;之后找小邊并入之后找小邊并入, ,賦賦0+0+更新更新 重復(fù)重復(fù)復(fù)雜度為復(fù)雜度為o(n2),與與邊數(shù)無關(guān)，適合稠邊數(shù)無關(guān)，適合稠密圖密圖上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束7.5.1 7.5.1 拓?fù)渑判蛲負(fù)渑判騪aov-網(wǎng)網(wǎng):頂點(diǎn)表示頂點(diǎn)表示活動(dòng)活動(dòng),弧表示活動(dòng)間弧表示活動(dòng)間先后先后(依賴依賴)關(guān)系關(guān)系的有向圖的有向圖.paov-網(wǎng)用以表示工程或系統(tǒng)的施工計(jì)劃，可據(jù)此判網(wǎng)用以表示工程或系統(tǒng)的施工計(jì)劃，可據(jù)此判斷工程是否可以順利進(jìn)行斷工程是否可以順利進(jìn)行paov-網(wǎng)中應(yīng)存在一個(gè)覆蓋全部頂點(diǎn)的序列網(wǎng)中應(yīng)存在一個(gè)覆蓋

45、全部頂點(diǎn)的序列(全序全序),在在該序列中頂點(diǎn)出現(xiàn)的順序滿足網(wǎng)中的先后關(guān)系該序列中頂點(diǎn)出現(xiàn)的順序滿足網(wǎng)中的先后關(guān)系(偏序偏序)。一個(gè)全序就對應(yīng)一個(gè)合法的一個(gè)全序就對應(yīng)一個(gè)合法的完整完整工序工序bdacbdac上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束由某個(gè)集合上的一個(gè)由某個(gè)集合上的一個(gè)偏序偏序得到該集合上的得到該集合上的一個(gè)一個(gè)全序全序, ,該操作稱該操作稱為為拓?fù)渑判蛲負(fù)渑判颉Ｈ舻玫揭粋€(gè)含全部頂點(diǎn)的拓?fù)溆行蛐蛄腥舻玫揭粋€(gè)含全部頂點(diǎn)的拓?fù)溆行蛐蛄? (全序全序) )則則說明工程可順利開展說明工程可順利開展, ,不存在則說明圖中存在有向回路不存在則說明圖中存在有向回路, ,不合理不合理何謂拓?fù)渑判蚝沃^

46、拓?fù)渑判騜dacabcdabcd或或acbdacbd均是含全均是含全部頂點(diǎn)的拓?fù)溆行蛐虿宽旤c(diǎn)的拓?fù)溆行蛐蛄辛?dag(dag圖圖) )bdac不存在含全部頂點(diǎn)的拓?fù)溆胁淮嬖诤宽旤c(diǎn)的拓?fù)溆行蛐蛄行蛐蛄? 存在有向回路存在有向回路bcdb上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束從有向圖中選取一沒有前驅(qū)的頂點(diǎn)并輸出之；從有向圖中選取一沒有前驅(qū)的頂點(diǎn)并輸出之；重復(fù)上述兩步，至重復(fù)上述兩步，至圖空圖空(得一全序得一全序)或圖不空但或圖不空但不存在無前驅(qū)的頂點(diǎn)不存在無前驅(qū)的頂點(diǎn)(得一有向環(huán)得一有向環(huán))。從圖中從圖中“刪除刪除”此頂點(diǎn)及所有從其出發(fā)的弧此頂點(diǎn)及所有從其出發(fā)的弧如何進(jìn)行拓?fù)渑判蛉绾芜M(jìn)行拓?fù)渑?/p>

47、序abcghdfea bc hdgfebdaca入度入度0頂點(diǎn)入棧頂點(diǎn)入棧,出棧并據(jù)此更新入度出棧并據(jù)此更新入度,零入度者入棧零入度者入棧重復(fù)至?？罩貜?fù)至?？丈享撋享?下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束3 3、拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)、拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)將入度為將入度為0的頂點(diǎn)入棧的頂點(diǎn)入棧,出棧并據(jù)此更新入度出棧并據(jù)此更新入度,如此重如此重復(fù)復(fù)status topologicalsort(algraph g)/g用鄰接表存儲(chǔ)用鄰接表存儲(chǔ),若若g無回路則輸出拓?fù)溆行蛐蛄袩o回路則輸出拓?fù)溆行蛐蛄?返返ok, 否則返否則返error. findindegree(g,indegree);/求各頂點(diǎn)入度存入數(shù)組求

48、各頂點(diǎn)入度存入數(shù)組indegreeindegree initstack(s initstack(s);); for(i=0;ig.vexnum;+i) if(!indegreei) push(s,i); count=0; /用以對輸出的頂點(diǎn)進(jìn)行計(jì)數(shù)用以對輸出的頂點(diǎn)進(jìn)行計(jì)數(shù) while (!stackempty(s) pop(s,i); printf(g.verticesi.data); +count; if(countnextarc for(p=g.verticesi.firstarc;p!=null;p=p-nextarc) k=p-adjvex k=p-adjvex; ; - -indeg

49、reek- -indegreek; /; /更新入度更新入度 if(!indegreek) push(s,wif(!indegreek) push(s,w);/);/新的入度為零的頂點(diǎn)入新的入度為零的頂點(diǎn)入棧棧 最初求入度最初求入度o(e); 第一波頂點(diǎn)入棧第一波頂點(diǎn)入棧o(n)；若為；若為dag圖則圖則每個(gè)頂點(diǎn)入棧、出棧各一次每個(gè)頂點(diǎn)入棧、出棧各一次,o(n);入度減入度減1的操作執(zhí)行的操作執(zhí)行e次次,故總復(fù)雜的度故總復(fù)雜的度o(n+e)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束作業(yè)：作業(yè)：7.7prim算法注意畫表，多張算法注意畫表，多張kruscal算法，手工執(zhí)行，直接給答案算法，手工執(zhí)行，

50、直接給答案abcdegf195141827168213ae12dcbgf71485316217121819上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束作業(yè)：作業(yè)：l9 對下圖執(zhí)行教材中的拓?fù)渑判蛩惴?，寫出得對下圖執(zhí)行教材中的拓?fù)渑判蛩惴?，寫出得到的拓?fù)溆行蛐蛄械降耐負(fù)溆行蛐蛄衋bcghdfeabcdegf195141827168213ae12dcbgf7148531621上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束7.5.2 7.5.2 關(guān)鍵路徑關(guān)鍵路徑aoe網(wǎng)網(wǎng)：頂點(diǎn)表示狀態(tài)，弧表示：頂點(diǎn)表示狀態(tài)，弧表示活動(dòng)活動(dòng)，弧權(quán)表示完成活動(dòng)所，弧權(quán)表示完成活動(dòng)所需需時(shí)間時(shí)間。用以估算工程的完成時(shí)間。用以估算工程的

51、完成時(shí)間問問:最短最短工期工期多長？哪些活動(dòng)是影響工期的多長？哪些活動(dòng)是影響工期的“關(guān)鍵活動(dòng)關(guān)鍵活動(dòng)”abcdefghk64521187244源點(diǎn)源點(diǎn)匯點(diǎn)匯點(diǎn)174關(guān)鍵路徑關(guān)鍵路徑( (長度最長的路徑長度最長的路徑) )決定工期決定工期關(guān)鍵活動(dòng)關(guān)鍵活動(dòng): :工程正常開展工程正常開展最早開始時(shí)間最早開始時(shí)間等于等于最遲開始時(shí)間最遲開始時(shí)間的活動(dòng)的活動(dòng)ee(actee(act) =) =veve( (頭頭) ) 與與 el(actel(act) )= =vlvl( (尾尾) - dur(act) - dur(act) )上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束ve(源點(diǎn)源點(diǎn))=0.對普通頂點(diǎn)對普通頂

52、點(diǎn)v,設(shè)設(shè)w為其前驅(qū)頂點(diǎn)集則為其前驅(qū)頂點(diǎn)集則ve(v)=max ve(w)+dut(w,v) | ww u如何保證求如何保證求ve(vve(v) )時(shí)時(shí)ve(wve(w) )已經(jīng)求出？已經(jīng)求出？關(guān)鍵活動(dòng)求取關(guān)鍵活動(dòng)求取求各點(diǎn)最早到達(dá)時(shí)間求各點(diǎn)最早到達(dá)時(shí)間ve(x)abcdefghk64521187244實(shí)現(xiàn)實(shí)現(xiàn):各頂點(diǎn)各頂點(diǎn)ve初始化為初始化為0,找無前驅(qū)頂點(diǎn)找無前驅(qū)頂點(diǎn),據(jù)其據(jù)其ve值值更新后更新后繼繼ve值值, “刪除刪除”如此重復(fù)如此重復(fù),至至圖空或發(fā)現(xiàn)回路圖空或發(fā)現(xiàn)回路.實(shí)際是按拓實(shí)際是按拓?fù)湫驌湫蛏享撋享?下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束status topologicalorder(a

53、lgraph g，stack &t)/求個(gè)頂點(diǎn)最早到達(dá)時(shí)間計(jì)入全局?jǐn)?shù)組求個(gè)頂點(diǎn)最早到達(dá)時(shí)間計(jì)入全局?jǐn)?shù)組ve,t按訪問順序存儲(chǔ)各頂點(diǎn)按訪問順序存儲(chǔ)各頂點(diǎn),求求vl用用 ve0.g.vexnum-1=0;ve0.g.vexnum-1=0; findindegree(g,indegree); initstack(s); initstack(s); initstack initstack t; t; for(i=0;inextarcfor(p=g.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; -indegree(k k=p-adjvex; -indeg

54、ree(k); ); if(indegreek= =0) push(s if(indegreek= =0) push(s, w);, w); if(vejif(vej+* *(p-(p-infoinfo)vek)vek=vej)vek)vek=vej+* *(p-(p-infoinfo) ) if(countnextarc) k=p-adjvex; dut=*(p-info); /對應(yīng)活動(dòng)對應(yīng)活動(dòng)的持續(xù)時(shí)間的持續(xù)時(shí)間 if( vlk-dut vlj ) vlj= vlk-dut; for(j=0;jnextarcfor(p=g.verticesj.firstarc;p;p=p-nextarc)

55、 k=p-adjvex; dut k=p-adjvex; dut= =* *(p-info);(p-info); ee=vej; el=vlk-dut ee=vej; el=vlk-dut/活動(dòng)活動(dòng)j,k 的最早的最早/ /遲開始時(shí)間遲開始時(shí)間 if(ee=el) printf(j,k,dut,ee,elif(ee=el) printf(j,k,dut,ee,el, , ); ); else printf(j,k,dut,ee,elelse printf(j,k,dut,ee,el, , ); ); 上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束棧棧t:t: a - d - f - c - b - e

56、 - h - g - kabcdefghk6452118724417400000 00006457115 715 14 1818181818181818181816 1486610807各頂點(diǎn)各頂點(diǎn)vlvl初始化成工期，按拓?fù)淠嫘虺跏蓟晒て冢赐負(fù)淠嫘?t(t的出棧順序的出棧順序) )逐個(gè)逐個(gè)更新該元素的更新該元素的vlvl上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束064577 15 14 18181416107866000 0 64 5 7 77 15 1414160 23 66 8 87 100 230 2630 26630 286630 2886630 27886630 210788663

57、0 216107886630 21416107886630 2ee作業(yè)題作業(yè)題1 1：7.10 7.10 求關(guān)鍵活動(dòng)求關(guān)鍵活動(dòng)上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束l單源最短路徑l每一對頂點(diǎn)之間的最短路徑7.6 7.6 最短路徑（最短路徑（p187p187）上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束集合集合s s存放已找到最短路的頂點(diǎn)存放已找到最短路的頂點(diǎn)將源并入將源并入s,s,初始化初始化源源到到v-sv-s中各中各頂點(diǎn)的最短路徑頂點(diǎn)的最短路徑在在v-sv-s中找長度最小的頂點(diǎn)并入中找長度最小的頂點(diǎn)并入s,s,據(jù)此更新?lián)烁略僬以俑略僬以俑? ,共重復(fù)共重復(fù)n-1n-1輪輪v0v1v2v4

58、v5100301050510v36020終點(diǎn)終點(diǎn)路徑路徑長度長度v0v0-v00v1v2v0-v210v3v4v0-v430v5v0-v5100終點(diǎn)終點(diǎn)路徑路徑長度長度v0v0-v00v1v2v0-v210v3v0v2v360v4v0-v430v5v0-v5100終點(diǎn)終點(diǎn)路徑路徑距離距離v0v0-v00v1v2v0-v210v304350v4v0-v430v504590.1單源最短路徑單源最短路徑-dijkstra-dijkstra算法算法上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束迪杰斯特拉算法實(shí)現(xiàn)：迪杰斯特拉算法實(shí)現(xiàn)：設(shè)輔助數(shù)組設(shè)輔助數(shù)組d,dkd,dk 存儲(chǔ)當(dāng)前所存儲(chǔ)當(dāng)前所得從

59、源到頂點(diǎn)得從源到頂點(diǎn)k k的最短路長度的最短路長度finalkfinalk 標(biāo)記標(biāo)記k k號(hào)頂點(diǎn)已并入號(hào)頂點(diǎn)已并入s spvwpvw 標(biāo)記源到標(biāo)記源到v v的最短路上的最短路上w w是否出現(xiàn)是否出現(xiàn)for(v=0;vg.vexnum;+vfor(v=0;vg.vexnum;+v) ) finalv finalv=false=false;/;/最初未得最初未得源點(diǎn)源點(diǎn)v0v0到到v v的最短路的最短路 for(w=0;wg.vexnum;+wfor(w=0;wg.vexnum;+w) ) pvw pvw=false;=false;/最短路最初為空最短路最初為空, ,不含任何頂點(diǎn)不含任何頂點(diǎn) dv

60、dv=g.arcsv0v; =g.arcsv0v; /根據(jù)根據(jù)v0v0更新更新 if(dvinfinity)pvv0=true;pvvif(dvv00v1v2v0-v210v3v4v0-v430v5v0-v5100上頁上頁 下頁下頁節(jié)節(jié)末頁末頁結(jié)束結(jié)束每次循環(huán)都找距離最小新頂點(diǎn)并入每次循環(huán)都找距離最小新頂點(diǎn)并入s s，更新，重復(fù)，更新，重復(fù)n-1n-1輪輪終點(diǎn)終點(diǎn)路徑路徑距離距離v0v0-v00v1v2v0-v210v3v4v0-v430v5v0-v5100終點(diǎn)終點(diǎn)路徑路徑長度長度v0v0-v00v1v2v0-v210v3v0v2v360v4v0-v430v5v0-v5100v0v1v2v4v