深圳大學-數據結構-2017圖演示文檔
《深圳大學-數據結構-2017圖演示文檔》由會員分享,可在線閱讀,更多相關《深圳大學-數據結構-2017圖演示文檔(96頁珍藏版)》請在裝配圖網上搜索。
.,第七章圖,數據結構,.,一、圖的定義(Graph),2,圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構: Graph( V, E ) 其中V = x | x數據對象是頂點的有窮非空集合 E是頂點之間關系的有窮集合,包括 E1 = (x, y) | x, y V 邊的集合 或 E2 = | x, y V 弧的集合,第一節(jié)圖的定義與術語,.,第一節(jié)圖的定義與術語,交通圖(公路、鐵路) 頂點:地點 邊:連接地點的公路交通圖中有單行道雙行道,分別用有向邊、無向邊表示;電路圖 頂點:元件 邊:連接元件之間的線路通訊線路圖 頂點:地點 邊:地點間的連線,.,二、無向圖(Undigraph),4,第一節(jié)圖的定義與術語,用(x,y)表示兩個頂點x,y之間的一條邊(edge)N=V,E,V=0,1,2,3,4,5,E=(0,1), (0,4), (0,5), (1,2), (1,3), (1,5), (2,3), (3,4), (3,5), (4,5),.,二、無向圖(完全圖),5,第一節(jié)圖的定義與術語,如果無向圖有n(n-1)/2條邊,稱為無向完全圖,.,二、無向圖,6,第一節(jié)圖的定義與術語,鄰接點:如果(x,y)E,稱x,y互為鄰接點,即x,y相鄰接依附:邊(x,y)依附于頂點x,y相關聯:邊(x,y)與x,y相關聯頂點的度:和頂點相關聯的 邊的數目,記為TD(x),.,三、有向圖(Digraph),7,第一節(jié)圖的定義與術語,用表示從x到y的一條弧(Arc),且稱x為弧尾,y為弧頭,N=V,E,V=0,1,2,3,4,E=, ,.,三、有向圖(完全圖),8,第一節(jié)圖的定義與術語,如果有向圖有n(n-1)條邊,則稱為有向完全圖,.,三、有向圖,9,第一節(jié)圖的定義與術語,鄰接:如果E,稱x鄰接到y,或y鄰接自x相關聯:弧與x,y相關聯入度:以頂點為頭的弧的 數目,記為ID(x)出度:以頂點為尾的弧的 數目,記為OD(x)度:TD(x)=ID(x)+OD(x),.,四、路徑(Path),10,第一節(jié)圖的定義與術語,路徑:是一個從頂點x到y的頂點序列(x, vi1, vi2, vin, y)其中,(x,vi1),(vij-1,vij),(vin,y)皆屬于E,1到3有路徑(1,0,4,3),1到4有路徑(1,2,4),.,五、回路,11,第一節(jié)圖的定義與術語,回路或環(huán):路徑的開始頂點與最后一個頂點相同,即路徑中(x, vi1, vi2, vin, y),x=y簡單路徑:路徑的頂點序列中,頂點不重復出現,1到1構成環(huán)(1,0,4,3,1),1到3是簡單路徑(1,0,4,3),.,六、連通,12,第一節(jié)圖的定義與術語,連通:如果頂點x到y有路徑,稱x和y是連通的連通圖:圖中所有頂點都連通,連通圖,非連通圖,.,七、子圖,13,第一節(jié)圖的定義與術語,設有兩個圖 G(V, E) 和 G(V, E)。若 V V 且 EE, 稱圖G是圖G的子圖,.,八、生成樹,14,第一節(jié)圖的定義與術語,一個連通圖的生成樹是一個極小連通子圖,它含有圖中全部n個頂點,但只有足以構成一棵樹的n-1條邊,.,第二節(jié)圖的存儲結構,圖的鄰接矩陣存儲表示法圖的鄰接表表示法圖的逆鄰接表表示法圖的十字鏈表表示法圖的鄰接多重表表示法,.,一、鄰接矩陣(Adjacency Matrix),16,第二節(jié)圖的存儲結構,鄰接矩陣:記錄圖中各頂點之間關系的二維數組。對于不帶權的圖,以1表示兩頂點存在邊(或弧)(相鄰接),以0表示兩頂點不鄰接,即 1 如果(i,j)E 或 EAij = 0 其它,.,一、鄰接矩陣,17,第二節(jié)圖的存儲結構,無向圖的鄰接矩陣為:有向圖的鄰接矩陣為:,.,一、鄰接矩陣(性質),18,第二節(jié)圖的存儲結構,無向圖的鄰接矩陣是對稱的其第i行1的個數或第i列1的個數,等于頂點i的度TD(i)有向圖的鄰接矩陣可能是不對稱的其第i行1的個數等于頂點i的出度OD(i),第j列1的個數等于頂點j的入度ID(j),.,一、鄰接矩陣(網絡),19,第二節(jié)圖的存儲結構,有時在圖的每條邊上附上相關的數值,這種與圖的邊相關的數值叫權。 權可以表示兩個頂點之間的距離、耗費等具有某種意義的數,若將圖的每條邊都賦上一個權,則稱這種帶權圖為網絡。 在網絡中,兩個頂點如果不鄰接,則被視為距離為無窮大; wi,j 如果(i,j)E 或 EAij = 其它,.,一、鄰接矩陣(網絡),20,第二節(jié)圖的存儲結構,有向網N=V,E,V=0,1,2,3,4,E=, E中每個元組的第三個元素表示權。 1、畫出該網, 2、寫出該網的鄰接矩陣。,.,一、鄰接矩陣(定義),21,第二節(jié)圖的存儲結構,#define MAXVERTEXNUM 100 /最大頂點數typedef struct int VertexNum; /頂點數char VertexMAXVERTEXNUM;/頂點數據int AdjMatrixMAXVERTEXNUMMAXVERTEXNUM; / 鄰接矩陣 Graph;Graph MGraph;,.,一、鄰接矩陣(創(chuàng)建),22,第二節(jié)圖的存儲結構,#define INFINITY100/無窮大void CreateGraph(Graph *G) /生成圖int i, j;cin G-VertexNum;/輸入圖的頂點數for (i=1; iVertexNum; i+)cin G-Vertexi; /輸入頂點信息for (i=1; iVertexNum; i+) for (j=1; jVertexNum; j+) cin G-AdjMatrixij; /依次輸入鄰接矩陣 if (G-AdjMatrixij = -1) G-AdjMatrixij = INFINITY; ,.,二、鄰接表(Adjacency List),23,第二節(jié)圖的存儲結構,鄰接表是圖的一種鏈式存儲結構在鄰接表中,每個頂點設置一個單鏈表,其每個結點都是依附于該頂點的邊(或以該頂點為尾的?。?.,二、鄰接表(結點結構),24,第二節(jié)圖的存儲結構,邊(弧)的結點結構 adjvex; / 該邊(弧)所指向的頂點的位置 nextarc;/ 指向下一條邊(弧)指針 info; / 該邊(弧)相關信息的指針或權值頂點的結點結構 data; / 頂點信息 firstarc;/指向第一條依附該頂點的邊(弧),.,typedef struct VexNode / 定義圖的頂點 char Vertex;/ 頂點int Weight;/ 邊(?。┑臋嘀祍truct VexNode *NextArc;/ 指向下一條邊(弧)指針 VexNode;,第二節(jié)圖的存儲結構,二、鄰接表(結點結構),.,二、鄰接表(無向圖),26,第二節(jié)圖的存儲結構,.,二、鄰接表(有向圖),27,第二節(jié)圖的存儲結構,.,二、鄰接表(網絡),28,第二節(jié)圖的存儲結構,.,二、鄰接表(定義),29,第二節(jié)圖的存儲結構,typedef struct / 定義圖(采用鄰接鏈表)int VertexNum;/ 頂點數VexNode *AdjList;/ 鄰接表頭指針 Graph;Graph MGraph;,.,二、鄰接表(創(chuàng)建),30,第二節(jié)圖的存儲結構,void CreateGraph(Graph *G)/ 創(chuàng)建圖(鄰接表)int i, ArcNum;char x, y;cin G-VertexNum;/ 輸入頂點數G-AdjList=new VexNodeG-VertexNum+1; / 申請n個頭結點for (i=1; iVertexNum; i+) cin G-AdjListi.Vertex;/ 輸入頂點信息(字符)G-AdjListi.NextArc=NULL; / 頭頂點下一條邊指針為空 cin ArcNum; / 輸入邊(?。礷or (i=1; i x; / 輸入頂點1(或弧尾)cin y; / 輸入頂點2(或弧頭)InsertLinkList(G, x, y); / 在x單鏈表中,插入y結點InsertLinkList(G, y, x); / 插入x結點(無向圖),.,二、鄰接表(創(chuàng)建插入結點),31,第二節(jié)圖的存儲結構,void InsertLinkList(Graph *G, char x, char y)int j;VexNode *p, *q;j = GetVexNodeNo(G, x); / 找到頂點x對應的單鏈表頭結點q = new VexNode;/ 申請一個新結點q-Vertex = y;/ 邊的另一個頂點(弧頭)為yq-NextArc = NULL;if (G-AdjListj.NextArc=NULL)|(G-AdjListj.NextArc-Vertexy)q-NextArc = G-AdjListj.NextArc; / 插入結點G-AdjListj.NextArc = q;else p = G-AdjListj.NextArc;while(p-NextArc),.,二、鄰接表(創(chuàng)建頂點對應的序號),32,第二節(jié)圖的存儲結構,int GetVexNodeNo(Graph *G, char c) / 找到字符對應的單鏈表序號 int j; for (j=1; jVertexNum; j+) if (G-AdjListj.Vertex = c) break; return(j);,.,二、鄰接表(性質),33,第二節(jié)圖的存儲結構,有向圖鄰接表: 頂點的出度-第i個鏈表中結點的個數; 頂點的入度-必須遍歷整個鄰接表也可以建立一個逆鄰接表要判定兩個頂點i和j是否有邊(或?。仨毸阉髡麄€第i個和第j個鏈表,不及鄰接矩陣方便,.,二、鄰接表(有向圖的逆鄰接表),34,第二節(jié)圖的存儲結構,逆鄰接表中,弧的箭頭向內(入弧),.,三、十字鏈表(Orthogonal List),35,第二節(jié)圖的存儲結構,十字鏈表是有向圖的另一種存儲結構十字鏈表是將有向圖的鄰接表和逆鄰接表結合起來的一種存儲結構,.,三、十字鏈表(結點結構),36,第二節(jié)圖的存儲結構,弧的結點結構 tailvex;/ 弧尾頂點的位置 headvex;/ 弧頭頂點的位置 tlink; / 指向弧尾相同的下一條弧 hlink; / 指向弧頭相同的下一條弧 info; / 該弧相關信息的指針或權值,.,三、十字鏈表(結點結構),37,第二節(jié)圖的存儲結構,頂點的結點結構data; / 與頂點相關的信息firstin; / 指向以頂點為弧頭的第一個弧結點firstout;/ 指向以頂點為弧尾的第一個弧結點,.,三、十字鏈表(舉例),38,第二節(jié)圖的存儲結構,.,四、鄰接多重表(Adjacency Multilist),39,第二節(jié)圖的存儲結構,鄰接多重表是無向圖的另一種存儲結構在無向圖中,一條邊要用2個結點表示(分別從2個頂點的角度看)在鄰接多重表中,一條邊只用一個結點表示將所有具有某頂點的結點,全部用鏈連結起來,鏈所在的域為該頂點對應的指針域,.,四、鄰接多重表(結點結構),40,第二節(jié)圖的存儲結構,邊的結點結構 mark; / 標記域,如指示該邊是否被搜索過 ivex,jvex;/ 該邊所依附的兩個頂點的位置 ilink;/ 指向下一條依附于ivex的邊 jlink;/ 指向下一條依附于jvex的邊 info; / 該邊相關信息的指針或權值,.,四、鄰接多重表(舉例),41,第二節(jié)圖的存儲結構,.,一、圖的遍歷,42,第三節(jié)圖的遍歷,從圖的某一頂點開始,訪遍圖中其余頂點,且使每一個頂點僅被訪問一次圖的遍歷主要應用于無向圖,.,二、深度優(yōu)先搜索(DFS),43,第三節(jié)圖的遍歷,圖的深度優(yōu)先搜索是樹的先根遍歷的推廣圖中可能存在回路,且圖的任一頂點都可能與其它頂點相通,在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。為了避免重復訪問,可設置一個標志頂點是否被訪問過的輔助數組 visited ,.,二、深度優(yōu)先搜索(DFS算法),第三節(jié)圖的遍歷,所有頂點訪問標志visited設置為FALSE從某頂點v0開始,設v=v01.如果visitedv=FALSE,則訪問該頂點,且設visitedv=TRUE2.如果找到當前頂點的一個新的相鄰頂點w,設v=w,重復13.否則(說明當前頂點的所有相鄰頂點都已被訪問過,或者當前頂點沒有相鄰頂點),如果當前頂點是v0,退出;否則返回上一級頂點,重復2,.,二、深度優(yōu)先搜索(舉例),45,第三節(jié)圖的遍歷,采用以下鏈表存儲結構時,DFS次序為0,1,2,3,4,5,visit,.,二、深度優(yōu)先搜索(舉例),46,第三節(jié)圖的遍歷,DFS次序1:V1,V2,V4,V8,V5,V3,V6,V7DFS次序2:V1,V2,V5,V8,V4,V3,V6,V7,由于沒有規(guī)定訪問鄰接點的順序,深度優(yōu)先序列不唯一,.,第三節(jié)圖的遍歷,當采用鄰接表存儲結構并且存儲結構已確定的情況下,遍歷的結果是確定的。,c0,c1,c3,c2,c4,c5,DFS序列:c0 c1 c3 c4 c5 c2,.,三、廣度優(yōu)先搜索(BFS),48,第三節(jié)圖的遍歷,廣度優(yōu)先搜索(BFS)是一種分層搜索方法BFS每向前走一步可能訪問一批頂點, 不存在往回退的情況BFS不是一個遞歸的過程。,.,三、廣度優(yōu)先搜索(BFS算法),49,第三節(jié)圖的遍歷,所有頂點訪問標志visited設置為FALSE從某頂點v0開始,訪問v0,visitedv0=TRUE,將v0插入隊列Q1.如果隊列Q不空,則從隊列Q頭上取出一個頂點v,否則結束2.依次找到頂點v的所有相鄰頂點v,如果visitedv=FALSE,訪問該頂點v,visitedv=TRUE,將v插入隊列Q3.重復1,2,.,三、廣度優(yōu)先搜索(BFS函數),50,第三節(jié)圖的遍歷,void BFSTraverse(Graph *G, char FirstVertex)int i, j; char y, VisitedMAXVERTEXNUM;VexNode *p;for (i=1; iVertexNum; i+) Visitedi = F;/ 所有結點對應的訪問位 賦初值InitQueue(GQ); / 清空循環(huán)隊列i = GetVexNodeNo(G, FirstVertex);Visitedi = T;cout AdjListi.Vertex;EnQueue(GQ, G-AdjListi.Vertex); / 新搜索到的結點插入隊列while (QueueEmpty(GQ) != ERROR) DeQueue(GQ, ,.,三、廣度優(yōu)先搜索(舉例),第三節(jié)圖的遍歷,BFS為0,1,4,5,2,3 BFS為v1,v2,v3,v4, v5,v6,v7,v8,.,算法分析 DFS遍歷:實質是對每個頂點查找鄰接點的過程,取決于存儲結構。當圖有e條邊,其時間復雜度為O(e),圖的每個頂點至多調用一次DFS函數(遞歸過程)。 總時間復雜度為O(n+e) 。 BFS遍歷: 與DFS遍歷唯一區(qū)別是鄰接點搜索次序不同. 總時間復雜度為O(n+e) 。,第三節(jié)圖的遍歷,.,練 習,例按順序輸入頂點對:(1,2),(1,6),(2,6),(1,4),(6,4),(1,3),(3,4),(6,5),(4,5),(1,5),(3,5), 根據建立無向圖的鄰接表算法,畫出相應的鄰接表。并寫出在該鄰接表上,從頂點4開始搜索所得的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列。,.,一、無向圖的連通性,54,第四節(jié)圖的連通性問題,如果無向圖中,存在不連通的頂點,則該圖稱為非連通圖 非連通圖 連通圖,.,二、無向圖的連通分量,55,第四節(jié)圖的連通性問題,非連通圖的極大連通子圖叫做連通分量若從無向圖的每一個連通分量中的一個頂點出發(fā)進行DFS或BFS遍歷,可求得無向圖的所有連通分量的生成樹(DFS或BFS生成樹)所有連通分量的生成樹組成了非連通圖的生成森林,.,二、無向圖的生成樹,56,第四節(jié)圖的連通性問題,由DFS遍歷,求得連通分量稱為DFS生成樹由BFS遍歷,求得連通分量稱為BFS生成樹,BFS生成樹,DFS生成樹,.,三、最小生成樹,57,第四節(jié)圖的連通性問題,如果無向圖中,邊上有權值,則稱該無向圖為無向網如果無向網中的每個頂點都相通,稱為連通網最小生成樹(Minimum Cost Spanning Tree)是代價最小的連通網的生成樹,即該生成樹上的邊的權值和最小,.,三、最小生成樹(準則),58,第四節(jié)圖的連通性問題,必須使用且僅使用連通網中的n-1條邊來聯結網絡中的n個頂點;不能使用產生回路的邊;各邊上的權值的總和達到最小。,.,四、普里姆(Prim)算法生成最小生成樹,59,第四節(jié)圖的連通性問題,假設N=(V,E)是連通網TE是N上最小生成樹中邊的集合1.U=u0,(u0V), TE=2.在所有uU,vV-U的邊(u,v)E中找一條代價最小的邊(u,v0)并入集合TE,同時v0并入U3.重復2,直到U=V,.,四、普里姆(Prim)算法舉例,60,第四節(jié)圖的連通性問題,原圖 (a) (b),(c) (d) (e) (f),.,P174頁,圖7.16,.,算法7.9,void MiniSpanTree_PRIM(MGraph G, VertexType u) / 用普里姆算法從第u個頂點出發(fā)構造網G的最小生成樹T,輸出T的各條邊,記錄從頂點集U到VU的代價最小的邊的輔助數組定義 struct VertexType adjvex; VRType lowcost; closedgeMAX_VERTEX_NUM; int i,j,k; k = LocateVex ( G, u ); for ( j=0; j0, viV-U printf(closedgek.adjvex, G.vexsk); / 輸出生成樹的邊 closedgek.lowcost = 0; / 第k頂點并入U集 for (j=0; jG.vexnum; +j) if (G.arcskj.adj Vertexi = StartVexChar) StartVex = i; break;for (i=1; iVertexNum; i+) Pathi0 = 0; / 順序表的0位置,存放順序表(路徑)的長度 Desti = INFINITY;/ 所有頂點到開始頂點之間的距離初值設為無窮大 if (G-AdjMatrixStartVexi AdjMatrixStartVexi; Pathi1 = G-VertexStartVex; Pathi2 = G-Vertexi; Pathi0 = 2; Finali = F;,76,.,三、Dijkstra算法代碼,第五節(jié)最短路徑,DestStartVex = 0; / 初始化,開始頂點屬于S集(已處理過的結點)FinalStartVex = T;for (i=1; iVertexNum; i+) MinDest = INFINITY; for (j=1; jVertexNum; j+) / 找未處理頂點中到開始頂點最近的頂點 if (Finalj = F) if (Destj VertexNum; j+) / 更新當前最短路徑及距離 if(Finalj=F) ,77,.,一、有向無環(huán)圖(DAG),第六節(jié)有向無環(huán)圖及其應用,有向無環(huán)圖(DAG:Directed Acycline Graph)是圖中無環(huán)的有向圖,DAG,非DAG,78,.,一、有向無環(huán)圖(DAG),第六節(jié)有向無環(huán)圖及其應用,有向圖中,可以用深度優(yōu)先搜索(DFS),找出是否存在環(huán)從某個頂點v出發(fā),進行DFS,如果存在一條從頂點u到v的回邊,則有向圖中存在環(huán)DFS: 0,1,2,4,3,非DAG,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應用,1.偏序若集合X上的關系R是:.自反的:x R x.反對稱的:x R y = y R x.傳遞的:xRy & yRz = xRz 則稱R是集合X上的偏序關系,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應用,2.全序設關系R是集合X上的偏序,如果對每個x,yX,必有xRy或者yRx,則稱R是X上的全序關系偏序指集合中僅有部分成員之間可比較全序指集合中全體成員之間均可比較,81,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應用,3.拓撲有序右圖是一個偏序關系,因為1,3沒有先后關系如果人為地增加1,3先后關系,如1先于3,則右圖變?yōu)槿颍?稱為拓撲有序,.,二、拓撲排序,第六節(jié)有向無環(huán)圖及其應用,4.拓撲排序由偏序定義得到的拓撲有序的操作稱拓撲排序算法:.在有向圖中選一個沒有前驅的頂點且輸出之.從圖中刪除該頂點和所有以它為尾的弧 重復兩步,直到所有頂點輸出為止,83,.,第六節(jié)有向無環(huán)圖及其應用,算法7.12:Status ToplogicalSort(ALGraph G) /ToplogicalSort() functionFindInDegree(G,indegree); /Find indegree of node0.vexnum-1InitStack(S);for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push(S,k);/end of for/end of whileif (countG.vexnum) return (ERROR);else return (OK);/end of ToptlogicalSort() function,.,二、拓撲排序(舉例),第六節(jié)有向無環(huán)圖及其應用,原圖,輸出0之后,輸出0,1之后,輸出0,1,3之后,4,最后輸出拓撲排序結果:0,1,3,2,4,輸出0,1,3,2之后,.,三、AOV-網,第六節(jié)有向無環(huán)圖及其應用,如果用有向圖的頂點表示活動,用弧表示活動間的優(yōu)先關系,則稱該有向圖為頂點表示活動的網AOV(Activity On Vertex Network)AOV一定是DAG,即圖中不存在環(huán),因為存在環(huán)意味著某項活動應以自己為先決條件,86,.,三、AOV-網(舉例),第六節(jié)有向無環(huán)圖及其應用,課程代號 課程名稱 先修課程C1 高等數學C2 程序設計基礎C3 離散數學 C1, C2 C4 數據結構 C3, C2C5 高級語言程序設計 C2C6 編譯方法 C5, C4C7 操作系統 C4, C9C8 普通物理 C1C9 計算機原理 C8拓撲排序結果為 C1 , C2 , C3 , C4 , C5 , C6, C8 , C9 , C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6,87,.,四、AOE-網,第六節(jié)有向無環(huán)圖及其應用,如果用有向圖的頂點表示事件,用弧表示活動,則稱該有向圖為邊表示活動的網AOE(Activity On Edge)AOE同樣是DAGAOE包括估算工程的完成時間,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,求工程的完成時間是AOE的一個應用在工程問題中,需要研究的問題有:.完成整個工程至少需要多少時間?.哪些活動是影響工程進度的關鍵?,89,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,1.關鍵路徑工程問題的AOE網中,從工程開始(頂點)到工程結束(頂點)之間路徑長度最長的路徑叫關鍵路徑提前完成關鍵路徑上的活動,工程進度會加快提前完成非關鍵路徑上的活動,對工程無幫助,90,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,2.關鍵活動關鍵路徑上的所有活動稱為關鍵活動找到工程AOE中的所有關鍵活動,即找到了關鍵路徑,91,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,3.關鍵活動有關的量e(i):活動ai最早開始時間l(i):活動ai最遲開始時間l(i)-e(i):活動ai開始時間余量如果l(i)=e(i),則稱活動ai為關鍵活動,92,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,3.關鍵活動有關的量ve(j):事件vj最早開始時間vl(j):事件vj最遲開始時間e(i)=ve(j)l(j)=vl(k)-dut() dut()為活動ai的持續(xù)時間,93,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,3.關鍵活動有關的量從ve(0)=0開始向前遞推 ve(j)=Maxve(i)+dut() T,T是所有以第j個頂點為頭的弧的集合從vl(n-1)=ve(n-1)起向后遞推 vl(i)=Minvl(j)-dut() S,S是所有以第i個頂點為尾的弧的集合,94,.,五、關鍵路徑,第六節(jié)有向無環(huán)圖及其應用,4.求關鍵活動算法從始點v0出發(fā),令ve0=0,按拓撲有序求vej從終點vn-1出發(fā),令vln-1=ven-1,按逆拓撲有序求vli根據各頂點的ve和vl值,求每條弧(活動)ai的最早開始時間eai和最遲開始時間lai如果eai=lai,則ai為關鍵活動,95,.,五、關鍵路徑(舉例),第六節(jié)有向無環(huán)圖及其應用,ve(j)=Maxve(i)+dut() vl(i)=Minvl(j)-dut()e(i)=ve(j) l(j)=vl(k)-dut()拓撲有序0,1,3,2,4,- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- 深圳大學 數據結構 2017 演示 文檔
裝配圖網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
鏈接地址:http://appdesigncorp.com/p-359907.html