《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》d

第7章圖編輯ppt第2

頁7.1圖的術(shù)語與定義圖的定義圖(Graph)——圖G是由兩個集合V(G)和E(G)組成的，記為G=(V,E)其中：V(G)是頂點的非空有限集

E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)?。圖的分類有向圖無向圖編輯ppt第3

頁7.1圖的術(shù)語與定義圖的定義有向圖——有向圖G是由兩個集合V(G)和E(G)組成的。

其中：

V(G)是頂點的非空有限集。

E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c的有序?qū)?，記?/p>

<v,w>，v、w是頂點，v為弧尾，w為弧頭。編輯ppt第4

頁7.1圖的術(shù)語與定義例如：G1=<V1,E1>V1={A,B,C,D,E}E1={<A,B>,<A,E>,<B,C>,<C,D>,<D,B>,

<D,A>,<E,C>}EACBD編輯ppt第5

頁7.1圖的術(shù)語與定義圖的定義無向圖——無向圖G是由兩個集合V(G)和E(G)組成的。 其中： V(G)是頂點的非空有限集。

E(G)是邊的有限集合，邊是頂點的無序?qū)?，記?/p>

(v,w)或

(w,v)，并且

(v,w)=(w,v)。編輯ppt第6

頁7.1圖的術(shù)語與定義例如：G2=<V2,E2>

V2={v0,v1,v2,v3,v4}

E2={(v0,v1),(v0,v3),(v1,v2),(v1,v4),

(v2,v3),(v2,v4)}V0V4V3V1V2編輯ppt網(wǎng)(Network)弧或邊帶權(quán)(Weight)的圖分別稱有向網(wǎng)和無向網(wǎng)ABCDE1341423906617.1圖的術(shù)語與定義編輯ppt第8

頁7.1圖的術(shù)語與定義圖的應(yīng)用舉例 例1.交通圖（公路、鐵路）

頂點：地點 邊：連接地點的路 例2.電路圖

頂點：元件 邊：連接元件之間的線路 例3.通訊線路圖

頂點：通訊站點

邊：站點間的連線 例4.各種流程圖 如產(chǎn)品的生產(chǎn)流程圖。

頂點：工序 邊：各道工序之間的順序關(guān)系編輯ppt第9

頁7.1圖的術(shù)語與定義圖的基本術(shù)語鄰接點及關(guān)聯(lián)邊 鄰接點：邊的兩個頂點互為鄰接點 關(guān)聯(lián)邊：若邊e=(v,u),則稱頂點v、u關(guān)連邊e。頂點V的度

=與V相關(guān)聯(lián)的邊的數(shù)目eV0V4V3V1V2編輯ppt第10

頁7.1圖的術(shù)語與定義頂點的度、入度、出度

在有向圖中：

頂點V的出度

=以V為起點的有向邊數(shù)

頂點V的入度

=以V為終點的有向邊數(shù)

頂點V的度

=V的出度+V的入度

ABCDE設(shè)圖G的頂點數(shù)為n，邊數(shù)為e

圖的所有頂點的度數(shù)和=2*e編輯ppt假設(shè)圖中有n個頂點，e條邊，則

含有e=n(n-1)/2條邊的無向圖稱作完全圖(Completedgraph)

含有e=n(n-1)

條弧的有向圖稱作有向完全圖

若邊或弧的個數(shù)e<nlogn，則稱作稀疏圖(Sparsegraph)，否則稱作稠密圖(Densegraph).BADEC7.1圖的術(shù)語與定義編輯ppt第12

頁7.1圖的術(shù)語與定義路徑、回路

假設(shè)v1,v2,…,vk為圖G=（V，E）的頂點序列，若G為無向圖，則有(vi,vi+1)E；或者G為有向圖，則有<vi,vi+1>E；其中(1≤i=1<k)，v=v1,u=vk，則稱該序列是從頂點v到頂點u的路徑；路徑上邊的數(shù)目稱作路徑長度。

若第一個頂點和最后一個頂點相同，則稱該序列為回路。

序列中頂點不重復(fù)出現(xiàn)的路徑定義為簡單路徑

構(gòu)成回路的簡單路徑稱其為簡單回路編輯ppt第13

頁7.1圖的術(shù)語與定義例如 在圖G1中，V0,V1,V2,V3是V0到V3的路徑，而且是簡單路徑；V0,V1,V2,V3,V0是簡單回路。無向圖G1有向圖G2V0V4V3V1V2V0V1V2V3 在圖G2中，V0,V2,V3是V0到V3的簡單路徑；V0,V2,V3,V0是簡單回路。編輯ppt第14

頁7.1圖的術(shù)語與定義連通圖 在無向圖G=<V,E>中，若對任何兩個頂點v、u都存在從v到u的路徑，則稱G是連通圖。

G2:非連通圖G1:連通圖V0V2V3V1V5V4V0V4V3V1V2編輯ppt第15

