圖圖的定義圖（graph）是一種網(wǎng)狀數(shù)據(jù)結(jié)構(gòu)，圖是由非空的頂點(diǎn)集合和一個(gè)描述頂點(diǎn)之間關(guān)系的集合組成。其形式化的定義如下： Graph=(V,E) V={x|x∈某個(gè)數(shù)據(jù)對(duì)象}

E={<u,v>|P(u,v)∧(u,v∈V)} V是具有相同特性的數(shù)據(jù)元素的集合，V中的數(shù)據(jù)元素通常稱為頂點(diǎn)（Vertex）。

E是兩個(gè)頂點(diǎn)之間關(guān)系的集合。 P(u,v)表示u和v之間有特定的關(guān)聯(lián)屬性。2024/9/292圖的基本術(shù)語(yǔ)若<u,v>∈E，則<u,v>表示從頂點(diǎn)u到頂點(diǎn)v的一條弧，并稱u為弧尾或起始點(diǎn)，稱v為弧頭或終止點(diǎn)，此時(shí)圖中的頂點(diǎn)之間的連線是有方向的，這樣的圖稱為有向圖（directedgraph）。若<u,v>∈E則必有<v,u>∈E，即關(guān)系E是對(duì)稱的，此時(shí)可以使用一個(gè)無(wú)序?qū)?u,v)來(lái)代替兩個(gè)有序?qū)?，它表示頂點(diǎn)u和頂點(diǎn)v之間的一條邊，此時(shí)圖中頂點(diǎn)之間的連線是沒(méi)有方向的，這種圖稱為無(wú)向圖（undirectedgraph）。2024/9/293圖的示例2024/9/294圖的基本術(shù)語(yǔ)簡(jiǎn)單圖圖中所有的邊自然構(gòu)成一個(gè)集合，并且每條邊的兩個(gè)頂點(diǎn)均不相同。2024/9/295圖的基本術(shù)語(yǔ)鄰接點(diǎn)對(duì)于無(wú)向圖G=(V,E)，如果邊(u,v)∈E，則稱頂點(diǎn)u與頂點(diǎn)v互為鄰接點(diǎn)。邊(u,v)依附于頂點(diǎn)u和v，或者說(shuō)邊(u,v)與頂點(diǎn)u和v相關(guān)聯(lián)。對(duì)于有向圖G=(V,E)，如果邊<u,v>∈E，則稱頂點(diǎn)u鄰接到頂點(diǎn)v，頂點(diǎn)v鄰接自頂點(diǎn)u，或稱v為u的鄰接點(diǎn)，u為v的逆鄰接點(diǎn)。同樣我們稱邊<u,v>與頂點(diǎn)u和v相關(guān)聯(lián)。從頂點(diǎn)u出發(fā)的邊也稱為u的出邊或鄰接邊，而指向頂點(diǎn)u的邊也稱為u的入邊或逆鄰接邊。2024/9/296圖的基本術(shù)語(yǔ)頂點(diǎn)的度、入度、出度頂點(diǎn)的度（degree）是指依附于某頂點(diǎn)v的邊數(shù)，通常記為T(mén)D(v)。在有向圖中，頂點(diǎn)v的入度（indegree）是指以頂點(diǎn)為終點(diǎn)的邊的數(shù)目，記為ID(v)；頂點(diǎn)v出度（outdegree）是指以頂點(diǎn)v為起始點(diǎn)的邊的數(shù)目，記為OD(v)。對(duì)于有向圖有TD(v)=ID(v)＋OD(v)。在無(wú)向圖中每條邊都可以看成出邊，也可以看成入邊，此時(shí)TD(v)=ID(v)=OD(v)。觀察結(jié)論7.1：在任何圖G=(V,E)中，|E|=(ΣTD(vi))/22024/9/297圖的基本術(shù)語(yǔ)完全圖、稠密圖、稀疏圖觀察結(jié)論7.2假設(shè)在圖G=(V,E)中有n個(gè)頂點(diǎn)和m條邊。1）若G是無(wú)向圖，則有0≤m≤n(n-1)/2。2）若G是有向圖，則有0≤m≤n(n-1)。有n(n-1)/2條邊的無(wú)向圖稱為無(wú)向完全圖；

