《數(shù)據(jù)結(jié)構(gòu)與算法》第七章圖.ppt

1、第七章 圖,7.1 圖的定義 7.2 圖的存儲(chǔ)結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性問(wèn)題 7.5 有向無(wú)環(huán)圖及其應(yīng)用 7.6 最短路徑,71圖的定義,一、有向圖和無(wú)向圖 頂點(diǎn)Vertex V:頂點(diǎn)的有窮非空集合 VR兩個(gè)頂點(diǎn)之間的關(guān)系的集合 若VR 則表示從v到w有一條弧Arc v稱作弧尾或初始點(diǎn)，Tail w稱作弧頭或終端點(diǎn), Head,有向圖,無(wú)向圖,稀疏圖 稠密圖 網(wǎng)Network,子圖,鄰接點(diǎn) 相關(guān)聯(lián) 頂點(diǎn)的度、入度、 出度,圖中邊/弧的數(shù)目與頂點(diǎn)度的關(guān)系,路徑,路徑的長(zhǎng)度,連通圖,回路或環(huán)Cycle 簡(jiǎn)單路徑 簡(jiǎn)單回路,強(qiáng)連通圖,完全圖,有向完全圖,由頂點(diǎn)的集合和弧的集合構(gòu)成的圖

2、稱為有向圖,G1=(V1,A1) V1=v1,v2,v3,v4 A1=,若VR必有VR 則用無(wú)序?qū)?v,w)代替和稱作邊Edge 由頂點(diǎn)的集合和邊的集合構(gòu)成的圖稱作無(wú)向圖,G2=(V2,E2) V2=v1,v2,v3,v4,v5 E2=(v1,v2),(v1,v4),(v2,v3),(v2,v5),(v3,v4),(v3,v5),二、完全圖 Completed Graph 完全圖 有n*（n-1）/2條邊的無(wú)向圖 有向完全圖 有n*（n-1）條弧的有向圖 稀疏圖 有很少條邊或弧的圖 稠密圖 網(wǎng)Network 帶權(quán)的圖,三、子圖Subgraph 若有兩個(gè)圖G =（V，E）,G1=（V1，E1）

3、如果V1 V , E1 E,則稱G1為G的子圖,子圖,四、度 1.無(wú)向圖G =（V，E） 若邊（v，v1）E，則稱頂點(diǎn)v和v1互為鄰接點(diǎn) 邊（v，v1）依附于頂點(diǎn)v和v1 或邊（v，v1）與頂點(diǎn)v、v1相關(guān)聯(lián) 頂點(diǎn)v的度是和v相關(guān)聯(lián)的邊的數(shù)目,記作TD（v） 2.有向圖G =（V，A） 弧v，v1A， 則稱v鄰接到v1 或v1鄰接自v 弧v，v1和頂點(diǎn)v、v1相關(guān)聯(lián) 以頂點(diǎn)v為頭的弧的條數(shù)稱作v的入度,記作ID（v） 以頂點(diǎn)v為尾的弧的條數(shù)稱作v的出度,記作OD（v） 頂點(diǎn)v的度TD（v）=ID（v）+OD（v）,圖中邊/弧的數(shù)目與頂點(diǎn)度的關(guān)系,(若圖中有n個(gè)頂點(diǎn)，e條邊/弧),五、路徑 1.

4、無(wú)向圖G=（V，E）中 從頂點(diǎn)v到v1的路徑是一個(gè)頂點(diǎn)序列: v=Vi,0, Vi,1,Vi,m =v1 其中（Vi,j-1，Vi,j）E， 1jm,3.路徑的長(zhǎng)度是路徑上邊或弧的數(shù)目,2.有向圖G=（V，A） 從頂點(diǎn)v到v1的路徑是一個(gè)有向頂點(diǎn)序列: v=Vi,0, Vi,1,Vi,m=v1 其中Vi,j-1，Vi,jA， 1jm,4.第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同的路徑稱為回路或環(huán)Cycle 5.序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑稱為簡(jiǎn)單路徑 除第一個(gè)和最后一個(gè)頂點(diǎn)外，其余頂點(diǎn)不重復(fù)出現(xiàn)的回路稱為簡(jiǎn)單回路,六、連通圖 Connected Graph 1.無(wú)向圖 v到v1有路徑，稱v和v1是連通的 若