頁7.1圖的術(shù)語與定義子圖 設(shè)有兩個圖G=(V，E)，G1=(V1，E1)，若V1

V且E1

E，則稱G1是G的子圖。例(a)(b)(c)V0V4V3V1V2V0V4V3V1V2V0V4V3V1V2

(b)、(c)

是(a)

的子圖編輯ppt第16

頁7.1圖的術(shù)語與定義若無向圖為非連通圖，則各個極大連通子圖稱作此圖的連通分量。

極大連通子圖含義：該子圖是G的連通子圖，將G的任何不在該子圖中的頂點加入，子圖不再連通。連通分量非連通圖V0V2V3V1V5V4編輯ppt第17

頁7.1圖的術(shù)語與定義強連通圖

在有向圖G=<V,E>中，若對任何兩個頂點v、u都存在從v到u的路徑，則稱G是強連通圖。強連通圖非強連通圖V0V1V2V3V0V1V2V3編輯ppt第18

頁7.1圖的術(shù)語與定義若有向圖為非強連通圖，它的各個極大強連通子圖稱為它的強連通分量。

極大強連通子圖含義：該子圖是D的強連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強連通的。強連通分量

V0

V2

V3

V1V0V1V2V3編輯ppt第19

頁7.1圖的術(shù)語與定義生成樹

連通圖G中，包含所有頂點的極小連通子圖稱為G的生成樹。

極小連通子圖含義：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。

若T是G的生成樹當(dāng)且僅當(dāng)T滿足如下條件： T包含G的所有頂點 T是G的連通子圖

T中無回路連通圖G1G1的生成樹V0V4V3V1V2V0V4V3V1V2編輯ppt207.1圖的基本操作1、結(jié)構(gòu)的建立和銷毀2、對頂點的訪問操作3、對鄰接點的操作4、插入或刪除頂點5、插入和刪除弧6、遍歷編輯ppt217.1圖的基本操作結(jié)構(gòu)的建立和銷毀CreatGraph(&G,V,VR):按定義(V,VR)構(gòu)造圖DestroyGraph(&G):銷毀圖對頂點的訪問操作LocateVex(G,u);若G中存在頂點u，則返回該頂點在圖中“位置”；否則返回其它信息GetVex(G,v);返回v的值PutVex(&G,v,value);對v賦值value

編輯ppt227.1圖的基本操作對鄰接點的操作FirstAdjVex(G,v);返回v的“第一個鄰接點”。若該頂點在G中沒有鄰接點，則返回“空”NextAdjVex(G,v,w);返回v的（相對于w的）“下一個鄰接點”。若w是v的最后一個鄰接點，則返回“空”。插入或刪除頂點InsertVex(&G,v);在圖G中增添新頂點vDeleteVex(&G,v);刪除G中頂點v及其相關(guān)的弧

編輯ppt237.1圖的基本操作插入和刪除弧DeleteVex(&G,v);刪除G中頂點v及其相關(guān)的弧DeleteArc(&G,v,w);在G中刪除弧<v,w>若G是無向的，則還刪除對稱弧<w,v>遍歷DFSTraverse(G,v,Visit());從頂點v起深度優(yōu)先遍歷圖G并對每個頂點調(diào)用函數(shù)Visit一次且僅一次BFSTraverse(G,v,Visit());從頂點v起廣度優(yōu)先遍歷圖G，并對每個頂點調(diào)用函數(shù)Visit一次且僅一次編輯ppt247.2圖的存儲表示

1、圖的數(shù)組(鄰接矩陣)存儲表示2、圖的鄰接表存儲表示3、有向圖的十字鏈表存儲表示4、無向圖的鄰接多重表存儲表示編輯ppt第25

頁7.2圖的存儲結(jié)構(gòu)一、數(shù)組表示法（鄰接矩陣表示）

鄰接矩陣：G的鄰接矩陣是滿足如下條件的n階矩陣：A[i][j]=1若(vi,vj)E或<vi,vj>E0否則01010010101011010001100在數(shù)組表示法中，用鄰接矩陣表示頂點間的關(guān)系011000000001000V1V2V3V4V1V5V4V2V3vi的度？第i

行(列)1的個數(shù)。vi的出度?第i

行1的個數(shù)第i列1的個數(shù)。vi

的入度？編輯ppt第26

頁7.2圖的存儲結(jié)構(gòu)二、鄰接表

鄰接表是圖的鏈式存儲結(jié)構(gòu) 1、無向圖的鄰接表

頂點：通常按編號順序?qū)㈨旤c數(shù)據(jù)存儲在一維數(shù)組中；

邊節(jié)點：對于每個頂點，用線性邊節(jié)點鏈表存儲關(guān)聯(lián)鄰接點編號。

01234m-1V1V2V3V4V513V1V5V4V2V30241340212鄰接點的位置共有多少邊節(jié)點？2*e編輯ppt第27

頁7.2圖的存儲結(jié)構(gòu)typedefstructArcNode//邊結(jié)點定義 {intadjvex;//鄰接點域，//存放與Vi鄰接的點在表頭數(shù)組中的位置

