數(shù)據(jù)結(jié)構(gòu)圖結(jié)構(gòu)動態(tài)

本章主要介紹圖的基本概念、圖的存儲結(jié)構(gòu)和有關(guān)圖的一些常用算法。通過本章學(xué)習(xí)，讀者應(yīng)該：1)

了解圖的定義和術(shù)語

2)掌握圖的各種存儲結(jié)構(gòu)3)

掌握圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法

4)

理解最小生成樹、最短路徑、拓?fù)渑判?、關(guān)鍵路徑等圖的常用算法

本章學(xué)習(xí)導(dǎo)讀

當(dāng)前第1頁\共有141頁\編于星期五\0點1

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

當(dāng)前第2頁\共有141頁\編于星期五\0點2

7.1圖的定義

7.2圖的存儲結(jié)構(gòu)

7.3圖的遍歷

7.4圖的連通性問題

7.5有向無環(huán)圖及其應(yīng)用

7.6最短路徑

第七章圖當(dāng)前第3頁\共有141頁\編于星期五\0點3

圖定義

圖G由兩個集合V和E組成，記為G=(V,E)

其中，V是頂點的有窮非空集合，

E是V中頂點偶對的有窮集，這些頂點偶對稱為邊。通常V(G)和E(G)分別稱為圖的頂點集合和邊集合。注：E(G)可以為空集。7.1圖的定義和術(shù)語當(dāng)前第4頁\共有141頁\編于星期五\0點47.1圖的定義和術(shù)語圖的數(shù)據(jù)結(jié)構(gòu)的形式化定義（p156）

G=(V,E)

其中V={x|xdataobject}

E={VR}VR={<x,y>|p(x,y)(x,yV)}VR是兩頂點間的關(guān)系的集合，即邊的集合。當(dāng)前第5頁\共有141頁\編于星期五\0點5圖的術(shù)語有向圖:

對一個圖G，若邊集E(G)為有向邊的集合，則稱該圖為有向圖。①②③④G1G1=（V，E）V={v1,v2,v3,v4}E={<v1,v2>,<v1,v3>,<v3,v4>,<v4,v1>}其中<x,y>表示從x到y(tǒng)的一條?。╝rc），A為弧集合，x為弧尾（tail），y為弧頭（head)x弧尾y弧頭當(dāng)前第6頁\共有141頁\編于星期五\0點6圖的術(shù)語無向圖:對一個圖G，若邊集E(G)為無向邊的集合，則稱該圖為無向圖。

①②G2③④⑤

G2=（V，E）V={v1,v2,v3,v4,v5}E={(v1,v2),(v1,v3),(v2,v3),(v3,v4),(v2,v5),(v3,v5)}其中，(x,y)表示x與y之間的一條連線，稱為邊（edge）當(dāng)前第7頁\共有141頁\編于星期五\0點7圖的術(shù)語設(shè)n為頂點數(shù)，e為邊或弧的條數(shù)

對無向圖有：0≤e≤

n(n-1)/2

有向圖有：0≤e≤n(n-1)證明：對有向圖，每個頂點至多有n-1條邊與其它的n-1個頂點相連，則n個頂點至多有n(n-1)條邊。但對無向圖，每條邊連接2個頂點，故最多為n(n-1)/2

當(dāng)前第8頁\共有141頁\編于星期五\0點8圖的術(shù)語端點和鄰接點

在一個無向圖中，若存在一條邊<vi,vj>,則稱vi，vj為該邊的兩個端點，并稱它們互為鄰結(jié)點。

21453G2當(dāng)前第9頁\共有141頁\編于星期五\0點9圖的術(shù)語起點和終點

在一個有向圖中，若存在一條邊<vi,vj>,則稱該邊是頂點vi的一條出邊，是vj的一條入邊，稱vi是起始端點（或起點），稱vj是終止端點（或終點）,并稱它們互為鄰結(jié)點.2134G1當(dāng)前第10頁\共有141頁\編于星期五\0點10圖的術(shù)語度

圖中每個頂點的度是以該頂點為一端點的邊的數(shù)目。記為D(V)。入度和出度

對于有向圖，入度為以該頂點為終點的邊的數(shù)目，出度為以該頂點為起點的邊的數(shù)目。例D(v1)=3

無向圖的度數(shù)為依附于頂點v的邊數(shù)；有向圖的度數(shù)等于以頂點v為弧頭的弧數(shù)與以頂點v為弧尾的弧數(shù)之和21453G22134G1例D(v1)=2

當(dāng)前第11頁\共有141頁\編于星期五\0點11圖的術(shù)語子圖

設(shè)有兩個圖G=（V，E）

G’=（V’，E’）中，若V’是V的子集，E’是E的子集，則稱G’是G子圖。①①④①③④⑤

①②③④⑤

①②G2③④⑤

當(dāng)前第12頁\共有141頁\編于星期五\0點12圖的術(shù)語簡單圖

對不含多重邊和自環(huán)的圖。2145321453簡單圖非簡單圖當(dāng)前第13頁\共有141頁\編于星期五\0點13圖的術(shù)語完全圖

邊達到最大的圖無向完全圖：具有n(n-1)/2條邊的簡單圖稱為無向完全圖有向完全圖：具有n(n-1)條邊的有向圖。稀疏圖：

邊或弧很少的圖。稠密圖：

邊或弧很多的圖。

權(quán)：與圖的邊或弧相關(guān)的數(shù)。

網(wǎng)：邊或弧上帶有權(quán)值的圖。當(dāng)前第14頁\共有141頁\編于星期五\0點14圖的術(shù)語路徑

非空有限點、弧交替序列，