有n(n-1)條邊的有向圖稱為有向完全圖。有很少邊（如m<nlogn）的圖稱為稀疏圖；

反之邊較多的圖稱為稠密圖。2024/9/298圖的基本術(shù)語(yǔ)子圖設(shè)圖G=(V,E)和圖G‘=(V’,E‘)。如果V’?V且E’?E，則稱G’是G的一個(gè)子圖（subgraph）。如果V‘=V且E’?E，則稱G‘是G的一個(gè)生成子圖（spanningsubgraph）。2024/9/299子圖2024/9/2910圖的基本術(shù)語(yǔ)路徑、環(huán)路及可達(dá)分量圖中的一條通路或路徑（path），就是由m+1個(gè)頂點(diǎn)與m條邊交替構(gòu)成的一個(gè)序列ρ={v0,e1,v1,e2,v2,…,em,vm}，m≥0，且ei=(vi-1,vi)，1≤i≤m。路徑上邊的數(shù)目稱為路徑長(zhǎng)度，計(jì)作|ρ|。長(zhǎng)度|ρ|≥1的路徑，若路徑的第一個(gè)頂點(diǎn)與最后一個(gè)頂點(diǎn)相同，則稱之為環(huán)路或環(huán)(cycle)。2024/9/2911圖的基本術(shù)語(yǔ)路徑、環(huán)路及可達(dá)分量如果組成路徑ρ的所有頂點(diǎn)各不相同，則稱之為簡(jiǎn)單路徑（simplepath）；如果在組成環(huán)的所有頂點(diǎn)中，除首尾頂點(diǎn)外均各不相同，則稱該環(huán)為簡(jiǎn)單環(huán)路（simplecycle）。如果組成路徑ρ的所有邊都是有向邊，且ei均是從vi-1指向vi，1≤i≤m，則稱ρ為有向路徑；同樣可以定義有向環(huán)路。2024/9/2912圖的基本術(shù)語(yǔ)路徑、環(huán)路及可達(dá)分量在有向圖G中，若從頂點(diǎn)s到頂點(diǎn)v有一條通路，則稱v是從s可達(dá)的。對(duì)于頂點(diǎn)s，從s可達(dá)的所有頂點(diǎn)所組成的集合，稱作s在G中對(duì)應(yīng)的可達(dá)分量。2024/9/2913圖的基本術(shù)語(yǔ)連通性與連通分量在無(wú)向圖中，如果從一個(gè)頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj(i≠j)有路徑，則稱頂點(diǎn)vi和vj是連通的。如果圖中任意兩頂點(diǎn)vi、vj∈V，vi和vj都是連通的，則稱該圖是連通圖（connectedgraph）。連通分量（connectedcomponent），是指無(wú)向圖的極大連通子圖。在有向圖中，若圖中任意一對(duì)頂點(diǎn)vi和vj(i≠j)均有一條從頂點(diǎn)vi到另一個(gè)頂點(diǎn)vj的路徑，也有從vj到vii的路徑，則稱該有向圖是強(qiáng)連通圖。有向圖的極大強(qiáng)連通子圖稱為強(qiáng)連通分量。2024/9/2914強(qiáng)連通圖和強(qiáng)連通分量2024/9/2915圖的基本術(shù)語(yǔ)無(wú)向圖的生成樹(shù)對(duì)于無(wú)向圖G=(V,E)。如果G是連通圖，則G的生成樹(shù)（spanningtree），是G的一個(gè)極小連通生成子圖。2024/9/2916圖的基本術(shù)語(yǔ)權(quán)與網(wǎng)圖的邊往往與具有一定實(shí)際意義的數(shù)有關(guān)，即每條邊都有與它相關(guān)的實(shí)數(shù)，稱為權(quán)。邊上具有權(quán)值的圖稱為帶權(quán)圖（weightedgraph）或網(wǎng)（network）。2024/9/2917抽象數(shù)據(jù)類型2024/9/2918圖的抽象數(shù)據(jù)類型定義2024/9/2919圖的抽象數(shù)據(jù)類型定義2024/9/2920圖的抽象數(shù)據(jù)類型定義2024/9/2921圖的抽象數(shù)據(jù)類型定義2024/9/2922圖的Java接口2024/9/2923圖的Java接口2024/9/2924圖的Java接口2024/9/2925UnsupportedOperation異常2024/9/2926圖的存儲(chǔ)方法2024/9/2927鄰接矩陣圖的鄰接矩陣（adjacentmatrix）表示法是使用數(shù)組來(lái)存儲(chǔ)圖結(jié)構(gòu)的方法，也被稱為數(shù)組表示法。假設(shè)圖G＝(V,E)有n個(gè)頂點(diǎn)，即V＝{v0,v1,…,vn-1}，則表示G中各頂點(diǎn)關(guān)聯(lián)關(guān)系的為一個(gè)n×n的矩陣A，矩陣的元素為：2024/9/2928鄰接矩陣2024/9/2929帶權(quán)圖的鄰接矩陣若G是一個(gè)有n個(gè)頂點(diǎn)的帶權(quán)圖，則它的鄰接矩陣是具有如下性質(zhì)的n×n的矩陣A：2024/9/2930帶權(quán)圖的鄰接矩陣2024/9/2931鄰接表鄰接表（adjacencylist）是圖的一種鏈?zhǔn)酱鎯?chǔ)方法，鄰接表表示法類似于樹(shù)的孩子鏈表表示法。在鄰接表中對(duì)于圖G中的每個(gè)頂點(diǎn)vi建立一個(gè)單鏈表，將所有鄰接于vi的頂點(diǎn)vj鏈成一個(gè)單鏈表，并在表頭附設(shè)一個(gè)表頭結(jié)點(diǎn)，這個(gè)單鏈表就稱為頂點(diǎn)vi的鄰接表。2024/9/2932鄰接表結(jié)點(diǎn)結(jié)構(gòu)2024/9/2933鄰接表2024/9/2934鄰接表2024/9/2935雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)2024/9/2936頂點(diǎn)與邊的結(jié)構(gòu)雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的頂點(diǎn)定義2024/9/29382024/9/29392024/9/29402024/9/29412024/9/29422024/9/2943Vertex類中方法的功能2024/9/2944雙鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的邊定義2024/9/29452024/9/2946472024/9/2948Edge類中方法的功能49圖ADT實(shí)現(xiàn)設(shè)計(jì)2024/9/2950圖ADT的實(shí)現(xiàn)首先，確定無(wú)向圖與有向圖都支持的操作中實(shí)現(xiàn)算法相同的操作，將這些操作的實(shí)現(xiàn)放在一個(gè)抽象類AbstractGraph