structArcNode*next;//鏈域，下一條邊或弧

}

ArcNode;adjvexnextvexdatafirstarctypedefstructtnode//頂點結(jié)點定義 {intvexdata;//存放頂點信息

ArcNode*firstarc;//指向第一個邊或弧

}

VNode,AdjList[MAX_VERTEX_NUM];typedefstruct//圖的定義 { AdjListvertices; int vexnum,arcnum;//頂點數(shù)和弧數(shù) int kind;//圖的種類 }編輯ppt第28

頁7.2圖的存儲結(jié)構(gòu)無向圖的鄰接表的特點

1）頂點v的度：等于v對應(yīng)線性鏈表的長度；

2）判定兩頂點v，u是否鄰接：要看v對應(yīng)線性鏈表中是否存在u。

3）在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點；

4）設(shè)存儲頂點的一維數(shù)組大小為m（m圖的頂點數(shù)n），圖的邊數(shù)為

e，G占用存儲空間為：m個點+2*e個表節(jié)點。G占用存儲空間與G的頂點數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖。編輯ppt第29

頁7.2圖的存儲結(jié)構(gòu)二、鄰接表 2、有向圖的鄰接表 頂點：用一維數(shù)組存儲（按編號順序） 以同一頂點為起點的?。河镁€性出邊節(jié)點鏈表存儲弧頭位置1234v1v3v4v2vexdatafirstarc

3

2

4

1^^^^adjvexnextV1V2V3V4弧頭的位置頂點i

的出度?頂點i的出邊表長度共有多少邊節(jié)點？e出邊表編輯ppt第30

頁7.2圖的存儲結(jié)構(gòu)二、鄰接表 3、有向圖的逆鄰接表 頂點：用一維數(shù)組存儲（按編號順序） 以同一頂點為終點的弧：用記錄弧尾位置的線性入邊節(jié)點鏈表存儲。1234v1v3v4v2vexdatafirstarc

4

1

1

3^^^^V1V2V3V4弧尾的位置頂點i

的入度?頂點i的入邊表長度共有多少邊節(jié)點？e入邊表編輯ppt第31