W=v0,a1,v1,…,ak,vk

使得i=1,2,…k,

弧ai的頭vi,尾為vi-1

。

路徑長度：路徑上邊或弧的數(shù)目當(dāng)前第15頁\共有141頁\編于星期五\0點15圖的術(shù)語簡單路徑：除首尾兩點外，其他各點都不相同的路徑稱為簡單路徑。簡單路徑當(dāng)前第16頁\共有141頁\編于星期五\0點16圖的術(shù)語回路:無重復(fù)邊的閉路徑。環(huán)：閉的簡單路徑，稱為環(huán)?；芈返皇黔h(huán)環(huán)當(dāng)前第17頁\共有141頁\編于星期五\0點17圖的術(shù)語連通圖：任何兩點都有路徑的圖。

無向圖：若圖中任意兩個頂點vi,vj都是連通

的，則稱該圖是連通圖(vi<>vj)有向圖：若圖中任意兩個頂點vi,vj，都存在

從vi到vj和從vj到vi的路徑，則稱

該有向圖為強連通圖

(vi<>vj)當(dāng)前第18頁\共有141頁\編于星期五\0點18圖的術(shù)語連通分量：

無向圖：無向圖中極大連通子圖，稱為

連通分量

有向圖：有向圖中極大強連通子圖，稱為

強連通分量當(dāng)前第19頁\共有141頁\編于星期五\0點19生成樹圖的術(shù)語生成樹

一個連通圖的生成樹是一個極小連通子圖，它含有圖中全部頂點，但只有足以構(gòu)成一棵樹的n-1條邊。

①②④⑤

①②④⑤

①②④⑤

①②④⑤

有向樹

如果一個有向圖恰有一個頂點入度為0，其余頂點的入度均為1，則是一棵有向樹。

當(dāng)前第20頁\共有141頁\編于星期五\0點20生成樹、生成森林生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。生成樹是對連通圖而言的是連通圖的極小連通子圖包含圖中的所有頂點有且僅有n-1條邊

非連通圖的生成樹則組成一個生成森林。若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。

一個有向圖的生成森林由若干棵有向樹組成，含有圖中全部頂點，但只有足以構(gòu)成若干棵不相交的有向樹的弧。當(dāng)前第21頁\共有141頁\編于星期五\0點21圖有兩種存儲結(jié)構(gòu)

鄰接矩陣鄰接表7.2圖的存儲結(jié)構(gòu)當(dāng)前第22頁\共有141頁\編于星期五\0點227.2.1鄰接矩陣鄰接矩陣(AdjacencyMatrix)是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G＝(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣。7.2圖的存儲結(jié)構(gòu)

無向圖的鄰接矩陣是以主對角線對稱的，有向圖的鄰接矩陣可能是不對稱的。在有向圖中：第i行1的個數(shù)就是頂點i的出度，第j列1的個數(shù)就是頂點j的入度。在無向圖中,第i行(列)1的個數(shù)就是頂點i的度。當(dāng)前第23頁\共有141頁\編于星期五\0點23一、鄰接矩陣（用二維數(shù)組表示）例如：G1的鄰接矩陣?yán)纾篏2的鄰接矩陣無向圖的鄰接矩陣為對稱矩陣G212345G11234當(dāng)前第24頁\共有141頁\編于星期五\0點24

對于無向圖，（vi，vj）和（vj，vi）表示同一條邊，因此，在鄰接矩陣中Aij=Aji。無向圖的鄰接矩陣是（關(guān)于主對角線）對稱矩陣，可用主對角線以上（或以下）的部分表示。對有向圖，弧<vi，vj>和<vj，vi>表示方向不同的兩條弧，Aij和Aji表示不同的弧，所以有向圖的鄰接矩陣一般不具有對稱性。

鄰接矩陣表示法適合于以頂點為主的運算。

當(dāng)前第25頁\共有141頁\編于星期五\0點25

對于有向圖，頂點vi的出度OD(vi)等于鄰接矩陣第i行元素之和；頂點vi的入度ID(vi)等于鄰接矩陣第i列元素之和，即：

對于無向圖，頂點vi的度等于鄰接矩陣第i行的元素之和，即：

OD(vi)=

ID(vi)=

TD（vi）=當(dāng)前第26頁\共有141頁\編于星期五\0點26若G是網(wǎng)（有權(quán)圖），鄰接矩陣定義為V2V1V3V435214如圖：

Wij若<vi,vj>

或<vj,vi>

∈E(G)A[i，j]=

0或若其它V1V2V3V4V1V2V3V4當(dāng)前第27頁\共有141頁\編于星期五\0點27

頂點表:一個記錄各個頂點信息的一維數(shù)組，

鄰接矩陣：一個表示各個頂點之間的關(guān)系（邊或?。┑亩S數(shù)組。

使用鄰接矩陣存儲結(jié)構(gòu)，可用一維數(shù)組表示圖的頂點集合，用二維數(shù)組表示圖的頂點之間關(guān)系（邊或弧）的集合，數(shù)據(jù)類型定義如下：

#defineMAX_VERTEX_NUM20//最大頂點數(shù)typedefintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣類型typedefstruct{ VertexTypevexs[MAX_VERTEX_NUM];//頂點表

AdjMatrixarcs;//鄰接矩陣

intvexnum，arcnum;//圖的頂點數(shù)和弧數(shù)}MGraph;

由于一般圖的邊或弧較少，其鄰接矩陣的非零元素較少，屬稀疏矩陣，因此會造成一定存儲空間的浪費。

當(dāng)前第28頁\共有141頁\編于星期五\0點28

鄰接表