5、圖中任意兩個(gè)頂點(diǎn)vi、vjV都是連通的 則稱G是連通圖,2.若一個(gè)無(wú)向圖中有n個(gè)頂點(diǎn)和少于n-1條邊 則該圖是非連通圖 若它有多于n-1條邊，則一定有環(huán),3.有向圖 對(duì)于每一對(duì)vi、vjV,從vi到vj和vj到vi 都存在路徑,則稱 G為強(qiáng)連通圖,七、圖的ADT ADT Graph 數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)。 數(shù)據(jù)關(guān)系R： R=VR VR=|v,wV且p(v,w), 表示從v到w的弧， 謂詞P(v,w)定義了弧的意義或信息 基本操作P： CreateGraph( 初始條件:圖G存在. 操作結(jié)果:銷毀圖G。,LocateVex(G,u); 初始條件：圖G存在，u和G

6、中頂點(diǎn)有相同特征。 操作結(jié)果: 若G中存在頂點(diǎn)u，則返回該點(diǎn)在圖中的位置,否則返回其它信息。,GetVex(G,v); 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。 操作結(jié)果: 返回v的值,PutVex( 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。 操作結(jié)果: 對(duì)v賦值 value。,FirstAdjVex(G,v); 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)。 操作結(jié)果:返回v的第一個(gè)鄰接頂點(diǎn)。 若頂點(diǎn)在G中沒有鄰接頂點(diǎn)，則返回“空”。,NextAdjVex(G,v,w); 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn)，w是v的鄰接頂點(diǎn)。 操作結(jié)果: 返回v的（相對(duì)于w的）下一個(gè)鄰接頂點(diǎn)。 若w是v 的最后一個(gè)鄰