頁7.2圖的存儲結(jié)構(gòu)三、有向圖的十字鏈表表示法弧結(jié)點：typedefstructArcBox{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置

structarcnode*hlink；//指向弧頭相同的下一條弧

structarcnode*tlink;//指向弧尾相同的下一條弧}ArcBox;tailvexheadvexhlinktlink頂點結(jié)點：typedefstructVexNode{VertexTypedata;//存與頂點有關(guān)信息

ArcBox*firstin；//指向以該頂點為弧頭的第1個弧結(jié)點

ArcBox*firstout;//指向以該頂點為弧尾的第1個弧結(jié)點}VexNode;VexNodeOLGraph[M];datafirstinfirstout編輯ppt第32

頁7.2圖的存儲結(jié)構(gòu)三、有向圖的十字鏈表表示法例bdacabcd123413123431434241^^^^^^^^相同弧尾相同弧頭編輯ppt第33

頁7.2圖的存儲結(jié)構(gòu)四、無向圖的鄰接多重表表示法頂點結(jié)點：typedefstructVexBox{VertexTypedata;//存與頂點有關(guān)的信息

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

VexBox;VexBoxAMLGraph[M];datafirstedge邊結(jié)點：typedefstructnode{VisitIfmark;//標志域，記錄是否已經(jīng)搜索過

intivex,jvex;//該邊依附的兩個頂點在表頭數(shù)組中位置

structEBox*ilink,*jlink;//分別指向依附于ivex和jvex的下一條邊}

EBox;markivexilinkjvexjlink編輯ppt第34

頁7.2圖的存儲結(jié)構(gòu)四、無向圖的鄰接多重表表示法例aecbd1234acdb5e

12

14

34

3235

52^^^^^編輯ppt第35

頁7.3圖的遍歷圖的遍歷

訪遍圖中所有的頂點，并且使圖中的每個頂點僅被訪問一次。遍歷實質(zhì)

遍歷所有連通分量，

對于連通子圖：根據(jù)鄰接關(guān)系遍歷所有頂點。

設(shè)置數(shù)組visited[0,…n]區(qū)分未訪問的子圖信息搜索路徑深度優(yōu)先遍歷（DFS）廣度優(yōu)先遍歷（BFS）編輯ppt第36

頁7.3圖的遍歷圖的深度遍歷（DFS）

深度優(yōu)先遍歷連通圖的過程類似于樹的先根遍歷，從圖中某個頂點V出發(fā)，訪問此頂點，然后依次從V的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V有路徑相通的頂點都被訪問到Vw1SG1SG2w2w3w2…V編輯ppt第37

頁7.3圖的遍歷圖的深度遍歷（DFS）例：achdekfachdkfeachkfed訪問次序bg編輯ppt第38

頁7.3圖的遍歷圖的深度遍歷（DFS）例：bgabchdekfachdkfeachkfedbg訪問次序bg編輯ppt第39

頁7.3圖的遍歷圖的深度遍歷（DFS）V1V2V4V5V3V7V6V8例1深度遍歷1：V1V2V4V8V5V6V3V7由于沒有規(guī)定訪問鄰接點的順序，所以深度優(yōu)先序列不惟一。深度遍歷2：V1V3V7V8V6V5V2V4編輯ppt第40

頁7.3圖的遍歷圖的深度遍歷（DFS）——算法7.4和7.5開始標志數(shù)組初始化V=0V訪問過?DFS(g,v)V=V+1V<VexNum結(jié)束NYYNDFS開始訪問V,置標志求V鄰接點有鄰接點w求下一鄰接點W訪問過結(jié)束NYNYDFS(G,w)編輯ppt第41

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法voidDFSTrav(GraphG,Void(*Visit)(VertexTypee)){

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;for(v=0;v<G.vexnum;++v)if(!visited[v])DFS(G,v,Visit);}//DFSTrav訪問標志數(shù)組：intvisited[]

全局變量，初始時所有分量全為FALSE編輯ppt第42

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法voidDFS(GraphG,intv,void(*Visit)(VertexTypee)){

/*從v出發(fā)（v是頂點位置），深度優(yōu)先遍歷v所在的連通分量*/visited[v]=TRUE;

Visit(v);//先根遍歷for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w,Visit(w));}//DFS編輯ppt第43

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法V1V2V4V5V3V7V6V8例深度遍歷：V112341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6

4

1^

5

1

2

8

2^678678

7

3

6

3

5

4^^^V3V7V6V2V5V8V4編輯ppt第44

頁7.3圖的遍歷圖的深度遍歷（DFS）——遞歸算法V1V2V4V5V3V7V6V8例12341342vexdatafirstarc

2

7

8

3^^^adjvexnext55

6^

4

8

2^678678

7^^^深度遍歷：V1V3V7V6V2V4V8V5編輯ppt第45

頁7.3圖的遍歷深度優(yōu)先遍歷的時間復(fù)雜度 DFS對每一條邊處理一次（無向圖的每條邊從兩個方向處理），每個頂點訪問一次。鄰接表表示總代價為：O(點數(shù)n+邊數(shù)e)鄰接矩陣表示查詢單個頂點的所有鄰接點信息，需要O(n)的時間，所以總代價為O(n2)。編輯ppt第46

頁7.3圖的遍歷圖的廣度遍歷（BFS） 從圖中某頂點v出發(fā)： 1)訪問頂點v； 2)訪問v所有未被訪問的鄰接點w1,w2,…wk； 3)依次從這些鄰接點出發(fā)，訪問其所有未被訪問的鄰接點。依此類推，直至圖中所有和V0有路徑相通的頂點都被訪問到。編輯ppt第47

頁7.3圖的遍歷圖的廣度遍歷（BFS）例：abchdekfgacdefhkachkfed訪問次序編輯ppt第48

頁7.3圖的遍歷圖的廣度遍歷（BFS）——遞歸算法開始標志數(shù)組初始化V=0V訪問過BFSV=V+1V<Vexnum結(jié)束NYYN編輯ppt第49

頁7.3圖的遍歷圖的廣度遍歷（BFS）——遞歸算法voidBFSTraverse(GraphG,void(*Visit)(VertexType)){//本算法對圖G進行廣度優(yōu)先遍歷

for(v=0;v<G.vexnum;++v)visited[v]=FALSE;//訪問標志數(shù)組初始化

for(v=0;v<G.vexnum;++v)if(!visited[v])BFS(G,v,Visit);}//BFSTraverse編輯ppt第50

頁7.3圖的遍歷圖的廣度遍歷（BFS）——算法7.6開始訪問V0,置標志求V鄰接點ww存在嗎V下一鄰接點ww訪問過結(jié)束NYNYBFS初始化隊列V0入隊隊列空嗎隊頭V出隊訪問w,置標志w入隊NY編輯ppt第51

頁7.3圖的遍歷voidBFS(GraphG,intv,void(*Visit)(VertexTypee)){//從第v個頂點出發(fā)

InitQueue(Q);//建立輔助空隊列Q

Visit(v);visited[v]=TRUE;

//訪問u，訪問標志數(shù)組EnQueue(Q,v);//v入隊

while(!QueueEmpty(Q)){DeQueue(Q,u);//隊頭元素出隊，并賦值給ufor(w=FirstAdjVex(G,u);w;w=NextAdjVex(G,u,w))if(!visited[w]){Visit(w);visited[w]=TRUE;

//訪問uEnQueue(Q,w);}}//while}//BFS編輯ppt第52

頁7.3圖的遍歷圖的廣度遍歷（BFS）例1423512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

20123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143編輯ppt第53

頁7.3圖的遍歷圖的廣度遍歷（BFS）例14235012345432fr遍歷序列：1432012345

32fr遍歷序列：1432012345

325fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2編輯ppt第54

頁7.3圖的遍歷圖的廣度遍歷（BFS）/p>

25fr遍歷序列/p>

5fr遍歷序列/p>

fr遍歷序列：1432512341342vexdatafirstarc

5

5

4

3^^^adjvexnext55

1^

5

1

1

4

3^

2

2編輯ppt第55

頁7.3圖的遍歷遍歷的應(yīng)用 求兩個頂點之間的最短路徑長度

廣度優(yōu)先搜索訪問頂點的次序是按“路徑長度”漸增的次序。求路徑長度最短的路徑可以基于廣度優(yōu)先搜索遍歷進行。abchdekfg編輯ppt第56

頁7.4圖的最小生成樹生成樹

包含無向圖G所有頂點的極小連通子圖稱為G生成樹，它只有n-1條邊，可以構(gòu)成一棵樹。

極小連通子圖含義：該子圖是G的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。

生成樹T的特點：

T是G的連通子圖

T包含G的所有頂點 T中有n-1條邊T中無回路

連通圖G1G1的生成樹V0V4V3V1V2V0V4V3V1V2編輯ppt第57

頁7.4圖的最小生成樹問題提出

假設(shè)要在n個城市之間建立通訊聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要修建n-1條線路，如何在最節(jié)省經(jīng)費的前提下建立這個通訊網(wǎng)？問題分析和數(shù)學(xué)建模：

頂點——表示城市

權(quán)——城市間建立通信線路所需花費代價

希望找到一棵生成樹，它的每條邊上的權(quán)值之和（即建立該通信網(wǎng)所需花費的總代價）最小——最小代價生成樹MST(MinimumcostSpanningTree)

編輯ppt7.4圖的最小生成樹最小生成樹(Leastweightedspanningtree)：權(quán)（之和）最小的生成樹。V3V1V4V6V5V23652165546V3V1V4V6V5V22415V3V1V4V6V5V2編輯ppt第59

頁7.4圖的最小生成樹最小生成樹的MST性質(zhì) 若U集是V的一個非空子集，若在所有聯(lián)接U和V-U的邊中，(u,v)權(quán)值最小，其中uU，vV-U；則：必有一棵最小生成樹包含(u,v)。典型算法普里姆(Prim)算法將頂點歸并，與邊數(shù)無關(guān)，適于稠密網(wǎng)?？唆斔箍?Kruskal)算法將邊歸并，適于求稀疏網(wǎng)的最小生成樹。編輯ppt60基本思想：從初始點u0開始將u0作為當(dāng)前的最小生成樹：T向T中增加一個節(jié)點：從與T的節(jié)點相連的所有邊中（不包含兩個頂點都在T內(nèi)的邊），找到最短的邊，將該邊及相應(yīng)節(jié)點加入T中直到所有的節(jié)點都加入T中為止7.4圖的最小生成樹編輯ppt第61

頁7.4圖的最小生成樹普里姆算法（Prim）

設(shè)G=(V,GE)為一個具有n個頂點的連通網(wǎng)絡(luò)，T=(U,TE)為生成樹。

(1)初始時，U={u0}，TE=；

(2)在所有uU且vV-U的邊(u,v)中選擇一條權(quán)值最小的邊，不妨設(shè)為(u,v)；

(3)(u,v)加入TE，同時將v加入U；

(4)重復(fù)(2)(3)，直到U=V為止；編輯ppt第62

頁7.4圖的最小生成樹普魯姆算法（Prim）——教材P175V3V1V4V6V5V23652165546V3V1V4V6V5V212V3V1V4V6V5V214V3V1V4V6V5V2142V3V1V4V6V5V21452V3V1V4V6V5V21453U={V1}U={V1,V3}U={V1,V3,V6}U={V1,V3,V6,V4}U={V1,V3,V6,V4,V2}U={V1,V3,V6,V4,V2,V5}編輯ppt第63

頁7.4圖的最小生成樹輔助數(shù)組closedge[]對不在生成樹中的每個頂點，記錄其和生成樹頂點相關(guān)聯(lián)且代價最小的邊：struct{VertexTypeAdjvex;//相關(guān)頂點VRTypelowcost;//最小邊的權(quán)值}closedge[MAX_VERTEX_NUM];

closedge.Adjvex[v]：

頂點v到子集U中權(quán)最小邊(v,u)相關(guān)聯(lián)的頂點u

closedge.lowcost[v]：

頂點v到子集U權(quán)最小邊

(v,u)的權(quán)值(距離)編輯ppt第64

頁7.4圖的最小生成樹

V1V1V1

V10

6

1

5

maxmax

0(V1)

1(V2)

2(V3)3(V4)4(V5)5(V6)

closedge.Adjvexclosedge.Lowcost

3652165546V6V5V4V3V2V1

V1V3V1

V1V3V3

0

5

0

5

64

0(V1)

1(V2)

2(V3)3(V4)4(V5)5(V6)

closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V2V1編輯ppt第65

頁7.4圖的最小生成樹

V3V1V1V3V30

5

0

564

0(V1)

1(V2)

2(V3)3(V4)4(V5)

5(V6)

closedge.Adjvexclosedge.Lowcost

0(V1)

1(V2)

2(V3)3(V4)4(V5)

5(V6)

V3V1V6V3V30

5

0

260closedge.Adjvexclosedge.Lowcost

3652165546V6V5V4V3V26V5V4V3V2V1編輯ppt第66

頁7.4圖的最小生成樹

V3V1

V6V3V30

5

00

6

0

0(V1)

1(V2)

2(V3)

3(V4)4(V5)

5(V6)

closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V2V1

V3

V1

V6

V3V30

5

0

0

6

0

0(V1)

1(V2)

2(V3)

3(V4)4(V5)

5(V6)closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V2V1編輯ppt第67

頁7.4圖的最小生成樹

V3V1V6

V3

V30000

3

0

0(V1)1(V2)2(V3)3(V4)

4(V5)

5(V6)

closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V26V5V4V3V2V1

V3

V1

V6

V3V30

5

0

0

6

0

0(V1)

1(V2)

2(V3)

3(V4)4(V5)

5(V6)closedge.Adjvexclosedge.Lowcost編輯ppt第68

頁7.4圖的最小生成樹

V3V1V6V3V3000000

0(V1)1(V2)2(V3)3(V4)4(V5)5(V6)closedge.Adjvexclosedge.Lowcost3652165546V6V5V4V3V26V5V4V3V2V1編輯ppt第69

頁7.4圖的最小生成樹voidMiniSpanTree_P(MGraphG,VertexTypeu){//用普里姆算法從頂點u出發(fā)構(gòu)造網(wǎng)G的最小生成樹

k=LocateVex(G,u);for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化

if(j!=k)closedge[j]={u,G.arcs[k][j]};closedge[k].Lowcost=0;//初始，U＝{u}for(i=1;i<G.vexnum;++i){}繼續(xù)向生成樹上添加頂點;編輯ppt第70

頁7.4圖的最小生成樹

k=minimum(closedge);

//求出加入生成樹的下一個頂點(k)printf(closedge[k].Adjvex,G.vexs[k]);

//輸出生成樹上一條邊

closedge[k].Lowcost=0;//第k頂點并入U集

for(j=0;j<G.vexnum;++j)//修改其它頂點到生成樹的最小邊

if(G.arcs[k][j]<closedge[j].Lowcost)closedge[j]={G.vexs[k],G.arcs[k][j]};

編輯ppt第71

頁7.4圖的最小生成樹普里姆算法的性能 設(shè)n是圖的頂點數(shù)，普魯姆算法的時間復(fù)雜度為O(n2)。 與邊數(shù)無關(guān)，適用于求邊稠密的網(wǎng)的最小生成樹。編輯ppt第72

頁7.4圖的最小生成樹克魯斯卡爾(Kruskal)算法 設(shè)連通網(wǎng)N=(V,{E})。

1)初始時最小生成樹只包含圖的n個頂點，每個頂點為一棵子樹； 2)選取權(quán)值較小且所關(guān)聯(lián)的兩個頂點不在同一子樹的邊，將此邊加入到最小生成樹中；

3)重復(fù)2）n-1次，即得到包含n個頂點和n-1條邊的最小生成樹。編輯ppt第73

頁7.4圖的最小生成樹克魯斯卡爾(Kruskal)算法566154V3V1V4V6V5V2365216543212345編輯ppt7.4克魯斯卡爾算法構(gòu)造非連通圖ST=(V,{});

k=i=0;//k計選中的邊數(shù)

while(k<n-1){

++i;

檢查邊集E中第i條權(quán)值最小的邊(u,v);

若(u,v)加入ST后不使ST中產(chǎn)生回路，

則輸出邊(u,v);且k++;}編輯ppt123456第75

頁7.4圖的最小生成樹克魯斯卡爾(Kruskal)算法16543212345datajihe124536124536vexhweight112213233544vextflag61535500000001342567893345566664260000111114211122222采用邊集數(shù)組的形式保存圖：566154V3V1V4V6V5V23652編輯ppt第76

頁7.4圖的最小生成樹克魯斯卡爾的性能 設(shè)圖的邊數(shù)是e，克魯斯卡爾算法的時間復(fù)雜度為O(eloge)。

適用于求邊稀疏的網(wǎng)的最小生成樹。編輯ppt第77

頁7.4圖的最小生成樹兩種算法比較普里姆算法克魯斯卡爾算法時間復(fù)雜度O(n2)O(eloge)稠密圖稀疏圖算法名適應(yīng)范圍編輯ppt7.5重連通圖和關(guān)節(jié)點定義：若從一個連通圖中刪去一個頂點及其相關(guān)聯(lián)的邊，連通圖成為兩個或多個連通分量，則該點稱為關(guān)節(jié)點。定義：若從一個連通圖中刪去任意一個頂點及其相關(guān)聯(lián)的邊，它仍為一個連通圖的話，則該連通圖被稱為重（雙）連通圖。ahgcbfde雙連通圖中沒有關(guān)節(jié)點沒有關(guān)節(jié)點的連通圖為雙連通圖編輯ppt7.5重連通圖和關(guān)節(jié)點abcdefgh對G進行深度優(yōu)先遍歷，得到深度優(yōu)先生成樹T虛線表示回邊：即在G中但不在T中的邊,是遍歷時選擇

已訪問的鄰接點ahgcbfde編輯ppt關(guān)節(jié)點的特征特征1：若生成樹的根結(jié)點，有兩個或兩個以上的分支，則此頂點(生成樹的根)必為關(guān)節(jié)點；ahgcbfdeabcdefgh編輯ppt特征2：對生成樹上的任意一個“頂點”，若某棵子樹的根或子樹中的其它“頂點”沒有和其祖先相通的回邊，則該“頂點”必為關(guān)節(jié)點。如何判斷節(jié)點滿足特征2？ahgcbfde關(guān)節(jié)點的特征abcdefgh編輯pptabcdefgh23456783311111設(shè)置visited[v]:頂點在DFS中的序號；設(shè)置low[v]:頂點v在DFS中所能訪問到的的節(jié)點最小序號(包括回邊)1low[v]＝Min{visited[v],low[w],visited[k]}w是頂點v在DFS樹上的子節(jié)點；k是頂點v在DFS樹上回聯(lián)的祖先節(jié)點；如何判斷節(jié)點滿足特征2？ahgcbfde編輯ppt如何判斷節(jié)點滿足特征2？條件：1)頂點v存在孩子節(jié)點w;2)visited[v]<=low[w];ahgcbfdeabcdefgh234567833111111編輯ppt第84