圖的鏈?zhǔn)酱鎯Y(jié)構(gòu)1)為每個頂點建立一個單鏈表，2)第i個單鏈表中包含頂點Vi的所有鄰接頂點。

鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。類似于樹的孩子鏈表表示法。在鄰接表中為圖中每個頂點建立一個單鏈表，用單鏈表中的一個結(jié)點表示依附于該頂點的一條邊（或表示以該頂點為弧尾的一條?。Q為邊（或?。┙Y(jié)點。

當(dāng)前第29頁\共有141頁\編于星期五\0點2925341543533412212123451.無向圖鄰接表G212345adjvexnextarcvexdatafirstarc當(dāng)前第30頁\共有141頁\編于星期五\0點302.有向圖鄰接表234143121234如圖G1的鄰接表為：G11234當(dāng)前第31頁\共有141頁\編于星期五\0點31

在鄰接表的邊鏈表中，各個邊結(jié)點的鏈入順序任意，視邊結(jié)點輸入次序而定。設(shè)圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結(jié)點，2e個邊結(jié)點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結(jié)點，e個邊結(jié)點。建立鄰接表的時間復(fù)雜度為O(n*e)。若頂點信息即為頂點的下標(biāo)，則時間復(fù)雜度為O(n+e)。當(dāng)前第32頁\共有141頁\編于星期五\0點32存儲表示typedefstructArcNode{ intadjvex;//該弧所指向的頂點的位置 structArcNode*nextarc;//指向下一條弧的指針int*

info;//該弧相關(guān)信息的指針}ArcNode;//邊結(jié)點類型typedefstructVNode{ VertexTypedata;//頂點信息 ArcNode*firstarc;//指向第一條依附該頂點的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];//鄰接表typedefstruct{ AdjListvertices;intvexnum,arcnum;//圖的當(dāng)前頂點數(shù)和弧數(shù)intkind;

//圖的種類標(biāo)志}ALGraph;當(dāng)前第33頁\共有141頁\編于星期五\0點3325341543533412212123451.無向圖鄰接表二、鄰接表G212345adjvexnextarcvexdatafirstarc當(dāng)前第34頁\共有141頁\編于星期五\0點341.無向圖鄰接表對圖中每個頂點Vi建立一個單鏈表，鏈表中的結(jié)點表示依附于頂點Vi的邊，每個鏈表結(jié)點為兩個域.其中：鄰接點域（adjvex）記載與頂點Vi鄰接的頂點信息；鏈域（nextarc）指向下一個與頂點Vi鄰接的鏈表p結(jié)點每個鏈表設(shè)一個頭結(jié)點，

頭結(jié)點結(jié)構(gòu)為：其中：vexdata存放頂點信息（姓名、編號等）；

firstarc指向鏈表的第一個結(jié)點。二、鄰接表adjvexnextarcvexdatafirstarc當(dāng)前第35頁\共有141頁\編于星期五\0點35二、鄰接表（adjacencylist）如圖G2的鄰接表為：2534154353341221212345G212345當(dāng)前第36頁\共有141頁\編于星期五\0點36BACDFE例20A141B0452C353D254E015F123當(dāng)前第37頁\共有141頁\編于星期五\0點372.有向圖鄰接表234143121234特點：1.n個頂點，e條弧的有向圖，需n個表頭結(jié)點，e個表結(jié)點2.第i條鏈表上的結(jié)點數(shù)，為Vi的出度（求頂點的出度易，求入度難）如圖G1的鄰接表為：G11234當(dāng)前第38頁\共有141頁\編于星期五\0點38142301201234

ABCDE2.有向圖的鄰接表ABECF可見，在有向圖的鄰接表中不易找到指向該頂點的弧。當(dāng)前第39頁\共有141頁\編于星期五\0點393.有向圖逆鄰接表123411431234此時，第i條鏈表上的結(jié)點數(shù)，為Vi的入度如圖G1的逆鄰接表為：①②③④G1當(dāng)前第40頁\共有141頁\編于星期五\0點40ABECD有向圖的逆鄰接表ABCDE30342001234在有向圖的鄰接表中，對每個頂點，鏈接的是指向該頂點的弧。在有向圖的鄰接表中，第i

個鏈表中結(jié)點的個數(shù)是頂點Vi的出度。在有向圖的逆鄰接表中，第i

個鏈表中結(jié)點的個數(shù)是頂點Vi

的入度。當(dāng)前第41頁\共有141頁\編于星期五\0點414.帶權(quán)有向圖的鄰接表鏈表中每個結(jié)點為三個域.

鄰接點權(quán)帶權(quán)圖的邊結(jié)點中info保存該邊上的權(quán)值。當(dāng)前第42頁\共有141頁\編于星期五\0點42ABECD4.帶權(quán)有向圖的鄰接表ABCDE0123411037^04

4223^28^102254837125^頂點Vi的邊鏈表的頭結(jié)點存放在下標(biāo)為i的頂點數(shù)組中。當(dāng)前第43頁\共有141頁\編于星期五\0點43

十字鏈表

十字鏈表(OrthogonalList)是有向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。

可看作是將有向圖的鄰接表和逆鄰接表結(jié)合的一種鏈表。

在十字鏈表中，為每個頂點vi設(shè)置一個結(jié)點，它包含數(shù)據(jù)域data和兩個鏈域firstout、firstin，稱為頂點結(jié)點。數(shù)據(jù)域data用于存放頂點vi的有關(guān)信息；鏈域firstin指向以頂點vi為弧頭的第一個弧結(jié)點；鏈域firstout指向以頂點vi為弧尾的第一個弧結(jié)點。

弧結(jié)點包括四個域：尾域tailvex、頭域headvex，鏈域hlink和tlink。

hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條弧；data頂點信息，firstin以該頂點為頭的第一個弧結(jié)點，firstout以該結(jié)點為尾的第一個弧結(jié)點。

起點vi終點vjhlinktlink弧結(jié)構(gòu)頂點結(jié)構(gòu)

datafirstinfirstout當(dāng)前第44頁\共有141頁\編于星期五\0點44圖7-8十字鏈表

圖7-8為圖7-6(a)有向圖的十字鏈表。見右圖

采用十字鏈表表示有向圖，很容易找到以頂點vi為弧尾的弧和以頂點vi為弧頭的弧，因此頂點的出度、入度都很容易求得。

當(dāng)前第45頁\共有141頁\編于星期五\0點45十字鏈表的數(shù)據(jù)類型定義如下：

#defineMAXV<最大頂點個數(shù)>typedefstructArcbox//弧結(jié)點{inttailvex,headvex;//弧尾和弧頭頂點位置

structArcNode*hlink,*tlink;//弧頭相同和弧尾相同的弧的鏈域}ArcBox;typedefstructVexNode//頂點結(jié)點{VertexTypedata;//頂點信息

ArcNode*firstin,*firstout;//分別指向該頂點的第一條入弧和出弧}VexNode;當(dāng)前第46頁\共有141頁\編于星期五\0點467.2.4鄰接多重表

鄰接多重表是無向圖的另一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接多重表中設(shè)置一個邊結(jié)點表示圖中的一條邊。邊結(jié)點包含五個域，結(jié)構(gòu)如下所示：

其中:mark域

標(biāo)志域，用于對該邊進行標(biāo)記；ivex域

存放該邊依附的一個頂點vi的位置信息；ilink域

該鏈域指向依附于頂點vi的另一條邊的邊結(jié)點；jvex域

存放該邊依附的另一個頂點vj的位置信息；jlink域

該鏈域指向依附于頂點vj的另一條邊的邊結(jié)點。鄰接多重表為每個頂點設(shè)置一個結(jié)點，其結(jié)構(gòu)如下：

當(dāng)前第47頁\共有141頁\編于星期五\0點47圖7-9鄰接多重表

圖7-9為圖7-5(a)無向圖的鄰接多重表。

由鄰接多重表可以看出，表示邊（vi，vj）的邊結(jié)點通過鏈域ilink和jlink鏈入了頂點vi和頂點vj的兩個鏈表中，實現(xiàn)了用一個邊結(jié)點表示一個邊的目的，克服了在鄰接表中用兩個邊結(jié)點表示一個邊的缺點。因此鄰接多重表是無向圖的一種很有效的存儲結(jié)構(gòu)。

當(dāng)前第48頁\共有141頁\編于星期五\0點48鄰接多重表的結(jié)點數(shù)據(jù)類型定義如下：

#defineMAXV<最大頂點個數(shù)>typedefstruct//邊結(jié)點類型{intmark;//訪問標(biāo)識

intivex,jvex;//該邊的兩個頂點位置信息

structEnode*ilink,*jlink;//分別指向依附這兩個頂點的下一條邊}Enode;typedefstruct//頂點結(jié)點類型{VertexTypedata;//頂點數(shù)據(jù)域

ENode*firstedge;//指向第一條依附該頂點的邊}Vnode;

當(dāng)前第49頁\共有141頁\編于星期五\0點497.3圖的遍歷

和樹的遍歷相似，若從圖中某頂點出發(fā)訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷。(TraversingGraph)。

圖的遍歷遠(yuǎn)比樹的遍歷復(fù)雜。因為從樹根到達樹的某個結(jié)點只有一條路徑，而圖的兩個頂點之間可能有多條路徑。

因此，在圖的遍歷過程中，可能會出現(xiàn)下面的現(xiàn)象，即在順著一條路徑訪問了某個頂點后，可能會沿著另一條路徑又回到該頂點。

為避免一個頂點被多次訪問，我們設(shè)置一個標(biāo)志數(shù)組

intvisited[MAX_VERTEX_NUM];它的元素初值為0。一旦vi被訪問了，便置相應(yīng)數(shù)組元素為1.

圖的遍歷方法有：這兩種方法對無向圖和有向圖都適用。

深度優(yōu)先搜索遍歷（簡稱DFS）廣度優(yōu)先搜索遍歷（簡稱BFS）當(dāng)前第50頁\共有141頁\編于星期五\0點50

深度優(yōu)先搜索（DFS）1．深度優(yōu)先搜索遍歷過程：

DFS在訪問圖中某一起始頂點v后，由

v出發(fā)，訪問它的任一鄰接頂點w1；再從w1出發(fā)，訪問與w1鄰接但還沒有訪問過的頂點w2；然后再從w2出發(fā)，進行類似的訪問，…如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。

接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。當(dāng)前第51頁\共有141頁\編于星期五\0點51

深度優(yōu)先搜索的示例

圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。為了避免重復(fù)訪問，可設(shè)置一個標(biāo)志頂點是否被訪問過的輔助數(shù)組visited[]，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點i

被訪問，就立即讓visited[i]為1，防止它被多次訪問。當(dāng)前第52頁\共有141頁\編于星期五\0點52

對上圖，深度優(yōu)先搜索遍歷的順序（之一）為：

v1

→v2→v4→v8→v5→v6→v3→v7。

圖7-10深度優(yōu)先搜索

當(dāng)前第53頁\共有141頁\編于星期五\0點53深度優(yōu)先搜索算法：intvisited[MAX_VERTEX_NUM];voidDFS(ALGraphG,intv){ArcNode*p;printf("%c",G.vertices[v].data);visited[v]=1;p=G.vertices[v].firstarc;while(p)

{if(!visited[p->adjvex])DFS(G,p->adjvex);p=p->nextarc;

}}//從第v個頂點出發(fā)DFS

當(dāng)前第54頁\共有141頁\編于星期五\0點54整個圖的DFS遍歷voidDFSTraverse(ALGraphG){for(intv=0;v<G.vexnum;++v)visited[v]=0;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v);}