中；其次，將兩類圖都支持但是實(shí)現(xiàn)算法不同的操作放在兩個(gè)不同的類DirectGraph

和UndirectedGraph

中分別實(shí)現(xiàn)，當(dāng)然DirectGraph

和UndirectedGraph

類都繼承自AbstractGraph

抽象類；最后，在DirectGraph類中實(shí)現(xiàn)只有有向圖才支持的操作，在UndirectedGraph

類中實(shí)現(xiàn)只有無(wú)向圖才支持的操作。2024/9/2951圖ADT實(shí)現(xiàn)結(jié)構(gòu)2024/9/2952AbstractGraph抽象類實(shí)現(xiàn)的方法2024/9/2953DirectGraph和UndirectedGraph分別實(shí)現(xiàn)的方法2024/9/2954圖的遍歷2024/9/2955圖的遍歷圖的遍歷就是從圖中某個(gè)頂點(diǎn)出發(fā)，按某種方法對(duì)圖中所有頂點(diǎn)訪問(wèn)且僅訪問(wèn)一次。兩種方法：深度優(yōu)先搜索廣度優(yōu)先搜索2024/9/2956深度優(yōu)先搜索深度優(yōu)先搜索（depthfirstsearch）從圖中某個(gè)頂點(diǎn)發(fā)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從v的未被訪問(wèn)的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。2024/9/2957深度優(yōu)先搜索2024/9/2958DFSTraverse2024/9/29592024/9/2960非遞歸實(shí)現(xiàn)DFS首先將初始頂點(diǎn)v入棧；當(dāng)堆棧不為空時(shí)，重復(fù)以下處理?xiàng)ｍ斣爻鰲＃粑丛L問(wèn)，則訪問(wèn)之并設(shè)置訪問(wèn)標(biāo)志，將其未曾訪問(wèn)的鄰接點(diǎn)入棧；如果圖中還有未曾訪問(wèn)的鄰接點(diǎn)，選擇一個(gè)重復(fù)以上過(guò)程。2024/9/2961DFS62廣度優(yōu)先搜索廣度優(yōu)先搜索（breadthfirstsearch）假設(shè)從圖中某頂點(diǎn)v出發(fā)，在訪問(wèn)了v之后依次訪問(wèn)v的各個(gè)未曾訪問(wèn)過(guò)的鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先被訪問(wèn)，直至圖中所有已被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到。若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。2024/9/29632024/9/2964算法思想首先訪問(wèn)初始頂點(diǎn)v并入隊(duì)；當(dāng)隊(duì)列不為空時(shí)，重復(fù)以下處理隊(duì)首元素出隊(duì)，訪問(wèn)其所有未曾訪問(wèn)的鄰接點(diǎn)，并它們?nèi)腙?duì)；如果圖中還有未曾訪問(wèn)的鄰接點(diǎn)，選擇一個(gè)重復(fù)以上過(guò)程。2024/9/2965BFSTraverse2024/9/29662024/9/2967圖的連通性2024/9/2968無(wú)向圖的連通分量2024/9/2969無(wú)向圖的生成樹(shù)設(shè)E是連通圖G中所有邊的集合，則從圖中任意一個(gè)頂點(diǎn)出發(fā)遍歷圖時(shí)，必定將E分成兩個(gè)子集：Et和Eb，其中Et是遍歷圖過(guò)程中經(jīng)歷的邊的集合；Eb是剩余邊的集合。顯然Et和圖中所有頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖，即圖G的生成樹(shù)。并且由深度優(yōu)先搜索得到的為深度優(yōu)先搜索生成樹(shù)；由廣度優(yōu)先搜索得到的為廣度優(yōu)先搜索生成樹(shù)。2024/9/2970無(wú)向圖的生成樹(shù)2024/9/2971非連通圖的生成森林2024/9/2972有向圖的強(qiáng)連通分量從有向圖中某個(gè)頂點(diǎn)s出發(fā)進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索，只能得到頂點(diǎn)s的可達(dá)分量，不一定能夠得到包含s在內(nèi)的強(qiáng)連通分量。2024/9/2973有向圖的強(qiáng)連通分量對(duì)于任何有向邊e=<u,v>，稱R(e)=<v,u>為e的鏡像邊，即R(e)的起點(diǎn)（終點(diǎn)）就是e的終點(diǎn)（起點(diǎn)）。對(duì)于任何有向圖G=(V,E)，我們稱R(E)={R(e)|e∈E}為E的鏡像邊集。此時(shí)，也稱R(G)=(V,R(E))為G的鏡像圖。構(gòu)造有向圖的強(qiáng)連通分量的方法：求出頂點(diǎn)s在圖G中的可達(dá)分量與頂點(diǎn)s在R(G)中的可達(dá)分量的交集；在有向圖中求頂點(diǎn)s的可達(dá)分量，只需要從s出發(fā)進(jìn)行深度優(yōu)先搜索或廣度優(yōu)先搜索即可。2024/9/2974有向圖的強(qiáng)連通分量2024/9/2975最小生成樹(shù)一個(gè)連通網(wǎng)的代價(jià)最小的生成樹(shù)稱為圖的最小生成樹(shù)（minimumspanningtree）。盡管最小生成樹(shù)必然存在，但不一定唯一。2024/9/2976構(gòu)造最小生成樹(shù)每步形成最小生成樹(shù)的一條邊；算法設(shè)置了邊集合A，初始時(shí)為空，該集合一直是某最小生成樹(shù)的子集。在每步?jīng)Q定是否把邊(u,v)添加到集合A中，其添加條件是A∪{(u,v)}仍然是最小生成樹(shù)的子集。稱這樣的邊為A的安全邊。通過(guò)上述過(guò)程找到|V|-1條邊最后返回集合A時(shí)，A就必然是一棵最小生成樹(shù)。2024/9/2977基本概念無(wú)向圖G=(V,E)的一個(gè)割(S,V-S)是對(duì)頂點(diǎn)集的一個(gè)劃分。當(dāng)邊(u,v)∈E的一個(gè)頂點(diǎn)在S中，而另外一個(gè)頂點(diǎn)在V-S中，我們說(shuō)邊(u,v)橫切割(S,V-S)。在橫切割的所有邊中，權(quán)最小的邊稱為輕邊。若集合A中沒(méi)有邊橫切割，則我們說(shuō)割不妨害邊的集合A。2024/9/2978割及輕邊的概念2024/9/2979確認(rèn)安全邊定理7.1設(shè)圖G=(V,E)是一個(gè)無(wú)向連通圖，且在E上定義了相應(yīng)的加權(quán)函數(shù)w，設(shè)A是E的一個(gè)子集且包含于G的某個(gè)最小生成樹(shù)中，割(S,V-S)是G的不妨害A的任意割且邊(u,v)是橫切割(S,V-S)的一條輕邊，則邊(u,v)對(duì)集合A是安全的。2024/9/2980Prim算法假設(shè)G=(V,E)是連通網(wǎng)，A是G上最小生成樹(shù)的邊的集合。算法從S={u0}（u0∈V），A={}開(kāi)始，重復(fù)執(zhí)行下述操作：找到橫切割(S,V-S)的輕邊(u0,v0)并入集合A，同時(shí)v0并入S，直到S=V為止。此時(shí)A中必定有|V|-1條邊，則T=(V,A)為G的最小生成樹(shù)。2024/9/2981Prim算法示例2024/9/29822024/9/2983算法實(shí)現(xiàn)策略首先，以頂點(diǎn)的成員變量visited來(lái)表示該頂點(diǎn)是否屬于S，visited=true表示屬于S，否則不屬于S。其次，到達(dá)V-S中各個(gè)頂點(diǎn)的最短橫切邊通過(guò)該頂點(diǎn)的成員變量application來(lái)表示，此時(shí)application指向的是Edge類的對(duì)象，它是從S到達(dá)本頂點(diǎn)橫切邊中權(quán)值最小的一條。最后，最小生成樹(shù)的表示采用設(shè)置圖中邊的類型來(lái)完成，即如果是最小生成樹(shù)的邊，將邊的類型設(shè)置為Edge.MST。2024/9/2984求MST時(shí)，對(duì)v.application的操作2024/9/2985generateMST2024/9/29862024/9/29872024/9/2988Kruskal算法假設(shè)G=(V,E)是連通網(wǎng)，則令最小生成樹(shù)的初始狀態(tài)為只有|V|個(gè)頂點(diǎn)而無(wú)邊的非連通圖，圖中每個(gè)頂點(diǎn)自成一個(gè)連通分量。在E中選擇權(quán)值最小的邊，若該邊依附的頂點(diǎn)落在T中的不同連通分量上，則將此邊加入T，否則舍去此邊選擇下一條代價(jià)最小的邊。以此類推，直到所有頂點(diǎn)都在同一連通分量上為止。2024/9/2989Kruskal算法示例2024/9/29902024/9/2991最短距離