頁7.5有向無環(huán)圖——拓撲排序有向無環(huán)圖(DAG) 沒有回路的有向圖。含有公共子式的表達式

(a+b)*(e/f)-(a+b)-a+b*/efa+b-a+b*/ef編輯ppt第85

頁7.5有向無環(huán)圖——拓撲排序問題提出：學(xué)生選修課程問題 頂點——表示課程 有向弧——表示先決條件，若課程i

是

課程j

的先決條件，則圖中有弧<i,j>。

學(xué)生應(yīng)按怎樣的順序?qū)W習(xí)這些課程，才能無矛盾、順利地完成學(xué)業(yè)——拓撲排序。

很顯然，不能出現(xiàn)回路。編輯ppt第86

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12課程代號課程名稱先修課C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1,C2C4匯編語言C1C5語言的設(shè)計和分析C3,C4C6計算機原理C11C7編譯原理C3.C5C8操作系統(tǒng)C3,C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C1,C9,C10編輯ppt第87

頁7.5有向無環(huán)圖——拓撲排序有向無環(huán)圖(DAG)某工程可分為7個子工程，工程流程圖。V4V3V2V6V5V1V7編輯ppt第88

頁7.5有向無環(huán)圖——拓撲排序定義

AOV網(wǎng)——用頂點表示活動，用弧表示活動間優(yōu)先關(guān)系的有向圖稱為頂點表示活動的網(wǎng)（ActivityOnVertexnetwork），簡稱AOV網(wǎng)。