對于連通圖，從一個頂點出發(fā)，調(diào)用DFS函數(shù)即可將所有頂點都遍歷到。當(dāng)前第55頁\共有141頁\編于星期五\0點55

廣度優(yōu)先搜索（BFS）1．廣度優(yōu)先搜索思想

廣度優(yōu)先搜索遍歷類似于樹的按層次遍歷。對于無向連通圖，廣度優(yōu)先搜索是從圖的某個頂點v0出發(fā)，在訪問v0之后，依次搜索訪問v0的各個未被訪問過的鄰接點w1，w2，…。然后順序搜索訪問w1的各未被訪問過的鄰接點，w2的各未被訪問過的鄰接點，…。即從v0開始，由近至遠(yuǎn)，按層次依次訪問與v0有路徑相通且路徑長度分別為1，2，…的頂點，直至連通圖中所有頂點都被訪問一次。廣度優(yōu)先搜索的順序不是唯一的，例如圖7-10(a)連通圖的廣度優(yōu)先搜索遍歷順序可為v1，v2，v3，v4，v5，v6，v7，v8

也可為v1，v3，v2，v7，v6，v5，v4，v8。

當(dāng)前第56頁\共有141頁\編于星期五\0點56

廣度優(yōu)先搜索在搜索訪問一層時，需要記住已被訪問的頂點，以便在訪問下層頂點時，從已被訪問的頂點出發(fā)搜索訪問其鄰接點。所以在廣度優(yōu)先搜索中需要設(shè)置一個隊列Queue，使已被訪問的頂點順序由隊尾進入隊列。在搜索訪問下層頂點時，先從隊首取出一個已被訪問的上層頂點，再從該頂點出發(fā)搜索訪問它的各個鄰接點。