2024/9/2992最短距離在圖中兩點(diǎn)之間的最短路徑問(wèn)題包括兩個(gè)方面：一是求圖中一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑；二是求圖中每對(duì)頂點(diǎn)之間的最短路徑。2024/9/2993單源最短路徑在帶權(quán)圖G=(V,E)中，已知源點(diǎn)為s∈V，求s到其余各頂點(diǎn)的最短路徑。在圖中若頂點(diǎn)v是從源點(diǎn)s可達(dá)的，那么從s到頂點(diǎn)v的最短路徑必然存在，其長(zhǎng)度稱為“從s到v的最短距離”，記作δ(s,v)。如果頂點(diǎn)v從s不可達(dá)，則可以認(rèn)為從s到v的距離為∞。兩點(diǎn)之間的最短路徑可能不是唯一的。2024/9/2994最短路徑的基本性質(zhì)定理7.2若π=(u0=s,u1,u2,…,uk=v)是從頂點(diǎn)s到頂點(diǎn)v的最短路徑，則對(duì)于任何0≤i<j≤k，τ=(ui,ui+1,…,uj)是從頂點(diǎn)ui到uj的最短路徑。2024/9/2995Dijkstra算法將帶權(quán)圖G=(V,E)的頂點(diǎn)分為兩個(gè)集合：S、V-S，其中頂點(diǎn)集S是已求出的最短路徑的終點(diǎn)集合（初始時(shí)S={s}）。頂點(diǎn)集V-S是尚未求出最短路徑的終點(diǎn)的集合。算法將按最短路徑長(zhǎng)度遞增的順序逐個(gè)將V-S中的頂點(diǎn)加入到S中，直到所有頂點(diǎn)都被加入到S中為止。2024/9/2996為每個(gè)頂點(diǎn)v定義了一個(gè)變量distance，該變量記錄了從s出發(fā)，經(jīng)由S中的頂點(diǎn)到達(dá)v的當(dāng)前最短距離。長(zhǎng)度最短的一條最短路徑必為π=(s,uk)，其中uk滿足： distance(uk)=min{distance(ui)|ui∈V-S}將uk并入S，即S=S∪{uk}。每當(dāng)一個(gè)新的頂點(diǎn)uk加入S之后，要以u(píng)k為“中轉(zhuǎn)”頂點(diǎn)對(duì)V-S中各個(gè)頂點(diǎn)的當(dāng)前最短路徑distance進(jìn)行修正。2024/9/2997修正當(dāng)前最短路徑依次對(duì)頂點(diǎn)uk的鄰接點(diǎn)ui（ui∈V-S）執(zhí)行如下操作：