7、接點(diǎn)則返回“空”。,InsertVex( 初始條件：圖G存在，v和圖中頂點(diǎn)有相同特征。 操作結(jié)果: 在圖G中增添新頂點(diǎn)v。,DeleteVex( 初始條件：圖G存在，v是G中某個(gè)頂點(diǎn) 操作結(jié)果：刪除G中頂點(diǎn)v及其相關(guān)的弧。,InsertArc( 初始條件：圖G存在，v和w是G中兩個(gè)頂點(diǎn)。 操作結(jié)果：在G中刪除弧。若G是無(wú)向的，則還刪除對(duì)稱弧,DFSTraverse(G,v,Visit(); 初始條件：圖G存在，v是G某個(gè)頂點(diǎn)，Visit是頂點(diǎn)的應(yīng)用函數(shù)。 操作結(jié)果:從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每個(gè)頂點(diǎn)調(diào)用visit一次且 僅一次。一旦visit()失敗，則操作失敗。 BFSTraverse

8、(G,v,Visit(); 初始條件：圖G存在，v是G某個(gè)頂點(diǎn)，visit是頂點(diǎn)的應(yīng)用函數(shù)。 操作結(jié)果: 從頂點(diǎn)v起廣度優(yōu)先遍歷圖G， 并對(duì)每個(gè)頂點(diǎn)調(diào)用visit 一次且僅一次。 一旦visit()失敗，則操作失敗。 ADT Graph,7.2 圖的存儲(chǔ)結(jié)構(gòu),在圖中，無(wú)法用數(shù)據(jù)元素在存儲(chǔ)區(qū)的物理位置表示元素之間的關(guān)系。,一、數(shù)組表示法(鄰接矩陣表示法) 用一個(gè)數(shù)組存儲(chǔ)頂點(diǎn)的信息， 用另一個(gè)數(shù)組存儲(chǔ)邊或弧的信息-鄰接矩陣,15,10,5,30,12,20,3,2,1,0,4,1.圖的數(shù)組存儲(chǔ)表示 / _ _ _ _ _ _圖的數(shù)組（鄰接矩陣）存儲(chǔ)表示 _ _ _ _ _ _ _ #define

9、INFINITY INT_MAX / 最大值 #define MAX_VERTEX_NUM 20 /最大頂點(diǎn)個(gè)數(shù) typedef enum DG,DN,UDG,UDNGraphKind; /有向圖，有向網(wǎng)，無(wú)向圖，無(wú)向網(wǎng) typedef struct ArcCell VRType adj; /VRType是頂點(diǎn)關(guān)系類型.對(duì)無(wú)權(quán)圖,用1或0 /表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類型。 InfoType *Info; /該弧相關(guān)信息的指針 ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;,typedef struct VertexType vexsMAX_

10、VERTEX_NUM; / 頂點(diǎn)向量 AdjMatrix arcs; / 鄰接矩陣 int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) GraphKind kind; / 圖的種類標(biāo)志 MGraph;,Mgraph G1; G1.vexnum=4 G1. arcnum=4 G1.kind=DG,G1.arcs01.adj=1,G1.arcs,2圖的構(gòu)造方法 Status CreateGraph( MGraph / CreateGraph,Status CreateUDN(MGraph /adj,info,for (k=0; k的權(quán)值 if (IncInfo) Input(* G.

11、); / 若弧含有相關(guān)信息,則輸入 G.arcsji =G.arcsij; / 置的對(duì)稱弧 return OK; / CreateUDN,二、鄰接表Adjacency List 方法：對(duì)每個(gè)頂點(diǎn)建立一個(gè)單向鏈表 鏈接與vi有邊相連的頂點(diǎn)（無(wú)向圖） 或從vi出發(fā)到達(dá)的頂點(diǎn)（有向圖）,指向該點(diǎn)出發(fā)到達(dá)的第一條弧,每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)頭結(jié)點(diǎn),每條邊/弧對(duì)應(yīng)一個(gè)結(jié)點(diǎn),無(wú)向圖,邊結(jié)點(diǎn),有向圖,/- - - - - - - 圖的鄰接表存儲(chǔ)表示 - - - - - - - #define MAX_VERTEX_NUM 20 typedef struct ArcNode int adjvex

12、; / 該弧所指向的頂點(diǎn)的位置 struct ArcNode * nextarc; / 指向下一條弧的指針 InfoType * info; / 該弧相關(guān)信息的指針 ArcNode ;,typedef struct VNode VertexType data; / 頂點(diǎn)信息 ArcNode * firstarc; / 指向第一條依附頂點(diǎn)的弧的指針 VNode, AdjListMAX_VERTEX_NUM ;,typedef struct AdjList vertices; int vexnum, arcnum; / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; / 圖的種類標(biāo)志 ALGraph;,

13、# define MAX_VERTEX_NUM 20 typedef struct ArcBox int tailvex, headvex ; / 該弧的尾和頭頂點(diǎn)的位置 struct ArcBox *hlink, *tlink; /分別為弧頭相同和弧尾相同的弧的鏈域 Info type *info; / 該弧相關(guān)信息的指針 ArcBox;,typedef struct VexNode VertexType data; ArcBox * firstin, * firstout; /分別指向該頂點(diǎn)第一條入弧和出弧 VexNode ; typedef struct VexNode xlist MA

14、X_VERTEX_NUM ; / 表頭向量 int vexnum, arcnum; / 有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) OLGraph ;,Status CreateDG(OLGraph / 初始化指針 ,for(k=0; kinfo); /若弧含有相關(guān)信息，則輸入 / CreateDG,四、鄰接多重表 Adjancency Multilist 頂點(diǎn)和邊分別用一個(gè)結(jié)點(diǎn)表示 邊：,該邊是否搜索過(guò),頂點(diǎn)i在圖中的位置(編號(hào)),下一條與i有關(guān)的邊,有關(guān)邊的信息,# define MAX_VERTEX_NUM 20 typedef enum unvisited, visitedVisitIf ; typed

15、ef struct EBox VisitIf mark; / 訪問(wèn)標(biāo)記 int ivex, jvex; / 該邊依附的兩個(gè)頂點(diǎn)的位置0 struct EBox * ilink, * jlink; /分別指向依附這兩個(gè)頂點(diǎn)的下一條邊 InfoType * info; / 該邊信息指針 EBox; typedef struct VexBox VertexType data; EBox * firstedge ; / 指向第一條依附該頂點(diǎn)的邊 VexBox;,typedef struct VexBox adjmulist MAX_VERTEX_NUM ; int vexnum, edgenum; /

16、 無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù) AMLGraph ;,73圖的遍歷Traversing Graph,圖的遍歷： 從圖中某個(gè)頂點(diǎn)出發(fā)訪問(wèn)遍圖中每個(gè)頂點(diǎn)， 且圖中每個(gè)頂點(diǎn)僅被訪問(wèn)一次。 遍歷過(guò)程中每個(gè)頂點(diǎn)可能被訪問(wèn)多次， 因此，每個(gè)頂點(diǎn)被訪問(wèn)后需作一個(gè)標(biāo)記 一般用一個(gè)數(shù)組標(biāo)記某個(gè)結(jié)點(diǎn)是否被訪問(wèn) 遍歷方法：深度優(yōu)先搜索、廣度優(yōu)先搜索,一、深度優(yōu)先收索Depth-First-Search(DFS) 方法： 從圖中某個(gè)頂點(diǎn)出發(fā)（設(shè)為v1），訪問(wèn)v1， 從v1出發(fā),選擇一個(gè)未被訪問(wèn)的鄰接點(diǎn)vk,訪問(wèn)vk， 從vk出發(fā)，選擇一個(gè)未被訪問(wèn)的鄰接點(diǎn), 若vk的所有鄰接頂點(diǎn)都被訪問(wèn)過(guò)了， 回到vk-1,再選擇的一個(gè)未

17、被訪問(wèn)的鄰接點(diǎn), 若圖中仍有未被訪問(wèn)的頂點(diǎn)， 從中選擇一個(gè)作為起點(diǎn)，重復(fù)上述過(guò)程 直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止。,從v1出發(fā),選擇一個(gè)未被訪問(wèn)的鄰接點(diǎn)vk,訪問(wèn)vk， 從vk出發(fā)，選擇一個(gè)未被訪問(wèn)的鄰接點(diǎn), 若vk的所有鄰接頂點(diǎn)都被訪問(wèn)過(guò)了， 回到vk-1,再選擇的一個(gè)未被訪問(wèn)的鄰接點(diǎn), 若圖中仍有未被訪問(wèn)的頂點(diǎn)， 從中選擇一個(gè)作為起點(diǎn)，重復(fù)上述過(guò)程 直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止。,Boolean visitedMAX; / 訪問(wèn)標(biāo)志數(shù)組 Status (* VisitFunc)(int v); / 函數(shù)指針變量 void DFSTraverse(Graph G, Status(* Visit)(

18、int v) / 對(duì)圖G作深度優(yōu)先遍歷 VisitFunc = Visit; /使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù) for(v=0; vG.vexnum; +v) visitedv = FALSE ; / 訪問(wèn)標(biāo)志數(shù)組初始化 for(v=0; vG.vexnum; +v ) if(!visitedv) DFS (G,v ); /對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFS ,/從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G void DFS(Graph G, int v) visitedv=TRUE; VistFunc(v); /訪問(wèn)第v個(gè)頂點(diǎn) for(w=FirstAdjVex(G,v);w0

19、; w=NextAdjVex(G,v,w) if(!visitedw) DFS(G,w); /對(duì)v的尚未訪問(wèn)的鄰接頂點(diǎn)w遞歸調(diào)用DFS printf(v); /起什么作用 ,1,2,3,4,5,6,7,8,9,搜索,回退,二、廣度優(yōu)先收索Breadth-First-Search(BFS) 方法： 從圖中某個(gè)頂點(diǎn)出發(fā)（設(shè)為vi），訪問(wèn)vi， 從vi出發(fā)，依次訪問(wèn)vi的所有未被訪問(wèn)的鄰接點(diǎn)， 再?gòu)倪@些鄰接點(diǎn)出發(fā)， 依次訪問(wèn)它們的所有未被訪問(wèn)的鄰接點(diǎn), 若圖中仍有未被訪問(wèn)的頂點(diǎn)， 從中選擇一個(gè)作為起點(diǎn)，重復(fù)上述過(guò)程 直到所有頂點(diǎn)均被訪問(wèn)過(guò)為止。,void BFSTraverse(Graph G,St

20、atus(* Visit)(int v) / 按廣度優(yōu)先非遞歸遍歷圖G。使用輔助隊(duì)列Q和訪問(wèn)標(biāo)志數(shù)組visited。 for(v=0; v0;w=NextAdjVex(G,u,w) if(!visitedw) visitedw = TRUE; Visit(w); EnQueue(Q,w); / u的尚未訪問(wèn)的鄰接頂點(diǎn)w入隊(duì)列Q /while / if / BFSTraverse,搜索,1,2,3,4,5,6,7,8,9,74圖的連通性問(wèn)題,一、無(wú)向圖的連通分量和生成樹 1.連通分量 無(wú)向圖的極大連通子圖。即:子圖中不能再增加一個(gè)頂點(diǎn),已有頂點(diǎn)的邊均包含在內(nèi)。 無(wú)向圖的連通分量的產(chǎn)生-多次調(diào)用D

21、FS 2.生成樹 一個(gè)連通圖的生成樹是一個(gè)極小連通子圖,且含有圖中全部頂點(diǎn),無(wú)向圖,連通分量,連通圖,生成樹,3.無(wú)向圖的生成樹 對(duì)一個(gè)連通圖G，從圖中任意一個(gè)頂點(diǎn)出發(fā)遍歷圖時(shí)，把E分為E1和E2，E1為遍歷過(guò)程中經(jīng)過(guò)的邊的集合，E2為剩余邊的集合，則E1與V構(gòu)成G的極小連通圖，即連通圖的一棵生成樹 若遍歷為DFS，則稱為深度優(yōu)先生成樹 若遍歷為BFS，則稱為廣度優(yōu)先生成樹,對(duì)于非連通圖，每個(gè)連通分量中的頂點(diǎn)集合,加上遍歷時(shí)經(jīng)過(guò)的邊，構(gòu)成了非連通圖的生成森林。,生成森林,4.無(wú)向非連通圖的深度優(yōu)先生成森林 void DFSForest(Graph G,CSTree /建立以p為根的生成樹 /D

22、FSForest,void DFSTree(Graph G, int v, CSTree /從第w個(gè)頂點(diǎn)出發(fā)深度優(yōu)先遍歷圖G,建立子生成樹q / if / DFSTree,二、最小生成樹Mininum Cost Spanning Tree 問(wèn)題： 設(shè)有n個(gè)城市，兩個(gè)城市之間都可以有一條路線，如何從最多n(n-1)/2條邊中選擇代價(jià)和最小的n-1條邊(要包含所有頂點(diǎn)),就是連通圖的最小代價(jià)生成樹問(wèn)題，簡(jiǎn)稱最小生成樹。,1.普里姆算法Prim 設(shè)N=（V，E）為連通網(wǎng) 用TE表示N上最小生成樹邊的集合 (1)從V中選一頂點(diǎn)u0加入U(xiǎn)，TE= (2)對(duì)所有uU，vV-U，（u，v）E,找一條代價(jià)最小

23、的邊（u0，v0）加入TE,并把v0加入U(xiǎn) (3)重復(fù)(2)，直到U=V為止,則（V，TE）為N的最小生成樹,U,V-U,v4,v6,v1,v2,v3,v5,1,5,5,5,6,6,6,3,4,2,2MST性質(zhì)(Prime算法正確性證明） 設(shè)N=(V,E)是一個(gè)連通圖, U是V的一個(gè)非空子集 若(u,v)是一個(gè)具有最小代價(jià)的邊,uU，vV-U 則必存在一棵包含邊(u ,v)的最小生成樹,u,v,u,v,U,V-U,證明： 假設(shè)網(wǎng)N的任何一棵最小生成樹都不包含(u ,v) 設(shè)T是N上的一棵最小生成樹，把(u ,v)加入到T中 則T中必存在一條包含(u ,v)的回路 同時(shí),T中必存在另一條邊(u,

24、v)， 其中uU vV-U 并且u和u ,v和v之間均存在路徑相通 刪去邊(u,v)，則可削去回路， 得到另一棵生成樹T 顯然,T的代價(jià)不高于T,且包含邊(u ,v),矛盾。,設(shè)N=（V，E）為連通網(wǎng) 用TE表示N上最小生成樹邊的集合 (1)從V中選一頂點(diǎn)u0加入U(xiǎn)，TE= (2)對(duì)所有uU，vV-U，（u，v）E,找一條代價(jià)最小的邊（u0，v0）加入TE,并把v0加入U(xiǎn) (3)重復(fù)(2),直到U=V為止,則（V,TE）為N的最小生成樹,圖-鄰接矩陣 最小的邊（u0，v0）（ u0U，v0V-U）用矩陣closedge表示,struct VertexType adjvex; /最短的邊對(duì)應(yīng)u中

25、的頂點(diǎn) VRType lowcost;/記錄u中頂點(diǎn)到頂點(diǎn)j的最短的邊 closedgeMAX_VERTEX_NUM;,void MiniSpanTree_PRIM(MGraph G,VertexType u) k = LocateVex(G, u ); for(j=0;jG.vexnum; +j ) / 輔助數(shù)組初始化 if(j!=k) closedgej=u,G.arcskj.adj; /adjvex,lowcost closedgek.lowcost = 0; / 初始，U = u,for(i=1; iG.vexnum;+i) / 選擇其余G.vexnum-1個(gè)頂點(diǎn) k =minimum

26、(closedge); /求出T的下一個(gè)結(jié)點(diǎn):第k頂點(diǎn) printf(closedgek.adjvex,G.vexsk); /輸出生成樹的邊 closedgek.lowcost = 0; /第k頂點(diǎn)并入U(xiǎn)集 for (j=0; jG.vexnum; +j) if(G.arcskj.adjclosedgej.lowcost) closedgej=G.vexsk,G.arcskj.adj; / MiniSpanTree,3.克魯斯卡爾算法 設(shè)連通圖N=（V，E） (1)構(gòu)造非連通圖T=(V,),圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量 (2)在E中選擇代價(jià)最小的邊（u，v），并刪去該邊。若(u,v)落在T中不

27、同的連通分量上,則將此邊加入T中 (3)重復(fù)(2），直到T中只有一個(gè)連通分量為止,2,4,5,3,6.5有向無(wú)環(huán)圖及其應(yīng)用,一、DAG圖 -Directed Acycline Graph 一個(gè)無(wú)環(huán)的有向圖稱為有向無(wú)環(huán)圖,二、拓?fù)渑判?Topological Sort 1AOV網(wǎng) Activity On Vertex Network 用頂點(diǎn)表示活動(dòng)， 用弧表示活動(dòng)之間的優(yōu)先關(guān)系的有向圖 稱為頂點(diǎn)表示活動(dòng)的網(wǎng)，簡(jiǎn)稱AOV網(wǎng)。 在網(wǎng)中,若頂點(diǎn)i到頂點(diǎn)j有一條路徑,則i為前驅(qū), j為后繼。若A，則vi為vj的直接前驅(qū)，vj為vi直接后繼,在AOV網(wǎng)中不能出現(xiàn)環(huán)，判定網(wǎng)中是否出現(xiàn)環(huán)的辦法是拓?fù)渑判?。若?/p>

28、有的頂點(diǎn)都在拓?fù)溆行蛐蛄兄?，則AOV網(wǎng)中無(wú)環(huán)，否則有環(huán)。,C語(yǔ)言程序設(shè)計(jì),數(shù)據(jù)結(jié)構(gòu)與算法,面向?qū)ο蟪绦蛟O(shè)計(jì),計(jì)算機(jī)網(wǎng)絡(luò)原理,信息科學(xué)導(dǎo)論,電路原理,大學(xué)物理,數(shù)字邏輯電路實(shí)驗(yàn),組成原理實(shí)驗(yàn),操作系統(tǒng),匯編語(yǔ)言程序設(shè)計(jì),高等數(shù)學(xué)1,離散數(shù)學(xué),數(shù)據(jù)庫(kù)原理,線性代數(shù),基礎(chǔ)物理實(shí)驗(yàn)B,高等數(shù)學(xué)2,高等數(shù)學(xué)3,C程序設(shè)計(jì)實(shí)驗(yàn),數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn),電路原理實(shí)驗(yàn),概率與數(shù)理統(tǒng)計(jì),數(shù)字邏輯電路,計(jì)算機(jī)組成原理,網(wǎng)絡(luò)原理實(shí)驗(yàn),操作系統(tǒng)實(shí)驗(yàn),面向?qū)ο髮?shí)驗(yàn),2拓?fù)浯涡?設(shè)AOV網(wǎng)中有n個(gè)頂點(diǎn)V1，V2，Vn， 將頂點(diǎn)排成這樣一個(gè)線性次序：Vi1，Vi2，Vin， 其中i1，i2，in是1到n的一個(gè)排列 且若V ij，V

29、ikA，則jk,對(duì)AOV網(wǎng)給出拓?fù)浯涡虻倪^(guò)程稱為拓?fù)渑判?3拓?fù)渑判蛩惴?(1)在網(wǎng)中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出它 (2)從圖中刪去該頂點(diǎn)及所有以它為尾的弧 (3)重復(fù)(1)(2)直到所有頂點(diǎn)被輸出 或圖中不存在無(wú)前驅(qū)的頂點(diǎn)為止,。采用鄰接表作存儲(chǔ)結(jié)構(gòu) 。用一個(gè)數(shù)組indegree存放頂點(diǎn)的入度 。用一個(gè)棧存放入度為0的頂點(diǎn),Status TopologicalSort( ALGraph G) /有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。 /若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K, /否則ERROR FindInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度indegree InitS