廣度優(yōu)先搜索過程 廣度優(yōu)先生成樹廣度優(yōu)先搜索的示例當(dāng)前第57頁\共有141頁\編于星期五\0點57廣度優(yōu)先搜索過程可描述為：（1）f=0;r=0;//隊列初始化，空隊列；f-隊首指針，r-隊尾指針（2）訪問v0;（3）visited[v0]=1;（4）insert(Queue,f,r,v0);//v0進入隊尾（5）whilef>0do(i)delete(Queue,f,r,x);//隊首元素出隊并賦于x(ii)對所有x的鄰接點wifvisited[w]=0then（a）訪問w;（b）visited[w]=1;（c）insert(Queue,f,r,w);//w進隊列

當(dāng)前第58頁\共有141頁\編于星期五\0點58

voidBFSseach(GraphG,intVisited[],intn){for(v=0;v<n;++v)visited[v]=0;//初始化訪問標(biāo)志

InitQueue(Q);//置空的輔助隊列Qfor(v=0;v<G.vexnum;++v)if(!visited[v]){//v尚未訪問visited[v]=1;Visit(v);//訪問uEnQueue(Q,v);

//v入隊列while(!QueueEmpty(Q)){u=DeQueue(Q,u);//隊頭元素出隊并置為ufor(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w))

if(!visited[w])

{

visited[w]=1;Visit(w);EnQueue(Q,w);

//訪問的頂點w入隊列

}//if}//while}//BFSTraverse當(dāng)前第59頁\共有141頁\編于星期五\0點59課堂練習(xí)練習(xí)1、寫出右圖的鄰接矩陣表示。ACBDEF當(dāng)前第60頁\共有141頁\編于星期五\0點60課堂練習(xí)練習(xí)2、寫出右圖的鄰接表表示。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧當(dāng)前第61頁\共有141頁\編于星期五\0點61課堂練習(xí)練習(xí)3、根據(jù)右圖的如下存儲表示，寫出以頂點A為出發(fā)點進行DFS的頂點訪問序列。ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，D，E，F(xiàn)，C當(dāng)前第62頁\共有141頁\編于星期五\0點62課堂練習(xí)ACBDEF543210FE∧DCBA

1

2∧

0

4

5∧

3

5∧

3∧

4∧A，B，C，D，E，F(xiàn)練習(xí)4、根據(jù)右圖的如下存儲表示，寫出以頂點A為出發(fā)點進行BFS的頂點訪問序列。當(dāng)前第63頁\共有141頁\編于星期五\0點63使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個頂點的連通網(wǎng)絡(luò)的生成樹有n個頂點、n-1條邊。構(gòu)造最小生成樹的準(zhǔn)則必須使用且僅使用該網(wǎng)絡(luò)中的n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點；不能使用產(chǎn)生回路的邊；各邊上的權(quán)值的總和達到最小。7.4

最小生成樹

當(dāng)前第64頁\共有141頁\編于星期五\0點64普里姆(Prim)算法普里姆算法的基本思想：從連通網(wǎng)絡(luò)N={V,E}中的某一頂點u0出發(fā),選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0,v),將其頂點加入到生成樹頂點集合U中。 以后每一步從一個頂點在U中,而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續(xù)下去,直到網(wǎng)絡(luò)中的所有頂點都加入到生成樹頂點集合U中為止。采用鄰接矩陣作為圖的存儲表示。當(dāng)前第65頁\共有141頁\編于星期五\0點65252510504613228102514242216185046132504613210原圖(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212當(dāng)前第66頁\共有141頁\編于星期五\0點66普里姆(Prim)算法在構(gòu)造過程中，還設(shè)置了兩個輔助數(shù)組：

lowcost[]存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點的各邊上的當(dāng)前最小權(quán)值；nearvex[]記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近(即權(quán)值最小)。5046132281025142422161812當(dāng)前第67頁\共有141頁\編于星期五\0點67普里姆(Prim)算法若選擇從頂點0出發(fā)，即u0=0，則兩個輔助數(shù)組的初始狀態(tài)為：02810

-1000000

lowcostnearvex01234565046132281025142422161812當(dāng)前第68頁\共有141頁\編于星期五\0點68然后反復(fù)做以下工作在lowcost[]中選擇nearvex[i]-1&&lowcost[i]最小的邊,用v標(biāo)記它。則選中的權(quán)值最小的邊為(nearvex[v],v),相應(yīng)的權(quán)值為lowcost[v]。將nearvex[v]改為-1,表示它已加入生成樹頂點集合,將邊(nearvex[v],v,lowcost[v])加入生成樹的邊集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成樹頂點集合外各頂點i到剛加入該集合的新頂點v的距離Edge[v][i]與原來它們到生成樹頂點集合中頂點的最短距離lowcost[i]做比較,取距離近的作為這些集合外頂點到生成樹頂點集合內(nèi)頂點的最短距離。如果生成樹頂點集合外頂點i到剛加入該集合的新頂點v的距離比原來它到生成樹頂點集合中頂點的最短距離還要近，則修改nearvex[i]:nearvex[i]=v。表示生成樹外頂點i到生成樹內(nèi)頂點v當(dāng)前距離最近。當(dāng)前第69頁\共有141頁\編于星期五\0點6902810

-1000000

lowcostnearvex0123456選v=5選邊(0,5)當(dāng)前第70頁\共有141頁\編于星期五\0點70頂點v=5加入生成樹頂點集合：02825

10

-10005

-10

lowcostnearvex0123456選v=4選邊(5,4)50461322810251424221618原圖邊(0,5,10)

加入生成樹1204613210255當(dāng)前第71頁\共有141頁\編于星期五\0點710123456頂點v=4加入生成樹頂點集合：02822

2510

24

-100

4

-1-1

4

lowcostnearvex選v=3選邊(4,3)50461322810251424221618原圖邊(5,4,25)

加入生成樹125046132102522當(dāng)前第72頁\共有141頁\編于星期五\0點72頂點v=3加入生成樹頂點集合：02812

222510

18

-103

-1-1-1

3

lowcostnearvex0123456選v=2選邊(3,2)50461322810251424221618原圖邊(4,3,22)

加入生成樹12504613210252212當(dāng)前第73頁\共有141頁\編于星期五\0點73lowcostnearvex0123456頂點v=2加入生成樹頂點集合：0

16

1222251018

-1

2

-1-1-1-13

選v=1選邊(2,1)50461322810251424221618原圖邊(3,2,12)

加入生成樹125041321025221612當(dāng)前第74頁\共有141頁\編于星期五\0點74頂點v=1加入生成樹頂點集合：01612222510

14

-1-1

-1

-1-1-1

1

lowcostnearvex0123456選v=6選邊(1,6)50461322810251424221618原圖邊(2,1,16)

加入生成樹125046132102514221612當(dāng)前第75頁\共有141頁\編于星期五\0點75lowcostnearvex0123456頂點v=6加入生成樹頂點集合：0161222251014

-1-1

-1

-1-1-1-1

50461322810251424221618原圖邊(1,6,14)

加入生成樹125046132102514221612最后生成樹中邊集合里存入得各條邊為：

(0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)當(dāng)前第76頁\共有141頁\編于星期五\0點76采用鄰接表作為存儲結(jié)構(gòu)：設(shè)置一個輔助數(shù)組closedge[]：

lowcost域存放生成樹頂點集合內(nèi)頂點到生成樹外各頂點的各邊上的當(dāng)前最小權(quán)值；即存放在V-U中各個頂點到集合U中的當(dāng)前最小權(quán)值；

adjvex域記錄生成樹頂點集合外各頂點距離集合內(nèi)哪個頂點最近(即權(quán)值最小)。即記錄該邊所依附的在U中的頂點。當(dāng)前第77頁\共有141頁\編于星期五\0點77利用普里姆算法建立最小生成樹:---了解（P175）typedefintVRType;struct{ VertexTypeadjvex; VRTypelowcost;}closedge[MAX_VERTEX_NUM];voidMiniSpanTree_PRIM(MGraphG,VertexTypeu){ intk,j,i,minCost; k=LocateVex(G,u); for(j=0;j<G.vexnum;++j) if(j!=k){ closedge[j].adjvex=u; closedge[j].lowcost=G.arcs[k][j];}當(dāng)前第78頁\共有141頁\編于星期五\0點78closedge[k].lowcost=0;for(i=1;i<G.vexnum;++i){k=minimum(closedge);minCost=INFINITY;for(j=0;j<G.vexnum;++j){if(closedge[j].lowcost<minCost&&closedge[j].lowcost!=0){minCost=closedge[j].lowcost; k=j;}}printf("(%c,%c)\n",closedge[k].adjvex,G.vexs[k]);closedge[k].lowcost=0;for(j=0;j<G.vexnum;++j)if(G.arcs[k][j]<closedge[j].lowcost){closedge[j].adjvex=G.vexs[k]; closedge[j].lowcost=G.arcs[k][j];}}}當(dāng)前第79頁\共有141頁\編于星期五\0點79

普里姆算法中的第二個for循環(huán)語句頻度為n-1，其中包含的兩個內(nèi)循環(huán)頻度也都為n-1，因此普里姆算法的時間復(fù)雜度為O(n2)。普里姆算法的時間復(fù)雜度與邊數(shù)e無關(guān)，該算法更適合于求邊數(shù)較多的帶權(quán)無向連通圖的最小生成樹。

當(dāng)前第80頁\共有141頁\編于星期五\0點80克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的基本思想：設(shè)一個有n個頂點的連通網(wǎng)絡(luò)N={V,E},最初先構(gòu)造一個只有n個頂點,沒有邊的非連通圖T={V,},圖中每個頂點自成一個連通分量。當(dāng)在

E中選到一條具有最小權(quán)值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中;否則將此邊舍去，重新選擇一條權(quán)值最小的邊。如此重復(fù)下去,直到所有頂點在同一個連通分量上為止。當(dāng)前第81頁\共有141頁\編于星期五\0點81應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程10504613228102514242216181250461325046132原圖(a)(b)當(dāng)前第82頁\共有141頁\編于星期五\0點821012504613228102514242216181250461325046132101412原圖(c)(d)504613210141612(e)(f)(g)504613210142216125046121025142216123當(dāng)前第83頁\共有141頁\編于星期五\0點83為實現(xiàn)克魯斯卡爾算法需要設(shè)置一維輔助數(shù)組E，按權(quán)值從小到大的順序存放圖的邊，數(shù)組的下標(biāo)取值從0到e-1（e為圖G邊的數(shù)目）。了解----假設(shè)數(shù)組E存放圖G中的所有邊，且邊已按權(quán)值從小到大的順序排列。n為圖G的頂點個數(shù)，e為圖G的邊數(shù)?？唆斔箍査惴ㄈ缦拢?defineMAXE<最大邊數(shù)>#defineMAXV<最大頂點數(shù)>typedefstruct{intvex1;//邊的起始頂點intvex2;//邊的終止頂點intweight;//邊的權(quán)值}Edge;

當(dāng)前第84頁\共有141頁\編于星期五\0點84

Voidkruskal(EdgeE[],intn,inte){inti,j,m1,m2,sn1,sn2,k;intvset[MAXV];for(i=0;i<n;i++)//初始化輔助數(shù)組

vset[i]=i;k=1;//表示當(dāng)前構(gòu)造最小生成樹的第k條邊，初值為1

j=0;//E中邊的下標(biāo)，初值為0

while(k<e)//生成的邊數(shù)小于e時繼續(xù)循環(huán){ml=E[j].vex1;m2=E[j].vex2;//取一條邊的兩個鄰接點

sn1=vset[m1];sn2=vset[m2];//分別得到兩個頂點所屬的集合編號

if(sn1!=sn2)//兩頂點分屬于不同的集合，該邊是最小生成樹的一條邊當(dāng)前第85頁\共有141頁\編于星期五\0點85

{printf(“(m1，m2)：％d＼n”,E[j].weight);k++;//生成邊數(shù)增lfor(i=0;i<n;i++)//兩個集合統(tǒng)一編號

if(vset[i]=i)//集合編號為sn2的改為sn1vset[i]=sn1;}j++;//掃描下一條邊}}

如果給定帶權(quán)無向連通圖G有e條邊，且邊已經(jīng)按權(quán)值遞增的次序存放在數(shù)組E中，則用克魯斯卡爾算法構(gòu)造最小生成樹的時間復(fù)雜度為O(e)。克魯斯卡爾算法的時間復(fù)雜度與邊數(shù)e有關(guān)，該算法適合于求邊數(shù)較少的帶權(quán)無向連通圖的最小生成樹。

當(dāng)前第86頁\共有141頁\編于星期五\0點867.５有向無環(huán)圖及其應(yīng)用１、有向無環(huán)圖的定義有向無環(huán)圖是描述一項工程或系統(tǒng)的進行過程的有效工具。因為幾乎所有的工程均可以分為若干個稱為活動的子工程，而這些子工程之間，通常受著一定條件的約束，如其中某些子工程的開始必須在另一些子工程完成之后。因此對整個工程和系統(tǒng)而言，最為關(guān)心的兩個問題：

一是工程能否順利進行；

二是估算整個工程完成所必須的最短時間。對應(yīng)于有向圖，即是探討拓?fù)渑判蚝完P(guān)鍵路徑問題。當(dāng)前第87頁\共有141頁\編于星期五\0點87一個無環(huán)的有向圖稱作有向無環(huán)圖(DirectidAcyclineGragp)稱為DAG圖。有向無環(huán)圖是描述一項工程或系統(tǒng)的進行過程的有效工具當(dāng)前第88頁\共有141頁\編于星期五\0點88課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計和分析計算機原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C12學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)？？？頂點

——表示課程有向弧

——若課程i是課程j的先決條件，則圖中有弧<i,j>學(xué)生選修課程問題當(dāng)前第89頁\共有141頁\編于星期五\0點89AOV網(wǎng)——

用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)(ActivityOnVertexnetwork)，簡稱AOV網(wǎng)。拓?fù)渑判颉?/p>