distance(ui)=min{distance(ui),distance(uk)+w(uk,ui)}，ui∈V-S

其中distance(ui)是ui當(dāng)前最短距離，distance(uk)+w(uk,ui)是經(jīng)過(guò)uk

“中轉(zhuǎn)”的路徑長(zhǎng)度，修正之后ui的當(dāng)前最短路徑長(zhǎng)度是兩者中小的。2024/9/2998Dijkstra算法①初始化： S={s}；distance(s)=0； distance(ui)=w(s,ui)或∞，（ui∈V-S）；②選擇distance(uk)=min{distance(ui)|ui∈V-S}，uk為下一條最短路徑的終點(diǎn)；③S=S∪{uk}④以u(píng)k為“中轉(zhuǎn)”，修正V-S中各個(gè)頂點(diǎn)distance：

distance(ui)=min{distance(ui),distance(uk)+w(uk,ui)}，ui∈V-S⑤重復(fù)②—④步|V|-1次。2024/9/29992024/9/29100對(duì)v.application的操作2024/9/29101Path類定義2024/9/291021032024/9/29104Dijkstra算法的具體實(shí)現(xiàn)shortestPath2024/9/291052024/9/291062024/9/291072024/9/29108任意頂點(diǎn)間的最短路徑定義：D(k)（0≤k≤|V|）是一個(gè)|V|階方陣，其中D(k)[i][j]是在考慮帶權(quán)圖中前k個(gè)頂點(diǎn)，將它們作為中間頂點(diǎn)時(shí)從頂點(diǎn)vi到頂點(diǎn)vj的當(dāng)前最短距離（1≤i≤|V|，1≤j≤|V|）。2024/9/29109Floyd算法基本思想：(1)用鄰接矩陣初始化D(0)，對(duì)角線元素為0；(2)在頂點(diǎn)vi、vj之間考慮頂點(diǎn)vl比較在引入vl之后vi到vjj的當(dāng)前最短距離是否可以通過(guò)vl變得更小。把vl放在vi到vj的路徑上，vi到vj之間可能會(huì)產(chǎn)生新的路徑，其距離為D(0)[i][1]+D(0)[1][j]，當(dāng)然vl的引入可能反而會(huì)加大vi到vj的距離，因此需要比較D(0)[i][1]+D(0)[1][j]與D(0)[i][j]的大小。最終，在考慮vl之后vi到vj的當(dāng)前最短距離為兩者中小的。即 D(1)[i][j]=min{D(0)[i][1]+D(0)[1][j],D(0)[i][j]}2024/9/29110Floyd算法基本思想：(3)一般情況下，如果在考慮了前k-1個(gè)頂點(diǎn){v1,v2,…,vk-1}之后，從頂點(diǎn)vi到vj的當(dāng)前最短距離是D(k-1)[i][j]。那么在頂點(diǎn)vi、vj之間考慮前k個(gè)頂點(diǎn)時(shí)，頂點(diǎn)vi到vj的當(dāng)前最短距離為以下兩個(gè)距離中小的：在考慮前k-1個(gè)頂點(diǎn)基礎(chǔ)上將vk放在vi到vj的路徑上，此時(shí)產(chǎn)生新的路徑長(zhǎng)度為D(k-1)[i][k]+D(k-1)[k][j]；以及不將vk放在vi到vj的路徑上的距離D(k-1)[i][j]。最終，在考慮前k個(gè)頂點(diǎn){v1,v2,…,vk}之后，vi到vj的當(dāng)前最短距離D(k)[i][j]=min{D(k-1)[i][k]+D(k-1)[k][j],D(k-1)[i][j]}1≤k≤|V|(4)依次進(jìn)行下去，直到k=|V|。此時(shí)D(|V|)[i][j]即為帶權(quán)圖中任意兩個(gè)頂點(diǎn)vi到vj的最短距離。2024/9/29111Floyd算法執(zhí)行過(guò)程2024/9/29112有向無(wú)環(huán)圖及其應(yīng)用2024/9/29113有向無(wú)環(huán)圖有向無(wú)環(huán)圖（directedacyclicgraph）是指一個(gè)無(wú)環(huán)的有向圖，簡(jiǎn)稱DAG。2024/9/29114拓?fù)渑判蛉绻谝粋€(gè)有向圖G=<V,E>中用頂點(diǎn)表示活動(dòng)，用有向邊<vi,vj>表示活動(dòng)vi必須先于活動(dòng)vj進(jìn)行。這種有向圖叫做頂點(diǎn)表示活動(dòng)的AOV網(wǎng)絡(luò)（activityonverticesnetworks）。2024/9/29115AOV網(wǎng)及拓?fù)湫蛄衋.購(gòu)買(mǎi)原材料；b.生產(chǎn)零件1；c.用零件1加工零件2；d.生產(chǎn)零件3；e.組裝零件2、3得到成品。2024/9/29116拓?fù)渑判蛴赡硞€(gè)集合上的一個(gè)偏序得到該集合上的一個(gè)全序，此操作稱之為拓?fù)渑判颍╰opologicalsort）。⑴在AOV網(wǎng)絡(luò)中選一個(gè)沒(méi)有直接前驅(qū)的頂點(diǎn)，并輸出之；⑵從圖中刪去該頂點(diǎn)，同時(shí)刪去所有它發(fā)出的有向邊；⑶重復(fù)以上⑴、⑵步,直到全部頂點(diǎn)均已輸出，或圖中不存在無(wú)前驅(qū)的頂點(diǎn)。2024/9/29117拓?fù)渑判虻倪^(guò)程2024/9/29118拓?fù)渑判虻膶?shí)現(xiàn)首先，為每個(gè)頂點(diǎn)v設(shè)置一個(gè)變量，記錄其在拓?fù)渑判蜻^(guò)程中的入度，入度為0的頂點(diǎn)就是沒(méi)有直接前驅(qū)的頂點(diǎn)。其次，刪除一條有向邊可以用有向邊終止點(diǎn)的入度減1來(lái)實(shí)現(xiàn)。2024/9/29119構(gòu)造AOV網(wǎng)絡(luò)的拓?fù)湫蛄孝沤⑷攵葹榱愕捻旤c(diǎn)棧；⑵當(dāng)入度為零的頂點(diǎn)棧不空時(shí)，重復(fù)執(zhí)行從頂點(diǎn)棧中退出一個(gè)頂點(diǎn)，并輸出之；搜索以這個(gè)頂點(diǎn)發(fā)出的邊，將邊的終頂點(diǎn)入度減1；