若

<vi,vj>是圖中有向邊，則

vi

是

vj

的直接前驅(qū)；vj

是

vi

的直接后繼。 AOV網(wǎng)中不允許有回路，因為回路意味著某項活動以自己為先決條件。編輯ppt第89

頁7.5有向無環(huán)圖——拓撲排序拓撲排序

把AOV網(wǎng)絡(luò)中各頂點按照它們相互之間的優(yōu)先關(guān)系排列成一個線性序列的過程。

檢測AOV網(wǎng)中是否存在環(huán)方法：對有向圖構(gòu)造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都在它的拓撲有序序列中，則該AOV網(wǎng)必定不存在環(huán)。編輯ppt第90

頁7.5有向無環(huán)圖——拓撲排序拓撲排序的方法

在有向圖中選一個沒有前驅(qū)的頂點且輸出之。

從圖中刪除該頂點和所有以它為尾的弧。

重復(fù)上述兩步，直至全部頂點均已輸出；或者當(dāng)圖中不存在無前驅(qū)的頂點為止。編輯ppt第91

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--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)的拓撲序列不是唯一的編輯ppt第92

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1編輯ppt第93

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1編輯ppt第94

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2編輯ppt第95

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2編輯ppt第96

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3編輯ppt第97

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3編輯ppt第98

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4編輯ppt第99

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4編輯ppt第100

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5編輯ppt第101

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5編輯ppt第102

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7編輯ppt第103

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7編輯ppt第104

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C6C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9編輯ppt第105

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C6C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9編輯ppt第106

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C6C8C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10編輯ppt第107