把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程叫~檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點的拓?fù)溆行蛐蛄?，若網(wǎng)中所有頂點都在它的拓?fù)溆行蛐蛄兄?，則該AOV網(wǎng)必定不存在環(huán)。當(dāng)前第90頁\共有141頁\編于星期五\0點90在有向圖中選一個沒有前驅(qū)的頂點且輸出之從圖中刪除該頂點和所有以它為尾的弧拓?fù)渑判虻姆椒ㄖ貜?fù)上述兩步，直至全部頂點均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點為止當(dāng)前第91頁\共有141頁\編于星期五\0點91C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏漠?dāng)前第92頁\共有141頁\編于星期五\0點92C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1（1）當(dāng)前第93頁\共有141頁\編于星期五\0點93C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2（2）C9C3C4C5C6C7C8C10C11C12拓?fù)湫蛄校篊1--C2--C3（3）當(dāng)前第94頁\共有141頁\編于星期五\0點94C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4（4）C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5（5）當(dāng)前第95頁\共有141頁\編于星期五\0點95C6C8C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7（6）C11拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9C6C8C9C10C12C6C8C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11當(dāng)前第96頁\共有141頁\編于星期五\0點96C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6C8C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12C8拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8當(dāng)前第97頁\共有141頁\編于星期五\0點97算法實現(xiàn)重復(fù)上述操作直至?？諡橹埂Ｈ魲？諘r輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀Ｒ脏徑颖碜鞔鎯Y(jié)構(gòu)把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧。當(dāng)前第98頁\共有141頁\編于星期五\0點98在實現(xiàn)拓?fù)渑判虻乃惴ㄖ?，采用鄰接表作為有向圖的存儲結(jié)構(gòu)，每個頂點設(shè)置一個單鏈表，每個單鏈表有一個表頭結(jié)點，在表頭結(jié)點中增加一個存放頂點入度的域count，這些表頭結(jié)點構(gòu)成一個數(shù)組，表頭結(jié)點定義如下：typedefstruct//表頭結(jié)點{Vertexdata;//頂點信息