30、tack(S); / 建零入度頂點(diǎn)棧S for(i=0; iG.vexnum; +i ) if(!indegreei) Push(S, i); / 入度為0者進(jìn)棧 count = 0; / 對(duì)輸出頂點(diǎn)計(jì)數(shù),while(!StackEmpty(S) Pop(S,i); printf(i,G.verticesi.data); +count; / 輸出i號(hào)頂點(diǎn)并計(jì)數(shù) for(p=G.verticesi.firstarc; p; p=p-nextarc) k = p-adjvex; /對(duì)i 號(hào)頂點(diǎn)的每個(gè)鄰接的入度減1 if(!(- -indegreek)Push(S, k); /若入度減為0，則入棧

31、/ for DestroyStack(S); if(countG.vexnum) return ERROR; /該有向圖有回路 else return OK; / TopologicalSort,。還可以利用深度優(yōu)先遍歷過(guò)程進(jìn)行拓?fù)渑判?，按退出DFS的逆序?yàn)橥負(fù)浯涡?1,2,3,4,5,6,拓?fù)浯涡驗(yàn)椋簐6、v1、v4、v3、v5、v2,4.關(guān)鍵路徑 AOE網(wǎng)Activity On Edge 頂點(diǎn)-事件 邊-活動(dòng) 權(quán)-活動(dòng)持續(xù)的時(shí)間 用AOE網(wǎng)估計(jì)工程的完工時(shí)間,Vi表示在此之前的活動(dòng)已完成，在此之后的活動(dòng)可以開始,1,2,3,4,5,買面粉3,買雞蛋3,買白菜4,買熟食6,6,7,剁餡5,切