頁7.5有向無環(huán)圖——拓撲排序拓撲排序C6C8C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8編輯ppt第108

頁7.5有向無環(huán)圖——拓撲排序拓撲排序算法實現(xiàn) 以鄰接表作存儲結(jié)構(gòu)。 把鄰接表中所有入度為0的頂點進棧。 棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼

Vk，把

Vk的入度

減1；若

Vk的入度為

0

則進棧。

重復(fù)上述操作直至?？諡橹?。

若?？諘r輸出的頂點個數(shù)不是

n，則有向圖有環(huán)；否則，拓撲排序完畢。 （實現(xiàn)過程見教材P182）編輯ppt第109

頁7.5有向無環(huán)圖——拓撲排序拓撲排序32104例1234560122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^top16toptop編輯ppt第110

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416toptopp2編輯ppt第111

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416topp21編輯ppt第112

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0122inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416P=NULL21top1編輯ppt第113

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210416P20top1編輯ppt第114

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210446P20top1編輯ppt第115

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210446P20top10編輯ppt第116

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210443P20top10編輯ppt第117

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext3^

2

5^

2

40123456^輸出序列：63210443P20top101P=NULL編輯ppt第118

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0112inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210443P10top1013編輯ppt第119

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210443P10top1003編輯ppt第120

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：63210442P10top1003P=NULL編輯ppt第121

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext2^