intcount;//存放頂點入度

ArcNode*firstarc;//指向第一條弧}Vnode;

在執(zhí)行拓?fù)渑判虻倪^程中，當(dāng)某個頂點的入度為零(沒有前驅(qū)頂點)時，就將此頂點輸出，同時將該頂點的所有后繼頂點的入度減1，相當(dāng)于刪除所有以該頂點為尾的弧。為了避免重復(fù)檢測頂點的入度是否為零，需要設(shè)立一個棧來存放入度為零的頂點。執(zhí)行拓?fù)渑判虻乃惴ㄈ缦拢寒?dāng)前第99頁\共有141頁\編于星期五\0點99

voidtopsort(VNodeadj[],intn){inti,j;intstack[MAXV],top=0;//棧stack的指針為topArcNode*p;for(i=0;i<n;i++)if(adj[i].count==0)//建入度為0的頂點棧{top++;stack[top]=i;}while(top>0)//棧不為空{(diào)i=stack[top];top--;//頂點vi出棧

printf(“％d”,i);//輸出vip=adj[i].firstarc;//指向以vi為弧尾的第一條弧

while(p!=NULL){j=p->adjvex;//以vi為弧尾的弧的另一頂點vj

當(dāng)前第100頁\共有141頁\編于星期五\0點100

while(p!=NULL){j=p->adjvex;//以vi為弧尾的弧的另一頂點vjadj[j].count--;//頂點vj的入度減1

if(adj[j].count==0)//入度為0的相鄰頂點入棧{top++;stack[top]=j;}p=p->nextarc;//指向以vi為弧尾的下一條弧}}}

可見，對于有n個頂點和e條邊的有向圖而言，for循環(huán)中建立入度為0的頂點棧時間為O（n）；若在拓?fù)渑判蜻^程中不出現(xiàn)有向環(huán)，則每個頂點出棧、入棧和入度減1的操作在while(top>0)循環(huán)語句中均執(zhí)行e次，因此拓?fù)渑判蚩偟臅r間花費為O(n+e)。

當(dāng)前第101頁\共有141頁\編于星期五\0點101例設(shè)一個工程有11項活動，9個事件事件V1——表示整個工程開始事件V9——表示整個工程結(jié)束987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)（ActivityOnEdge）邊表示活動用頂點表示事件，弧表示活動，權(quán)表示活動持續(xù)的時間；網(wǎng)中只有：唯一一個入度為0的點源點唯一一個出度為0的點匯點完成整項工程至少需要多少時間？哪些活動是影響工程進度的關(guān)鍵？7.5.2關(guān)鍵路徑當(dāng)前第102頁\共有141頁\編于星期五\0點102Ve(j)——表示事件Vj的最早發(fā)生時間Vl(j)——表示事件Vj的最遲發(fā)生時間ee(i)——表示活動ai的最早開始時間el(i)——表示活動ai的最遲開始時間

el(i)-ee(i)——表示完成活動ai的時間余量關(guān)鍵活動就是時間余量el(i)-ee(i)＝0的活動關(guān)鍵路徑

——

路徑長度最長的路徑叫~關(guān)鍵活動

——

關(guān)鍵路徑上的活動叫~987645321a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4AOE網(wǎng)常用于表示工程的計劃或進度。由于實際工程只有一個開始點和一個結(jié)束點，同時AOE網(wǎng)應(yīng)當(dāng)是無環(huán)的。

當(dāng)前第103頁\共有141頁\編于星期五\0點103如何找ee(i)=el(i)的關(guān)鍵活動？設(shè)活動ai用弧<j,k>表示，其持續(xù)時間記為：dut(<j,k>)則有：（1）ee(i)=Ve(j)

（2）el(i)=Vl(k)-dut(<j,k>)jkai如何求Ve(j)和Vl(j)？(1)從Ve(1)=0開始向前遞推(