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

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