如果邊的終頂點(diǎn)入度減至0，則該頂點(diǎn)進(jìn)入棧；⑶如果輸出頂點(diǎn)個(gè)數(shù)少于AOV網(wǎng)絡(luò)的頂點(diǎn)個(gè)數(shù)，說(shuō)明網(wǎng)絡(luò)中存在有向環(huán)。2024/9/29120對(duì)v.application的操作2024/9/29121toplogicalSort2024/9/291222024/9/29123關(guān)鍵路徑如果在有向無(wú)環(huán)的帶權(quán)圖中：用有向邊表示一個(gè)工程中的各項(xiàng)活動(dòng)(activity)；用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(duration)；用頂點(diǎn)表示事件(event)；

則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱AOE(activityonedges)網(wǎng)絡(luò)。2024/9/29124AOE網(wǎng)假設(shè)活動(dòng)a需時(shí)3天、活動(dòng)b需時(shí)1天、活動(dòng)c需時(shí)2天、活動(dòng)d需時(shí)5天、活動(dòng)e需時(shí)2天。 a.購(gòu)買(mǎi)原材料； b.生產(chǎn)零件1； c.用零件1加工零件2； d.生產(chǎn)零件3； e.組裝零件2、3得到成品。2024/9/29125AOE網(wǎng)在正常情況下，AOE網(wǎng)絡(luò)中只有一個(gè)入度為0的頂點(diǎn)，也只有一個(gè)出度為0的頂點(diǎn)，它們分別稱之為源點(diǎn)和匯點(diǎn)。完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。這條路徑長(zhǎng)度最長(zhǎng)的路徑就叫做關(guān)鍵路徑（criticalpath）。2024/9/29126變量定義在圖G={V,E}中，假設(shè)V={v0,v1,…,vn-1}，其中n=|V|，v0是源點(diǎn)，vn-1是匯點(diǎn)。為求關(guān)鍵活動(dòng)，定義以下變量：事件vi的最早可能開(kāi)始時(shí)間Ve[i]：是從源點(diǎn)v0到頂點(diǎn)vi的最長(zhǎng)路徑長(zhǎng)度。活動(dòng)ak的最早可能開(kāi)始時(shí)間e[k]：設(shè)活動(dòng)ak在邊<vi,vj>上，則e[k]是從源點(diǎn)v0到頂點(diǎn)vi的最長(zhǎng)路徑