2

5^

2

40123456^輸出序列：6321044210top1003P=NULL2編輯ppt第122

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104400top1003P24編輯ppt第123

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104500top1003P24編輯ppt第124

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：632104500top1003P=NULL24編輯ppt第125

頁7.5有向無環(huán)圖——拓撲排序拓撲排序0111inlink

5

5

4

3^^^vexnext1^

2

5^

2

40123456^輸出序列：63210400top1003P=NULL245編輯ppt第126

頁7.5有向無環(huán)圖——關(guān)鍵路徑問題提出： 1）工程能否順序進行，即工程流程是否“合理”

2）完成整項工程至少需要多少時間，哪些子工程是影響工程進度的關(guān)鍵子工程？V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1頂點表示事件邊表示活動事件Vj發(fā)生表示

ak已結(jié)束ak

VjVi事件Vi發(fā)生表示

ak可以開始

AOE網(wǎng)編輯ppt第127

頁7.5有向無環(huán)圖——關(guān)鍵路徑AOE網(wǎng)

AOE——用邊表示活動的網(wǎng)。它是有一個帶權(quán)的有向無環(huán)圖。 頂點——表示事件，弧——表示活動， 權(quán)值——活動持續(xù)的時間。

路徑長度——路徑上各活動持續(xù)時間之和

關(guān)鍵路徑——路徑長度最長的路徑叫關(guān)鍵路徑編輯ppt第128

頁7.5有向無環(huán)圖——關(guān)鍵路徑AOV網(wǎng)和AOE網(wǎng)的區(qū)別 都能用來表示工程中的各子工程的流程： 一個用頂點表示活動， 一個用邊表示活動， 但AOV網(wǎng)側(cè)重表示活動的前后次序，AOE網(wǎng)除表示活動先后次序，還表示了活動的持續(xù)時間等。 因此可利用AOE網(wǎng)解決工程所需最短時間及哪些子工程拖延會影響整個工程按時完成等問題。編輯pptabcdefghk64521182446147“關(guān)鍵活動”指的是：該弧上的權(quán)值增加將使有向圖上的最長路徑的長度增加。整個工程完成的時間為：從有向圖的源點到匯點的最長路徑。源點匯點77.5有向無環(huán)圖——關(guān)鍵路徑編輯ppt如何求關(guān)鍵活動？“活動(弧)”的最早開始時間e(i)“活動(弧)”的最遲開始時間l(i)關(guān)鍵活動：e(i)＝l(i)“事件(頂點)”的最早發(fā)生時間ve(j)“事件(頂點)”的最遲發(fā)生時間vl(k)活動(弧)發(fā)生時間的計算公式假設(shè)第i條弧為<j,k>，則對第i項活動言e(i)=ve(j)；l(i)=vl(k)–dut(<j,k>)；jkiabce641161編輯ppt事件(頂點)發(fā)生時間的計算公式最早開始時間：ve(源點)=0；ve(k)=Max{ve(j)+dut(<j,k>)}最遲開始時間：vl(匯點)=ve(匯點)；vl(j)=Min{vl(k)–dut(<j,k>)}如何求關(guān)鍵活動？abce641161jki編輯ppt13200000000064571157151418181818181818181818161486610807拓撲有序序列:a-d-f-c-b-e-h-g-k如何求關(guān)鍵活動？abcdefghk64521182447編輯ppt1330645771514181814161078660000645777151414160236688710e(i)=ve(j)；l(i)=vl(k)–dut(<j,k>)；編輯ppt134算法的