32、2,和面2,煮雞蛋1,包餃子4,最短要多久才能包好餃子,開始聚餐?,在一般情況下,AOE網(wǎng)中只有一個(gè)入度為0的頂點(diǎn),稱為源點(diǎn) 只有一個(gè)出度為0的頂點(diǎn)，稱為匯（聚）點(diǎn) ？完成整個(gè)工程至少需要多少時(shí)間 -從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 ？哪些活動(dòng)是影響工程進(jìn)度的關(guān)鍵,路徑長(zhǎng)度最長(zhǎng)的路徑叫做關(guān)鍵路徑 Critical Path 從源點(diǎn)到Vi的最長(zhǎng)路徑叫做事件的最早發(fā)生時(shí)間,也就是所有以Vi為尾的弧所表示活動(dòng)的最早開始時(shí)間,令e(i)表示ai的最早開始時(shí)間 l(i)表示ai的最遲開始時(shí)間 l(i)-e(i)為時(shí)間余量 關(guān)鍵路徑上的所有活動(dòng)有：l(i)=e(i) 把所有e(i)=l(i)的活動(dòng)叫做關(guān)鍵活動(dòng)。,設(shè)

33、ai由弧表示 ve(j)表示事件j的最早發(fā)生時(shí)間 vl(j)表示事件j的最遲發(fā)生時(shí)間 ai的持續(xù)時(shí)間為dut() 則：e(i)=ve(j) l(i)=vl(k)-dut(),最早開始時(shí)間:前驅(qū)活動(dòng)都按期完成情況下的開始時(shí)間 最遲開始時(shí)間:保證所有活動(dòng)都能按期完成情況下最晚開始時(shí)間 關(guān)鍵路徑上的所有活動(dòng)最早=最遲,計(jì)算的方法： （1）ve(0)=0 （2）按拓?fù)漤樞蛴?jì)算：,其中T是所有以第j個(gè)頂點(diǎn)為頭的弧的集合,（3）vl(n-1)=ve(n-1) （4）按逆拓?fù)漤樞蛴?jì)算：,其中S是所有以第i個(gè)頂點(diǎn)為尾的弧的集合,（5）根據(jù)各頂點(diǎn)的ve和vl的值 計(jì)算每條弧s的e(s)和l(s),ve(3)=5

