數(shù)據(jù)結(jié)構(gòu)第07章圖.ppt

第七章圖,本章介紹另一種非線性數(shù)據(jù)結(jié)構(gòu)圖圖：是一種多對多的結(jié)構(gòu)關(guān)系，每個元素可以有零個或多個直接前趨；零個或多個直接后繼；,第七章圖7.1圖的概念7.2圖的存儲結(jié)構(gòu)7.3圖的遍歷7.4生成樹7.5最短路徑7.6拓撲排序,第七章圖,學習要點1熟悉圖的各種存儲結(jié)構(gòu)及其構(gòu)造算法，了解實際問題的求解效率與采用何種存儲結(jié)構(gòu)和算法有密切聯(lián)系；2熟練掌握圖的兩種遍歷：深度優(yōu)先遍歷和廣度優(yōu)先遍歷的算法。在學習中應(yīng)注意圖的遍歷算法與樹的遍歷算法之間的類似和差異。樹的先根遍歷是一種深度優(yōu)先搜索策略，樹的層次遍歷是一種廣度優(yōu)先搜索策略3理解各種圖的算法；,第七章圖,7.1圖的基本概念,一圖的概念圖的定義圖G由兩個集合構(gòu)成，記作G=其中V是頂點的非空有限集合，E是邊的有限集合，其中邊是頂點的無序?qū)蛴行驅(qū)稀?G1=V=v0,v1,v2,v3,v4E=(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4),G1圖示,無序?qū)?vi,vj)：用連接頂點vi、vj的線段表示，稱為無向邊；,例,G2圖示,有序?qū)Γ河靡詖i起點、以vj為終點的有向線段表示，稱為有向邊或弧；稱vi為弧尾，vj為弧頭,無向圖：在圖G中，若所有邊是無向邊，則稱G為無向圖；有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖；混和圖：在圖G中，既有無向邊也有有向邊，則稱G為混合圖；,7.1圖的基本概念,G2=V=v0v1,v2,v3E=,圖的應(yīng)用舉例例1交通圖（公路、鐵路）頂點：地點邊：連接地點的公路交通圖中的有單行道雙行道，分別用有向邊、無向邊表示；例2電路圖頂點：元件邊：連接元件之間的線路例3通訊線路圖頂點：地點邊：地點間的連線例4各種流程圖如產(chǎn)品的生產(chǎn)流程圖頂點：工序邊：各道工序之間的順序關(guān)系,7.1圖的基本概念,1鄰接點及關(guān)聯(lián)邊鄰接點：邊的兩個頂點,v、u互為鄰接點關(guān)聯(lián)邊：若邊e=(v,u),則稱頂點v、u關(guān)聯(lián)邊e2頂點的度、入度、出度在無向圖中：頂點V的度=與V相關(guān)聯(lián)的邊的數(shù)目在有向圖中：頂點V的出度=以V為起點有向邊數(shù)頂點V的入度=以V為終點有向邊數(shù)頂點V的度=V的出度+V的入度設(shè)圖G的頂點數(shù)為n，邊數(shù)為e圖的所有頂點的度數(shù)和=2*e（每條邊對圖的所有頂點的度數(shù)和“貢獻”2度）,e,圖的基本術(shù)語,7.1圖的基本概念,完全圖、權(quán)、網(wǎng)有向完全圖具有n(n-1)條弧的n個頂點的有向圖稱為無向完全圖有n(n-1)/2條邊的n個頂點的無向圖稱為權(quán)與圖的邊或弧相關(guān)的數(shù)叫網(wǎng)帶權(quán)的圖叫,7.1圖的基本概念,4路徑、回路路徑路徑是頂點的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E或E,(1arcsjiw;,容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊（弧）、找頂點的鄰接點等等。n個頂點需要n*n個單元存儲邊(弧);空間效率為O(n2)。對稀疏圖而言尤其浪費空間。,鄰接矩陣法優(yōu)點：,鄰接矩陣法缺點：,注：用兩個數(shù)組分別存儲頂點表和鄰接矩陣#defineINFINITYINT_MAX/最大值#defineMAX_VERTEX_NUM20/假設(shè)的最大頂點數(shù)typedefenumDG,DN,AG,ANGraphKind;/有向/無向圖，有向/無向網(wǎng)typedefstructArcCell/?。ㄟ叄┙Y(jié)點的定義VRTypeadj;/頂點間關(guān)系，無權(quán)圖取1或0；有權(quán)圖取權(quán)值類型InfoType*info;/該弧相關(guān)信息的指針ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstruct/圖的定義VertexTypevexsMAX_VERTEX_NUM;/頂點表，用一維向量即可AdjMatrixarcs;/鄰接矩陣intVernum,arcnum;/頂點總數(shù)，?。ㄟ叄┛倲?shù)GraphKindkind;/圖的種類標志Mgraph;,圖的鄰接矩陣存儲表示（參見教材P161）,對于n個頂點的圖或網(wǎng)，空間效率=O(n2),StatusCreateUDN(Mgraph/CreateUDN,例：用鄰接矩陣生成無向網(wǎng)的算法（參見教材P162）,對于n個頂點e條弧的網(wǎng)，建網(wǎng)時間效率=O(n2+n+e*n),鄰接表(AdjacencyList),在鄰接表中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點vi的邊。每個結(jié)點由三個域組成：,鄰接點域,指示與頂點vi鄰接的點在圖中的位置,鏈域,指示下一條邊或弧的結(jié)點,數(shù)據(jù)域,存儲與邊或弧相關(guān)的信息，如權(quán)值，無權(quán)圖一般不用,每個單鏈表附設(shè)一個頭結(jié)點。在表頭結(jié)點中，除了設(shè)有鏈域指向鏈表中第一個結(jié)點之外，還設(shè)有存儲頂點vi的名或其它有關(guān)信息的數(shù)據(jù)域。,數(shù)據(jù)域,鏈域,表頭結(jié)點可以鏈相接，通常以順序結(jié)構(gòu)的形式存儲，以便隨機訪問任一頂點的鏈表。,存放與該頂點相關(guān)的信息,指示第一條依附于該頂點的邊的指針,圖的鄰接表存儲表示,#defineMAX_VERTEX_NUM20typedefstructArcNodeintadjvex;/該弧所指向的頂點的位置structArcNode*nextarc;/指向下一條弧的指針I(yè)nfoType*info;/該弧相關(guān)信息的指針ArcNode;typedefstructVNodeVertexTypedata;/頂點信息ArcNode*firstarc;/指向第一條依附該頂點的弧VNode,AdjListMAX_VERTEX_NUM;typedefstructAdjListvertices;intvexnum,arcnum;/圖的當前頂點數(shù)和弧數(shù)intkind;/圖的種類標志ALGraph;,無向圖的鄰接表,在無向圖的鄰接表中，頂點vi的度恰為第i個鏈表中的結(jié)點數(shù)。,有向圖的鄰接表(出邊表),有向圖中對每個結(jié)點建立以Vi為尾的弧的單鏈表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為起點的?。河镁€性鏈表存儲,有向圖的逆鄰接表(入邊表),有向圖中對每個結(jié)點建立以Vi為頭的弧的單鏈表頂點：用一維數(shù)組存儲（按編號順序）以同一頂點為終點的弧：用線性鏈表存儲,在有向圖中，第i個鏈表中的結(jié)點個數(shù)只是頂點vi的出度，為求入度，必須遍歷整個鄰接表。在所有鏈表中其鄰接點域的值為i的結(jié)點的個數(shù)是頂點vi的入度。在有向圖的鄰接表中，第i個邊鏈表鏈接的邊都是頂點i發(fā)出的邊。也叫做出邊表。在有向圖的逆鄰接表中，第i個邊鏈表鏈接的邊都是進入頂點i的邊。也叫做入邊表。,該結(jié)點表示邊（ViVj）,其中的2是Vj在一維數(shù)組中的位置,鄰接表,特點無向圖中頂點Vi的度為第i個單鏈表中的結(jié)點數(shù)有向圖中頂點Vi的出度為第i個單鏈表中的結(jié)點個數(shù)頂點Vi的入度為整個單鏈表中鄰接點域值是i的結(jié)點個數(shù)判定兩頂點v,u是否鄰接：要看v對應(yīng)線性鏈表中有無對應(yīng)的結(jié)點u在G中增減邊：要在兩個單鏈表插入、刪除結(jié)點；若無向圖中有n個頂點、e條邊，則它的鄰接表需n個頭結(jié)點和2e個表結(jié)點?？梢姡珿占用存儲空間與G的頂點數(shù)、邊數(shù)均有關(guān)；適用于邊稀疏的圖。,帶權(quán)圖的鄰接表,多一個info域,相反，已知某網(wǎng)的鄰接（出邊）表，可以畫出該網(wǎng)絡(luò)。,80,64,1,2,5,當鄰接表的存儲結(jié)構(gòu)形成后，圖便唯一確定！,鄰接表的缺點：,鄰接表的優(yōu)點：,空間效率高；容易尋找頂點的鄰接點；,判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。,討論：鄰接表與鄰接矩陣有什么異同之處？,1.聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。2.區(qū)別：對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。3.用途：鄰接矩陣多用于稠密圖的存儲（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲（en2),三、十字鏈表（自學）（適用于有向圖）四、鄰接多重表（自學）（適用于無向圖）,有向圖的十字鏈表表示法,無向圖的鄰接多重表表示法,7.3圖的遍歷,從圖中某個頂點出發(fā)游歷圖，訪遍圖中其余頂點，并且使圖中的每個頂點僅被訪問一次。這一過程就稱為圖的遍歷。圖的遍歷比樹的遍歷要復(fù)雜得多。因為圖的任一頂點都可能和其余的頂點相鄰接；因此在訪問了某個頂點后，可能沿著某條路徑搜索后，又回到該頂點上。為了避免同一頂點被訪問多次，在遍歷圖的過程中，必須記下每個已訪問過的頂點。,為了避免重復(fù)訪問，可設(shè)置一個標志頂點是否被訪問過的輔助數(shù)組visited0.n-1，它的初始狀態(tài)為0，在圖的遍歷過程中，一旦某一個頂點i被訪問，就立即讓visitedi為1，防止它被多次訪問。,通常有兩條遍歷圖的路徑：深度優(yōu)先搜索、廣度優(yōu)先搜索,深度優(yōu)先搜索DFS(Depth_FirstSearch),算法思想：假設(shè)初始狀態(tài)是圖中所有頂點未曾被訪問，則可從圖中某個頂點V0出發(fā)，訪問此頂點，然后依次從V0的各個未被訪問的鄰接點出發(fā)深度優(yōu)先搜索遍歷圖，直至圖中所有和V0有路徑相通的頂點都被訪問到，若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。,圖的深度優(yōu)先搜索類似于樹的前序遍歷,深度優(yōu)先搜索的示例,由上得到頂點訪問序列為：v1、v2、v4、v8、v5、v3、v6、v7,顯然這是一個遞歸的過程，為了在遍歷過程中便于區(qū)分頂點是否已被訪問，需附設(shè)訪問數(shù)組visited0.n-1，數(shù)組元素的初始值為false；在遍歷過程中，一旦某一個頂點i被訪問，則置visitedi為true。,例2：,v2v1v3v5,DFS結(jié)果,v4v6,起點,深度優(yōu)先搜索（遍歷）步驟：,詳細歸納：在訪問圖中某一起始頂點v后，由v出發(fā)，訪問它的任一鄰接頂點w1；再從w1出發(fā)，訪問與w1鄰接但還未被訪問過的頂點w2；然后再從w2出發(fā)，進行類似的訪問，如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點u為止。,簡單歸納：訪問起始點v;若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；若當前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。,接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問；如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。,BooleanvisitedMAX;/訪問標志數(shù)組Status(*VisitFunc)(intv);/函數(shù)變量/以上兩個變量都是全局變量voidDFSTraverse(GraphG,Status(*Visit)(intv)/對圖G作深度優(yōu)先遍歷。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSE;/訪問標志數(shù)組初始化for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/對尚未訪問的頂點調(diào)用DFS,圖的深度優(yōu)先搜索算法,voidDFS(GraphG,intv)/從第v個頂點出發(fā)遞歸地深度優(yōu)先遍歷圖G。visitedv=TRUE;/訪問標記置為trueVisitFunc(v);/訪問第v個頂點for(w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/對v的尚未訪問的鄰接頂點w/遞歸調(diào)用DFS,算法時間復(fù)雜度分析,從上述算法可知，在遍歷過程中，對圖中每個頂點至多調(diào)用一次DFS函數(shù)；因為一旦某個頂點被標志成已被訪問，就不再從它出發(fā)進行搜索。因此，對圖的遍歷實際上是對每個頂點查找其鄰接點的過程，耗費的時間取決于所用的存儲結(jié)構(gòu)。,如果用鄰接表表示圖，沿Firstoutlink鏈可以找到某個頂點v的所有鄰接頂點w。由于總共有2e個邊結(jié)點，所以掃描邊的時間為O(e)。而且對所有頂點遞歸訪問1次，所以遍歷圖的時間復(fù)雜性為O(n+e)。如果用鄰接矩陣表示圖，則查找每一個頂點的所有的邊，所需時間為O(n)，則遍歷圖中所有的頂點所需的時間為O(n2)。,廣度優(yōu)先搜索BFS(Breadth_FirstSearch),圖的廣度優(yōu)先搜索類似于樹的按層次遍歷過程,算法思想：從圖中的某個頂點V0出發(fā)，并在訪問此頂點之后依次訪問V0的所有未被訪問過的鄰接點，之后按這些頂點被訪問的先后次序依次訪問它們的鄰接點，直至圖中所有和V0有路徑相通的頂點都被訪問到。若此時圖中尚有頂點未被訪問,則另選圖中一個未曾被訪問的頂點作起始點，重復(fù)上述過程，直至圖中所有頂點都被訪問到為止。,廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。,廣度優(yōu)先搜索的示例,由上得到頂點訪問序列為：v1、v2、v3、v4、v5、v6、v7、v8,為了實現(xiàn)對圖的逐層訪問，需要在算法中使用一個隊列，以記憶正在訪問的這一層和上一層的頂點，以便于向下一層訪問。為避免重復(fù)訪問，還需要一個輔助數(shù)組visited0.n-1，給被訪問過的頂點加標記。,例2：,v3,BFS結(jié)果,v4v5,v2v1v6,v9v8v7,起點,廣度優(yōu)先搜索（遍歷）步驟：,簡單歸納：在訪問了起始點v之后，依次訪問v的鄰接點；然后再依次訪問這些頂點中未被訪問過的鄰接點；直到所有頂點都被訪問過為止。,廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。,圖的廣度優(yōu)先搜索算法,voidBFSTraverse(GraphG,Status(*Visit)(intv)/按廣度優(yōu)先非遞歸遍歷圖G。/使用輔助隊列Q和訪問標志數(shù)組visited。for(v=0;vG.vexnum;+v)visitedv=FALSE;InitQueue(Q);/置空的輔助隊列Qfor(v=0;vG.vexnum;+v)if(!visitedv)/若頂點v尚未被訪問EnQueue(Q,v);/頂點v入隊列while(!QueueEmpty(Q)DeQueue(Q,u);/隊頭元素出隊并置為uvisitedu=TRUE;Visit(u);/訪問u,for(w=FirstAdjVex(G,u);w!=0;w=NextAdjVex(G,u,w)if(!visitedw)/u的尚未訪問的鄰接點w入隊visitedw=TRUE;Visit(w);/訪問wEnQueue(Q,w);/if/while/if/BFSTraverse,如果使用鄰接表表示圖，則循環(huán)的總時間代價為d0+d1+dn-1=O(e)，其中的di是頂點i的度。如果使用鄰接矩陣，則對于每一個被訪問過的頂點，循環(huán)要檢測矩陣中的n個元素，總的時間代價為O(n2)。,算法時間復(fù)雜度分析,7.4圖的連通性,當無向圖為非連通圖時，從圖中某一頂點出發(fā)，利用深度優(yōu)先搜索算法或廣度優(yōu)先搜索算法不可能遍歷到圖中的所有頂點，只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。若從無向圖的每一個連通分量中的一個頂點出發(fā)進行遍歷，可求得無向圖的所有連通分量。,例,圖G4,G4的三個連通分量,在以上算法中，需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發(fā)遍歷圖，可求得圖的另一個連通分量。,對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。,最小生成樹(minimumcostspanningtree),使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n個頂點的連通網(wǎng)絡(luò)的生成樹有n個頂點、n-1條邊。,假設(shè)要在n個城市之間建立通信聯(lián)絡(luò)網(wǎng)，則連通n個城市只需要n-1條線路。問題是：如何在最節(jié)省經(jīng)費的前提下建立這個通信網(wǎng)。,解決辦法：在每兩個城市之間設(shè)置一條線路，n個城市之間最多可設(shè)置n(n-1)/2條線路；要在這些可能的線路中選擇n-1條，以使總的耗費最少。,可以用連通網(wǎng)來表示n個城市以及n個城市間可能設(shè)置的通信線路，其中網(wǎng)的頂點表示城市，邊表示兩城市之間的線路，賦予邊的權(quán)值表示相應(yīng)的代價。,對于n個頂點的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹都可以是一個通信網(wǎng)。從這些生成棵中選擇權(quán)值最小的，就滿足建立耗費最小的通信網(wǎng)的要求了。這個問題就是構(gòu)造連通網(wǎng)的最小代價生成樹問題，簡稱為最小生成樹問題。,構(gòu)造最小生成樹的準則,1、必須只使用該網(wǎng)絡(luò)中的邊來構(gòu)造最小生成樹；2、必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)中的n個頂點；3、不能使用產(chǎn)生回路的邊。,構(gòu)造最小生成樹可以有多種算法，大多數(shù)算法都利用了以下MST性質(zhì)：假設(shè)N=(V,E)是一個連通網(wǎng)，U是頂點集V的一個非空子集。若(u,v)是一條具有最小權(quán)值（代價）的邊，其中uU,vV-U，則必存在一棵包含邊(u,v)的最小生成樹。,普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法是兩個利用以上MST性質(zhì)構(gòu)造最小生成樹的算法。,普里姆算法(Prim),可取圖中任意一個頂點v作為生成樹的根，之后若要往生成樹上添加頂點w，則在頂點v和頂點w之間必定存在一條邊，并且該邊的權(quán)值在所有連通頂點v和w之間的邊中取值最小。一般情況下，假設(shè)n個頂點分成兩個集合：U（包含已落在生成樹上的結(jié)點）和V-U（尚未落在生成樹上的頂點），則在所有連通U中頂點和V-U中頂點的邊中選取權(quán)值最小的邊。,普里姆算法的基本思想：從連通網(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中為止。,為了實現(xiàn)以上算法，還需要附設(shè)一個輔助數(shù)組closedge0.n-1，以記錄從U到V-U具有最小代價的邊。,structVertexTypeadjvex;/存儲該邊依附的在U中的頂點VRTypelowcost;/存儲該邊上的權(quán)closedgeMAX_VERTEX_NUM;,普里姆算法構(gòu)造最小生成樹的過程,起點,7,13,9,5,10,起點,例,算法時間復(fù)雜度分析,從上述算法可知，若網(wǎng)中有n個頂點，則第一次進行初始化的循環(huán)語句的頻度為n，第二次循環(huán)語句包含兩個內(nèi)循環(huán)：一是在closedgev.lowcost中求最小值，其頻度為n-1；二是重新選擇具有最小代價的邊,其頻度為n。由此可知，普里姆算法的時間復(fù)雜度為O(n2),與網(wǎng)中的邊數(shù)無關(guān)，適用于求邊稠密的網(wǎng)的最小生成樹。,克魯斯卡爾算法(Kruskal),為使生成樹上邊的權(quán)值之和最小，顯然，其中每一條邊的權(quán)值應(yīng)該盡可能地小?？唆斔箍査惴ǖ淖龇ň褪牵合葮?gòu)造一個只含n個頂點的子圖SG，然后從權(quán)值最小的邊開始，若它的添加不使SG中產(chǎn)生回路，則在SG上加上這條邊，如此重復(fù)，直至加上n-1條邊為止。,算法的基本思想：設(shè)有一個有n個頂點的連通網(wǎng)絡(luò)N=V,E,最初先構(gòu)造一個只有n個頂點，沒有邊的非連通圖T=V,圖中每個頂點自成一個連通分量。當在E中選到一條具有最小權(quán)值的邊時,若該邊的兩個頂點落在不同的連通分量上，則將此邊加入到T中；否則將此邊舍去，重新選擇一條權(quán)值代價最小的邊。如此重復(fù)下去，直到所有頂點在同一個連通分量上為止。,克魯斯卡算法構(gòu)造最小生成樹的過程,7,13,9,5,10,例,算法時間復(fù)雜度分析,上述算法至多對e條邊各掃描一次，假若以“堆”來存儲網(wǎng)中的邊，則每次選擇最小代價的邊僅需O(loge)的時間。而且生成樹T的每個連通分量可看成是一個等價類，則構(gòu)造T加入新的邊的過程類似于求等價類的過程，則可用MFSet類型來描述T，使構(gòu)造T的過程僅需O(eloge)的時間。因此，克魯斯卡爾算法的時間復(fù)雜度為O(n2)，適用于求邊稀疏的網(wǎng)的最小生成樹。,7.5有向無環(huán)圖及其應(yīng)用,一個無環(huán)的有向圖稱做有向無環(huán)圖，簡稱DAG圖。有向無環(huán)圖是描述含有公共子式的表達式的有效工具。,如：表達式(a+b)*(b*(c+d)+(c+d)*e)(c+d)*e)中，對于一些相同的子表達式如(c+d)、(c+d)*e，可以利用有向無環(huán)圖，實現(xiàn)對相同子式的共享，從而節(jié)省存儲空間。,有向無環(huán)圖也是描述一項工程或系統(tǒng)的進行過程的有效工具。,通常把工程分成若干個稱作活動的子工程，而這些子工程之間通常受著一定條件的約束,如其中某些子工程的開始必須在另一些子工程完成之后。對整個工程和系統(tǒng)，主要考慮以下兩個問題：一是工程能否順利進行；二是估算整個工程完成所必須的最短時間。對應(yīng)于有向圖，即為進行拓撲排序和關(guān)鍵路徑的操作。,拓撲排序,例如，計算機專業(yè)學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學習。,C1高等數(shù)學C2程序設(shè)計基礎(chǔ)C3離散數(shù)學C1,C2C4數(shù)據(jù)結(jié)構(gòu)C3,C2C5高級語言程序設(shè)計C2C6編譯方法C5,C4C7操作系統(tǒng)C4,C9C8普通物理C1C9計算機原理C8,課程代號,課程名稱,先修課程,表示課程之間優(yōu)先關(guān)系的有向圖,由上可知，可用有向圖表示一個工程。,在這種有向圖中，用頂點表示活動，用有向邊表示活動。Vi必須先于活動Vj進行。這種有向圖叫做頂點表示活動的AOV網(wǎng)絡(luò)(ActivityOnVertices)。,因此，對給定的AOV網(wǎng)絡(luò)，必須先判斷它是否存在有向環(huán)。,在AOV網(wǎng)絡(luò)中，如果活動Vi必須在活動Vj之前進行，則存在有向邊，AOV網(wǎng)絡(luò)中不能出現(xiàn)有向回路，即有向環(huán)。在AOV網(wǎng)絡(luò)中如果出現(xiàn)了有向環(huán)，則意味著某項活動應(yīng)以自己作為先決條件。,即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。這種構(gòu)造AOV網(wǎng)絡(luò)全部頂點的拓撲有序序列的運算就叫做拓撲排序。,檢測有向環(huán)的一種方法是對AOV網(wǎng)絡(luò)構(gòu)造它的拓撲有序序列。,如果通過拓撲排序能將AOV網(wǎng)絡(luò)的所有頂點都排入一個拓撲有序的序列中，則該AOV網(wǎng)絡(luò)中必定不會出現(xiàn)有向環(huán)；相反，如果得不到滿足要求的拓撲有序序列，則說明AOV網(wǎng)絡(luò)中存在有向環(huán)，此AOV網(wǎng)絡(luò)所代表的工程是不可行的。,例如，對學生選課工程圖進行拓撲排序，得到的拓撲有序序列為C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6,進行拓撲排序的方法,1、在AOV網(wǎng)絡(luò)中選一個沒有直接前驅(qū)的頂點，并輸出之;2、從圖中刪去該頂點，以及所有以它為尾的弧;3、重復(fù)以上兩步,直到1）全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；2）圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點了。這時AOV網(wǎng)絡(luò)中必定存在有向環(huán)。,拓撲排序過程的示例,(h)全部結(jié)點已輸出，拓撲排序完成,由上得到的拓撲有序序列為C4,C0,C3,C2,C1,C5。它滿足圖中給出的所有前驅(qū)和后繼關(guān)系，對于本來沒有這種關(guān)系的頂點，如C4和C2，也排出了先后次序關(guān)系。,拓撲排序的算法實現(xiàn),可以用鄰接表作有向圖的存儲結(jié)構(gòu)，且在頭結(jié)點中增加一個存放頂點入度的數(shù)組(indegree)。入度為0的頂點即為沒有前驅(qū)的頂點，刪除頂點及以它為尾的弧的操作，可用弧頭頂點的入度減1的方法來實現(xiàn)。,另外，使用一個存放入度為零的頂點的鏈式棧，供選擇和輸出無前驅(qū)的頂點。只要出現(xiàn)入度為零的頂點，就將它加入棧中。,(1)建立入度為零的頂點棧;(2)當入度為零的頂點棧不空時,重復(fù)執(zhí)行：從頂點棧中退出一個頂點,并輸出之;從AOV網(wǎng)絡(luò)中刪去這個頂點和它發(fā)出的邊,邊的終頂點入度減一;如果邊的終頂點入度減至0,則該頂點進入度為零的頂點棧;(3)如果輸出頂點個數(shù)少于AOV網(wǎng)絡(luò)的頂點個數(shù),則報告網(wǎng)絡(luò)中存在有向環(huán)。,使用這種棧的拓撲排序算法可以描述如下：,拓撲序列：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)的拓撲序列不是唯一的,算法實現(xiàn)以鄰接表作存儲結(jié)構(gòu)把鄰接表中所有入度為0的頂點進棧棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧重復(fù)上述操作直至棧空為止。若?？諘r輸出的頂點個數(shù)不是n，則有向圖有環(huán)；否則，拓撲排序完畢,鄰接表結(jié)點：typedefstructnodeintvex;/頂點域structnode*next;/鏈域JD;,表頭結(jié)點：typedefstructtnodeintin;/入度域structnode*link;/鏈域TD;TDgM;/g0不用,算法分析,建鄰接表：T(n)=O(e)搜索入度為0的頂點的時間：T(n)=O(n)拓撲排序：T(n)=O(n+e),Ch6_4.c,算法描述,Ch6_40.c,1,6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：6,輸出序列：61,輸出序列：61,輸出序列：61,4,輸出序列：61,4,輸出序列：61,4,輸出序列：61,4,3,輸出序列：61,4,3,輸出序列：61,4,3,輸出序列：61,4,3,輸出序列：61,4,3,輸出序列：613,4,3,輸出序列：613,4,輸出序列：613,4,輸出序列：613,4,輸出序列：613,4,2,輸出序列：613,4,2,輸出序列：613,4,2,輸出序列：6132,4,2,輸出序列：6132,4,輸出序列：61324,4,輸出序列：61324,輸出序列：61324,5,輸出序列：61324,5,輸出序列：613245,5,輸出序列：613245,分析此拓撲排序算法可知，如果AOV網(wǎng)絡(luò)有n個頂點，e條邊，在拓撲排序的過程中，搜索入度為零的頂點，建立鏈式棧所需要的時間是O(n)。在正常的情況下，有向圖有n個頂點，每個頂點進一次棧，出一次棧，共輸出n次。頂點入度減一的運算共執(zhí)行了e次。所以總的時間復(fù)雜度為O(n+e)。,算法時間復(fù)雜度分析,關(guān)鍵路徑,如果在帶權(quán)有向無環(huán)圖中用有向邊表示一個工程中的活動(Activity)用邊上權(quán)值表示活動持續(xù)時間(Duration)用頂點表示事件(Event)則這樣的有向圖叫做用邊表示活動的網(wǎng)絡(luò)，簡稱AOE(ActivityOnEdges)網(wǎng)絡(luò)。,一個AOE網(wǎng)絡(luò),AOE網(wǎng)絡(luò)在某些工程估算方面非常有用，可以使人們了解：(1)完成整個工程至少需要多少時間(假設(shè)網(wǎng)絡(luò)中沒有環(huán))?(2)為縮短完成工程所需的時間,應(yīng)當加快哪些活動?,在AOE網(wǎng)絡(luò)中,有些活動順序進行，有些活動并行進行。從源點到各個頂點，以至從源點到匯點的有向路徑可能不止一條；這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，整個工程才算完成。,因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關(guān)鍵路徑(CriticalPath)。,要找出關(guān)鍵路徑，必須找出關(guān)鍵活動，即不按期完成就會影響整個工程完成的活動。,關(guān)鍵路徑上的所有活動都是關(guān)鍵活動。因此，只要找到了關(guān)鍵活動，就可以找到關(guān)鍵路徑。,幾個與計算關(guān)鍵活動有關(guān)的量：,事件Vi的最早可能開始時間Ve(i)是從源點V0到頂點Vi的最長路徑長度。事件Vi的最遲允許開始時間Vli是在保證匯點Vn-1在Ven-1時刻完成的前提下，事件Vi的允許的最遲開始時間。,活動ak的最早可能開始時間ek設(shè)活動ak在邊上，則ek是從源點V0到頂點Vi的最長路徑長度。因此,ek=Vei?；顒觓k的最遲允許開始時間lklk是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。lk=Vlj-dur()。其中，dur()是完成ak所需的時間。時間余量lk-ek表示活動ak的最早可能開始時間和最遲允許開始時間的時間余量。lk=ek表示活動ak是沒有時間余量的關(guān)鍵活動。,為找出關(guān)鍵活動,需要求各個活動的ek與lk，以判別是否lk=ek。為求得ek與lk，需要先求得從源點V0到各個頂點Vi的各事件的最早開始時間Vei和最遲開始時間Vli。,求最早開始時間Vej和最遲開始時間Vlj需分兩步進行：,（1）從Ve0=0開始，向前遞推,T,i=1,2,n-1,其中,T是所有以第j個頂點為頭的弧的集合。,(2)從Vln-1=Ven-1開始，反向遞推,S,i=n-2,n-3,0,其中,S是所有以第i個頂點為尾的弧的集合。,以上這兩個遞推公式的計算必須分別在拓撲有序及逆拓撲有序的前提下進行。,*設(shè)活動ak(k=1,2,e)在帶權(quán)有向邊上,它的持續(xù)時間用dut()表示，則有ek=Vei；lk=Vlj-dur()；k=1,2,e。這樣就得到計算關(guān)鍵路徑的算法。*計算關(guān)鍵路徑時，可以一邊進行拓撲排序一邊計算各頂點的Vei。為了簡化算法，假定在求關(guān)鍵路徑之前已經(jīng)對各頂點實現(xiàn)了拓撲排序，并按拓撲有序的順序?qū)Ω黜旤c重新進行了編號。算法在求Vei,i=0,1,n-1時按拓撲有序的順序計算，在求Vli,i=n-1,n-2,0時按逆拓撲有序的順序計算。,（1）輸入e條弧，建立AOV-網(wǎng)的存儲結(jié)構(gòu)；（2）從源點v1出發(fā)，令ve1=0，按拓撲有序求其余各頂點的最早發(fā)生時間vei（2=i=n）。如果得到的拓撲有序序列中頂點個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止；否則執(zhí)行步驟（3）。,求關(guān)鍵路徑的過程：,（3）從匯點vn出發(fā)，令vln=ven，按逆拓撲有序號求其余各頂點的最遲發(fā)生時間vli（n-1i1）；（4）根據(jù)各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s)。若某條弧滿足條件e(s)=l(s)，則為關(guān)鍵活動。,求關(guān)鍵路徑的示例,在拓撲排序求Vei和逆拓撲有序求Vli時,所需時間為O(n+e),求各個活動的ek和lk時所需時間為O(e),總共花費時間仍然是O(n+e)。,算法時間復(fù)雜度分析,求關(guān)鍵路徑步驟求Ve(i)求Vl(j)求e(i)求l(i)計算l(i)-e(i),V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,0,0,0,0,2,2,6,6,0,4,6,2,5,8,3,7,7,0,7,7,0,7,10,3,16,16,0,14,14,0,0,3,3,算法實現(xiàn)以鄰接表作存儲結(jié)構(gòu)從源點V1出發(fā)，令Ve1=0,按拓撲序列求各頂點的Vei從匯點Vn出發(fā)，令Vln=Ven,按逆拓撲序列求其余各頂點的Vli根據(jù)各頂點的Ve和Vl值，計算每條弧的ei和li,找出ei=li的關(guān)鍵活動,鄰接表結(jié)點：typedefstructnodeintvex;/頂點域intlength;/權(quán)值structnode*next;/鏈域JD;,表頭結(jié)點：typedefstructtnodeintvexdata;/頂點信息intin;/入度域structnode*link;/鏈域TD;TDgM;/g0不用,算法描述輸入頂點和弧信息，建立其鄰接表計算每個頂點的入度對其進行拓撲排序排序過程中求頂點的Vei將得到的拓撲序列進棧按逆拓撲序列求頂點的Vli計算每條弧的ei和li,找出ei=li的關(guān)鍵活動,Ch6_20.c,一頂點到其余各頂點,7.6.求最短路徑,兩種常見的最短路徑問題：一、單源最短路徑用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑用Floyd（弗洛伊德）算法,典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？問題抽象：在帶權(quán)有向圖中A點（源點）到達B點（終點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。,（注：最短路徑與最小生成樹不同，路徑上不一定包含n個頂點）,任意兩頂點之間,一、單源最短路徑(Dijkstra算法),目的：設(shè)一有向圖G=（V,E），已知各邊的權(quán)值，以某指定點v0為源點，求從v0到圖的其余各點的最短路徑。限定各邊上的權(quán)值大于或等于0。,例1：,源點,從FA的路徑有4條：FA：24FBA：518=23FBCA：5+7+9=21FDCA：25+12+9=36,又：從FB的最短路徑是哪條？從FC的最短路徑是哪條？,10,30,100,例2：,60,01234,50,90,70,討論：計算機如何自動求出這些最短路徑？,60,Dijkstra（迪杰斯特拉）算法,算法思想：先找出從源點v0到各終點vk的直達路徑（v0,vk），即通過一條弧到達的路徑。從這些路徑中找出一條長度最短的路徑（v0,u）,然后對其余各條路徑進行適當調(diào)整：若在圖中存在?。╱,vk），且（v0,u）+（u,vk）（v0,vk）,則以路徑（v0,u,vk）代替（v0,vk）。在調(diào)整后的各條路徑中，再找長度最短的路徑，依此類推。,總之，按路徑“長度”遞增的次序來逐步產(chǎn)生最短路徑,算法描述：,（1）設(shè)arcsnn為有向網(wǎng)的帶權(quán)鄰接矩陣，arcsij表示?。╲i，vj)的權(quán)值，S為已找到從源點v0出發(fā)的最短路徑的終點集合，它的初始狀態(tài)為v0.輔助數(shù)組Dn為各終點當前找到的最短路徑的長度，它的初始值為Diarcsv0,i/即鄰接矩陣中第v0行的權(quán)值,（2）選擇u，使得DuminDw|wV-S/w是S集之外的頂點/Du是從源點v0到S集外所有頂點的弧中最短的一條S=Su/將u加入S集,（3）對于所有不在S中的終點w，若Du+arcsu,wDw/即(v0,u)(u,w)(v0,w)則修改Dw為：DwDu+arcsu,w,（4）重復(fù)操作（2）、（3）共n-1次，由此求得從v0到各終點的最短路徑。,算法的C語言程序見教材P189；,對應(yīng)流程圖見下頁,VoidShortPath_DIJ(MgraphG,intv0,PathMatrix+i),更新v0到V-S中頂點的dist,求最短路徑長度,算法流程：,(v0,v2)+(v2,v3)(v0,v3),S之外的當前最短路徑之頂點,v0,v2,v0,v2,v4,v0,v2,v4,v3,v0,v2,v4,v3,v5,例3：,v2,v4,v3,v5,012345,Dw,012345,與最小生成樹的不同點：路徑可能是累加的！,10v0,v2,50v0,v4,v3,30v0,v4,二、所有頂點之間的最短路徑,問題的提出：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點vivj，希望求出vi與vj之間的最短路徑和最短路徑長度。解決思路：可以通過調(diào)用n次Dijkstra算法來完成，但時間復(fù)雜度為O(n3)。改進：Floyd算法（略）,圖,存儲結(jié)構(gòu),遍歷,最小生成樹,（利用DFS）,本章小結(jié),(利用DFS和BFS),最短路徑(ShortestPath),最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權(quán)值總和達到最小。問題解法邊上權(quán)值非負情形的單源最短路徑問題Dijkstra算法邊上權(quán)值為任意值的單源最短路徑問題Bellman和Ford算法所有頂點之間的最短路徑Floyd算法,邊上權(quán)值非負情形的單源最短路徑問題,問題的提法：給定一個帶權(quán)有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權(quán)值大于或等于0。為求得這些最短路徑，Dijkstra提出按路徑長度的遞增次序，逐步產(chǎn)生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。舉例說明,Dijkstra逐步求解的過程,引入一個輔助數(shù)組dist。它的每一個分量disti表示當前找到的從源點v0到終點vi的最短路徑的長度。初始狀態(tài)：若從源點v0到頂點vi有邊，則disti為該邊上的權(quán)值；若從源點v0到頂點vi沒有邊，則disti為+。一般情況下，假設(shè)S是已求得的最短路徑的終點的集合，則可證明：下一條最短路徑必然是從v0出發(fā)，中間只經(jīng)過S中的頂點便可到達的那些頂點vx(vxV-S)的路徑中的一條。每次求得一條最短路徑之后，其終點vk加入集合S，然后對所有的viV-S，修改其disti值。,Dijkstra算法可描述如下：,初始化：Sv0;distjEdge0j,j=1,2,n-1;/n為圖中頂點個數(shù)求出最短路徑的長度：distkmindisti,iV-S;SSUk;修改：distimindisti,distk+Edgeki,對于每一個iV-S;判斷：若S=V,則算法結(jié)束，否則轉(zhuǎn)。,Dijkstra算法中各輔助數(shù)組的變化,如何從表中讀取源點0到終點v的最短路徑？舉頂點4為例path4=2path2=3path3=0，反過來排列，得到路徑0,3,2,4，這就是源點0到終點4的最短路徑。,0,4,1,2,3,10,50,10,20,60,30,100,邊上權(quán)值為任意值的單源最短路徑問題,帶權(quán)有向圖D的某幾條邊或所有邊的長度可能為負值。利用Dijkstra算法，不一定能得到正確的結(jié)果。源點0到終點2的最短路徑應(yīng)是0,1,2，其長度為2，它小于算法中計算出來的dist2的值。,若設(shè)源點v=0，使用Dijkstra算法所得結(jié)果,0,1,1,5,7,-5,Bellman和Ford提出了從源點逐次繞過其它頂點，以縮短到達終點的最短路徑長度的方法。該方法有一個限制條件，即要求圖中不能包含有由帶負權(quán)值的邊組成的回路。當圖中沒有由帶負權(quán)值的邊組成的回路時，有n個頂點的圖中任意兩個頂點之間如果存在最短路徑，此路徑最多有n-1條邊。我們將以此為依據(jù)考慮計算從源點v到其它頂點u的最短路徑的長度distu。,0,1,2,5,7,-5,0,1,2,1,1,-2,Bellman-Ford方法構(gòu)造一個最短路徑長度數(shù)組序列dist1u，dist2u，distn-1u。其中，dist1u是從源點v到終點u的只經(jīng)過一條邊的最短路徑的長度，dist1u=Edgevu；dist2u是從源點v最多經(jīng)過兩條邊到達終點u的最短路徑的長度，dist3u是從源點v出發(fā)最多經(jīng)過不構(gòu)成帶負長度邊回路的三條邊到達終點u的最短路徑的長度，distn-1u是從源點v出發(fā)最多經(jīng)過不構(gòu)成帶負長度邊回路的n-1條邊到達終點u的最短路徑的長度。算法的最終目的是計算出distn-1u?？梢杂眠f推方式計算distku。,dist1u=Edgevu；distku=mindistk-1u,mindistk-1j+Edgeju設(shè)已經(jīng)求出distk-1j,j=0,1,n-1,此即從源點v最多經(jīng)過不構(gòu)成帶負長度邊回路的k-1條邊到達終點j的最短路徑的長度。從圖的鄰接矩陣中可以找到各個頂點j到達頂點u的距離Edgeju，計算mindistk-1j+Edgeju，可得從源點v繞過各個頂點，最多經(jīng)過不構(gòu)成帶負長度邊回路的k條邊到達終點u的最短路徑的長度。用它與distk-1u比較，取小者作為distku的值。,圖的最短路徑長度,所有頂點之間的最短路徑,問題的提法：已知一個各邊權(quán)值均大于0的帶權(quán)有向圖，對每一對頂點vivj，要求求出vi與vj之間的最短路徑和最短路徑長度。Floyd算法的基本思想：定義一個n階方陣序列：A(-1),A(0),A(n-1).其中A(-1)ij=Edgeij；A(k)ij=minA(k-1)ij，A(k-1)ik+A(k-1)kj,k=0,1,n-1,A(0)ij是從頂點vi到vj,中間頂點是v0的最短路徑的長度,A(k)ij是從頂點vi到vj,中間頂點的序號不大于k的最短路徑的長度,A(n-1)ij是從頂點vi到vj的最短路徑長度。,所有各對頂點之間的最短路徑voidGraph:AllLengths(intn)/Edgenn是一個具有n個頂點的圖的鄰接矩陣。/aij是頂點i和j之間的最短路徑長度。pathij/是相應(yīng)路徑上頂點j的前一頂點的頂點號,在求/最短路徑時圖的類定義中要修改path為/pathNumVerticesNumVertices。,for(inti=0;ij/縮短路徑長度,繞過k到j(luò),以Path(3)為例，對最短路徑的讀法加以說明。從A(3)知，頂點1到0的最短路徑長度為a10=11,其最短路徑看path10=2，path12=3，path13=1,表示頂點0頂點2頂點3頂點1;從頂點1到頂點0最短路徑為,。Floyd算法允許圖中有帶負權(quán)值的邊，但不許有包含帶負權(quán)值的邊組成的回路。本章給出的求解最短路徑的算法不僅適用于帶權(quán)有向圖，對帶權(quán)無向圖也可以適用。因為帶權(quán)無向圖可以看作是有往返二重邊的有向圖，只要在頂點vi與vj之間存在無向邊(vi,vj)，就可以看成是在這兩個頂點之間存在權(quán)值相同的兩條有向邊和。,6.7最短路徑問題提出,用帶權(quán)的有向圖表示一個交通運輸網(wǎng)，圖中：頂點表示城市邊表示城市間的交通聯(lián)系權(quán)表示此線路的長度或沿此線路運輸所花的時間或費用等問題：從某頂點出發(fā)，沿圖