34、,ve(4)=7,ve(7)=14,ve(8)=18,vl(8)=18,vl(7)=14 vl(6)=16,vl(4)=7,ve(0)=0,vl(1)=6 vl(2)=6,vl(0)=0,ve(5)=7,ve(6)=16,vl(5)=10,vl(3)=8,ve(2)=4 ve(1)=6,Status TopologicalOrder(ALGraph G, Stack / 初始化,while (! StackEmpty(S) Pop(S, j); Push(T,j); +count; /j號(hào)頂點(diǎn)入T棧并計(jì)數(shù) for(p=G.verticesj.firstarc;p;p=p-nextarc) k

35、= p-adjvex; / 對(duì)j號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1 if(-indegreek=0)Push(S, k); /若入度減為0，則入棧 if(vej+*(p-info)vek)vek=vej+*(p-info); / *(p-info)= dut() / while DestroyStack(S); if(countG.vexnum) return ERROR; /該有向網(wǎng)有回路 else return OK; / TopologicalOrder,Status CriticalPath(ALGraph G) /G為有向網(wǎng)，輸出G的各項(xiàng)關(guān)鍵活動(dòng) if(!TopologicalOrder(

36、G,T) return ERROR; vl0.G.vexnum-1=veG.vexnum-1; /初始化頂點(diǎn)事件的最遲發(fā)生時(shí)間 while (! StackEmpty(T) /按拓?fù)淠嫘蚯蟾黜旤c(diǎn)的v1值 for(Pop(T,j),p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; dut = * (p-info); / dut if(vlk-dutv1j) vlj = vlk-dut; / for,for(j=0;jnextarc) k = p-adjvex; dut = * (p-info) ; ee=vej; el=vlk-dut; ta

37、g=(ee=e1)? * : ; printf ( j,k, dut, ee, el, tag); / 輸出關(guān)鍵活動(dòng) / CriticalPath,76最短路徑 用頂點(diǎn)表示城市， 用邊表示城市之間的交通狀況 用邊上的權(quán)表示城市之間的耗費(fèi)（距離、時(shí)間、各種費(fèi)用等） 一、從一點(diǎn)到另一點(diǎn)，經(jīng)過(guò)的結(jié)點(diǎn)最少 二、從某個(gè)源點(diǎn)到其余各個(gè)頂點(diǎn)的最短路徑 給定帶權(quán)的有向圖G和源點(diǎn)v， 求從v到G中其余各點(diǎn)的最短路徑 方法：按路徑長(zhǎng)度遞增序產(chǎn)生最短路徑 -迪杰斯特拉Dijksta方法,v0,v5,60,v1,v2,v3,v4,100,30,10,10,50,5,20,v0,v5,v1,v2,v3,v4,存儲(chǔ)結(jié)構(gòu) 用帶權(quán)的鄰接矩陣arcs表示帶權(quán)有向圖 arcsij= A 上的權(quán)值 A,算法 (1)設(shè)S為已找到從v出發(fā)的最短路徑的終點(diǎn)集合, 初值S= Di表示從v到Vi的最短路徑的長(zhǎng)度 若A,Di為從v到Vi上的權(quán),否則為 即：Di=arcsLo