數(shù)據(jù)結(jié)構(gòu)第 7 章 圖@南京工程學(xué)院通信工程學(xué)院

《數(shù)據(jù)結(jié)構(gòu)第 7 章 圖@南京工程學(xué)院通信工程學(xué)院》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫(kù)。

1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容多對(duì)多（m:n) 27.1抽象數(shù)據(jù)類(lèi)型圖的定義7.2圖的存儲(chǔ)表示7.3圖的遍歷7.4最小生成樹(shù)7.5重（雙）連通圖和關(guān)節(jié)點(diǎn)7.6兩點(diǎn)之間的最短路徑問(wèn)題7.7拓?fù)渑判?.8關(guān)鍵路徑第七章圖 3一、圖的定義和術(shù)語(yǔ)圖(Graph)——圖G是由兩個(gè)集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點(diǎn)的非空有限集E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)蛴行驅(qū)?。有向圖——有向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集E(G)是有向邊（也稱(chēng)?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)?，記?v,w>，v,w是頂點(diǎn)，v為弧尾，w為弧頭無(wú)向圖——無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集E(G)是邊的有限集合，邊是頂點(diǎn)的無(wú)序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v)7.1抽象數(shù)據(jù)類(lèi)型圖的定義(u,v)V=VertexE=Edge 4例245136G1有向圖G1=（V，E）中：V(G1)={1,2,3,4,5,6}E(G1)={<1,2>,<2,1>,<2,3>,<2,4>,<3,5>,<5,6>,<6,3>}例157324G26無(wú)向圖G2=（V，E）中：V(G2)={1,2,3,4,5,6,7}E(G1)={(1,2),(1,3),(2,3),(2,4),(2,5),(5,6),(5,7)}圖的示例 5有向完全圖——有n(n-1)條弧的n個(gè)頂點(diǎn)的有向圖無(wú)向完全圖——有n(n-1)/2條邊的n個(gè)頂點(diǎn)的無(wú)向圖稀疏圖--若邊或弧的個(gè)數(shù)e，若G是無(wú)向的，則還增添對(duì)稱(chēng)弧(w,v)。DeleteArc(&G,v,w);//在G中刪除弧，若G是無(wú)向的，則還刪除對(duì)稱(chēng)弧(w,v)。 16遍歷DFSTraverse(G,v,Visit());//從頂點(diǎn)v起深度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。BFSTraverse(G,v,Visit());//從頂點(diǎn)v起廣度優(yōu)先遍歷圖G，并對(duì)每//個(gè)頂點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。 177.2圖的存儲(chǔ)表示1、數(shù)組(鄰接矩陣)存儲(chǔ)表示2、鄰接表存儲(chǔ)表示3、有向圖的十字鏈表存儲(chǔ)表示4、無(wú)向圖的鄰接多重表存儲(chǔ)表示 18用兩個(gè)數(shù)組分別存儲(chǔ)頂點(diǎn)信息和頂點(diǎn)之間的關(guān)系信息(鄰接矩陣—表示頂點(diǎn)間相鄰關(guān)系的矩陣)定義：設(shè)G=(V,E)是有n?1個(gè)頂點(diǎn)的圖，G的鄰接矩陣A（二維數(shù)組）是具有以下性質(zhì)的n階方陣：例G12413例15324G2??????????????????1、圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示 19鄰接矩陣特點(diǎn)：無(wú)向圖的鄰接矩陣對(duì)稱(chēng)，可壓縮存儲(chǔ)；有n個(gè)頂點(diǎn)的無(wú)向圖需存儲(chǔ)空間為n(n+1)/2有向圖鄰接矩陣不一定對(duì)稱(chēng)；有n個(gè)頂點(diǎn)的有向圖需存儲(chǔ)空間為n2無(wú)向圖中頂點(diǎn)Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點(diǎn)Vi的出度是A中第i行元素之和頂點(diǎn)Vi的入度是A中第i列元素之和(第i行非0元素1的個(gè)數(shù))??????????????????例G12413例15324G2 20??????????例1452375318642網(wǎng)的鄰接矩陣示意圖網(wǎng)的鄰接矩陣可定義為：∞反之容易實(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)： 21typedefstructArcCell{//弧的定義VRTypeadj;//VRType是頂點(diǎn)關(guān)系類(lèi)型,//對(duì)無(wú)權(quán)圖，用1或0表示相鄰否；對(duì)帶權(quán)圖，則為權(quán)值類(lèi)型。InfoType*info;//該弧相關(guān)信息的指針}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示實(shí)現(xiàn)#defineINFINITYINT_MAX//定義無(wú)窮大∞#defineMAX_VERTEX_NUM20//定義圖的類(lèi)型{有向圖,有向網(wǎng),無(wú)向圖,無(wú)向網(wǎng)}typedefenum{DG,DN,UDG,UDN}GraphKind;typedefstruct{//圖的定義VertexTypevexs[MAX_VERTEX_NUM];//頂點(diǎn)數(shù)組AdjMatrixarcs;//鄰接矩陣，可設(shè)二維intvexnum,arcnum;//頂點(diǎn)數(shù)，弧數(shù)GraphKindkind;//圖的種類(lèi)標(biāo)志}MGraph; 22例G12413例15324G2??????????????????圖的數(shù)組(鄰接矩陣)存儲(chǔ)表示實(shí)例（構(gòu)建算法見(jiàn)教材P162）G1.vexs={1，2，3，4}；G1.arcs=G1.vexnum=4；G1.arcnum=4；G1.kind=DG；G2.vexs={[1，2，3，4，5}；G2.arcs=G2.vexnum=5；G2.arcnum=6；G2.kind=UDG；MGraphG1; 23表頭結(jié)點(diǎn)結(jié)構(gòu):數(shù)據(jù)域（data）用于存儲(chǔ)頂點(diǎn)的名或其它有關(guān)信息；鏈域（firstarc）用于指向鏈表中第一個(gè)頂點(diǎn)（即與頂點(diǎn)vi鄰接的第一個(gè)鄰接點(diǎn)）邊表結(jié)點(diǎn)結(jié)構(gòu)：adjvex與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置info存儲(chǔ)和邊相關(guān)的信息(若無(wú)，則置空NULL)nextarc指向下一條邊的結(jié)點(diǎn)的指針表頭結(jié)點(diǎn)弧結(jié)點(diǎn)datafirstarcadjvexinfonextarc2、圖的鄰接表存儲(chǔ)表示實(shí)現(xiàn)：為圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)Vi的邊（有向圖中指以Vi為尾的?。?；同時(shí)為每一個(gè)單鏈表附設(shè)一個(gè)表頭結(jié)點(diǎn)，并將所有的表頭結(jié)點(diǎn)順序存儲(chǔ)（數(shù)組），以便隨機(jī)訪問(wèn)任一頂點(diǎn)的鏈表。 24例G1bdac例aecbdG21234acdbvexdatafirstarc3241^^^^adjvexnextarc1234acdbvexdatafirstarc4212^^^adjvexnextarc5e435^15323^提示：在無(wú)向圖，每一個(gè)邊結(jié)點(diǎn)在圖的單鏈表中出現(xiàn)兩次，故無(wú)向圖中若有n個(gè)頂點(diǎn)和e條邊，則需要存儲(chǔ)空間為：n+2e圖的鄰接表存儲(chǔ)實(shí)例 25typedefstructArcNode//弧結(jié)點(diǎn){intadjvex;//鄰接點(diǎn)域，存放與Vi鄰接的點(diǎn)在表頭數(shù)組中的位置structnode*nextarc;//鏈域，指示依附于vi的下一條邊或弧的結(jié)點(diǎn)，//VRTypeweight;InfoType*info;//定義與弧相關(guān)的權(quán)值，無(wú)權(quán)則為0}ArcNode;//定義指向該弧相關(guān)信息的指針typedefstructVNode//表頭結(jié)點(diǎn){VertexTypevexdata;//存放頂點(diǎn)信息structArcNode*firstarc;//指示第一個(gè)鄰接點(diǎn)}VNode，AdjList[MAX_VERTEX_NUM];vexdatafirstarc圖的鄰接表存儲(chǔ)表示typedefstruct{//圖的結(jié)構(gòu)定義AdjListvertices;//頂點(diǎn)向量intvexnum,arcnum;GraphKindkind;//圖的種類(lèi)標(biāo)志}ALGraph;adjvexnextarcWeightinfo 26鄰接表特點(diǎn)無(wú)向圖中頂點(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ù)（以vi為弧頭）。為此需遍歷整個(gè)鄰接表。一種解決的方法是逆鄰接表法 27一種解決的方法是逆鄰接表法，我們可以對(duì)每一頂點(diǎn)vi再建立一個(gè)逆鄰接表，即對(duì)每個(gè)頂點(diǎn)vi建立一個(gè)所有以頂點(diǎn)vi為弧頭的弧的表，如圖所示。圖G1的鄰接表和逆鄰接表表示法例G1bdac1234acdbvexdatafirstarc41^1^^3^adjvexnextarc1234acdbvexdatafirstarc2341^^^^adjvexnextarc 28練習(xí)：求下圖各頂點(diǎn)的出度、入度，圖的鄰接矩陣、鄰接表和逆鄰接表圖G1cdabe 29討論：鄰接表與鄰接矩陣有什么異同之處？聯(lián)系：鄰接表中每個(gè)鏈表對(duì)應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點(diǎn)個(gè)數(shù)等于該行中非零元素的個(gè)數(shù)。2.區(qū)別：①對(duì)于任一確定的無(wú)向圖，鄰接矩陣是唯一的（行列號(hào)與頂點(diǎn)編號(hào)一致），但鄰接表不唯一（鏈接次序與頂點(diǎn)編號(hào)無(wú)關(guān)）。②鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。e隨n的改變而變化--函數(shù)關(guān)系3.用途：鄰接矩陣多用于稠密圖的存儲(chǔ)（e接近n(n-1)/2)；而鄰接表多用于稀疏圖的存儲(chǔ)（e<");//輸入各邊并構(gòu)造鄰接表scanf("%d,%d",&i,&j);s=(ArcNode*)malloc(sizeof(ArcNode));s->adjvex=j;s->nextarc=G.vertices[i].firstarc;G.vertices[i].firstarc=s;}} 31舉例：建立有（無(wú)）向圖的鄰接表圖的鄰接表是應(yīng)用較多的一種存儲(chǔ)結(jié)構(gòu)。從鄰接表的結(jié)構(gòu)定義可見(jiàn)，建立鄰接表的主要操作是在鏈表中插入一個(gè)結(jié)點(diǎn)，以下是輸入無(wú)向圖的頂點(diǎn)和邊建立鄰接表的算法步驟。BCAFED0A411B5402C533D524E105F320依次輸入的數(shù)據(jù)為：1.頂點(diǎn)、邊數(shù)：67UDG2.頂點(diǎn)：ABCDEF3.邊：ABAEBEBFCDCFDF頭插法vexdatafirstarcadjvexnextarc 32舉例：建立有（無(wú)）向圖的鄰接表（續(xù)）建立鄰接表的主要操作是在鏈表中插入一個(gè)結(jié)點(diǎn)，以下是輸入有向圖的頂點(diǎn)和弧建立鄰接表的算法。依次輸入的數(shù)據(jù)為：1.57DG2.ABCDE3.ABAEBCCDDADBECABECD142301201234ABCDE?????尾插法 333、有向圖的十字鏈表存儲(chǔ)表示有向圖的鄰接表和逆鄰接表組合 ABCABC012∧02∧∧0121∧20∧∧有向圖十字鏈表表示示意圖有向圖的十字鏈表 35typedefstructArcNode{inttailvex,headvex;//弧尾、弧頭在表頭數(shù)組中位置structArcNode*hlink；//指向弧頭相同的下一條弧structArcNode*tlink;//指向弧尾相同的下一條弧InfoType*info;//定義弧的相關(guān)信息，如權(quán)值}ArcNode;typedefstructVexNode{intdata;//存與頂點(diǎn)有關(guān)信息ArcNode*firstin；//指向以該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)ArcNode*firstout;//指向以該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)}VexNode;datafirstinfirstout有向圖的十字鏈表存儲(chǔ)表示tailvexheadvexhlinktlinkinfo弧結(jié)點(diǎn)：頂點(diǎn)結(jié)點(diǎn)：typedefstruct{//圖的定義VexNodexlist[MAX_VERTEX_NUM];//頂點(diǎn)結(jié)點(diǎn)(表頭向量)intvexnum,arcnum;//有向圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}OLGraph; 36類(lèi)似于有向圖的十字鏈表，若將無(wú)向圖中表示同一條邊的兩個(gè)結(jié)點(diǎn)合在一起，將得到無(wú)向圖的另一種表示方法--鄰接多重表。例如4、無(wú)向圖的鄰接多重表存儲(chǔ)表示BCAFED 37無(wú)向圖的鄰接多重表存儲(chǔ)表示在鄰接多重表中，每一條邊用一個(gè)結(jié)點(diǎn)表示，邊結(jié)點(diǎn)結(jié)構(gòu)如下：markivexilinkjvexjlinkinfoconstMAX_VERTEX_NUM=20;typedefemnu{unvisited,visited}VisitIf;typedefstructEdgeNode{//邊結(jié)點(diǎn)結(jié)構(gòu)定義VisitIfmark;//訪問(wèn)標(biāo)記intivex,jvex;//該邊依附的兩個(gè)頂點(diǎn)（vi，vj）在圖中的位置structEdgeNode*ilink,*jlink;//分別指向依附這兩個(gè)頂點(diǎn)的下一條邊VRTypeweight;//與弧相關(guān)的權(quán)值，無(wú)權(quán)則為0InfoType*info;//與該邊相關(guān)信息的指針};datafirstedge頂點(diǎn)結(jié)點(diǎn)：typedefstruct{//頂點(diǎn)結(jié)點(diǎn)結(jié)構(gòu)定義VertexTypedata;EdgeNode*firstedge;//指向第一條依附該頂點(diǎn)的邊}VexNode;typedefstruct{//多重鏈表結(jié)構(gòu)定義VexNodeadjmulist[MAX_VERTEX_NUM];intvexnum,edgenum;//無(wú)向圖的當(dāng)前頂點(diǎn)數(shù)和邊數(shù)GraphKindkind;//圖的種類(lèi)標(biāo)志}AMLGraph; 38各種存貯結(jié)構(gòu)的適用類(lèi)型數(shù)組(鄰接矩陣)：有向圖和無(wú)向圖鄰接表（逆鄰接表）：有向圖和無(wú)向圖十字鏈表：有向圖鄰接多重表：無(wú)向圖 397.3圖的遍歷從圖中某個(gè)頂點(diǎn)出發(fā)游歷圖，訪遍圖中其余頂點(diǎn)，并且使圖中的每個(gè)頂點(diǎn)僅被訪問(wèn)一次的過(guò)程。圖的遍歷（TraversingGraph）:V1V2V4V5V3V7V6V8例提示：前面學(xué)習(xí)過(guò)樹(shù)的遍歷有遞歸遍歷（前序、中序和后序）和非遞歸算法演示提問(wèn)：樹(shù)的遍歷能否用于圖的遍歷？能或不能為什么？不能！因?yàn)閳D有回路，若用樹(shù)的遍歷算法可能導(dǎo)致無(wú)限循環(huán)。為防止循環(huán)，可設(shè)置已訪問(wèn)標(biāo)志。然而，圖中可能有孤立點(diǎn)，若不加修改地使用樹(shù)的遍歷，就可能會(huì)遺漏圖中的一部分頂點(diǎn)。 40為了保證圖中的各頂點(diǎn)在遍歷過(guò)程中訪問(wèn)且僅訪問(wèn)一次，需要為每個(gè)頂點(diǎn)設(shè)一個(gè)訪問(wèn)標(biāo)志，因此我們?yōu)閳D設(shè)置一個(gè)訪問(wèn)標(biāo)志數(shù)組visited［n］:vi未被訪問(wèn):visited[i]值為falsevi被訪問(wèn)過(guò)：visited［i］為true根據(jù)搜索路徑方向不同：深度優(yōu)先搜索（縱向↓）廣度優(yōu)先搜索（橫向→）遍歷應(yīng)用舉例V1V2V4V5V3V7V6V8例 41深度優(yōu)先搜索(Depth-FirstSearch—DFS)是指按照深度方向搜索,它類(lèi)似于樹(shù)的先根遍歷,是樹(shù)的先根遍歷的推廣。深度優(yōu)先搜索連通子圖的基本思想是：假設(shè)圖G初態(tài)為所有頂點(diǎn)未被訪問(wèn)（visited[i]=false），從G中任選一頂點(diǎn)vi：⑴、從該頂點(diǎn)vi出發(fā),首先訪問(wèn)vi,,置visited[vi]=true;⑵、然后依次搜索vi的每一個(gè)鄰接點(diǎn)vj；⑶、若vj未被訪問(wèn)過(guò)，則以vj為新的初始出發(fā)點(diǎn)，重復(fù)⑴若vj已被訪問(wèn)過(guò)，則返回到vi另一個(gè)鄰接點(diǎn)，重復(fù)⑶⑷、如果經(jīng)過(guò)⑴、⑵、⑶后,圖中仍有未被訪問(wèn)的頂點(diǎn),再?gòu)闹腥芜x一頂點(diǎn),重復(fù)⑴、⑵、⑶,直至所有頂點(diǎn)都被訪問(wèn)過(guò),遍歷結(jié)束。一、深度優(yōu)先搜索遍歷圖V1V2V4V5V3V7V6V8例無(wú)向圖深度遍歷：V1?V2?V4?V8?V5?V3?V6?V7V1V2V4V5V3V7V6V8例有向圖 42V1V2V4V5V3V7V6V8例深度遍歷：V1?1234v1v3v4v2vexdatafirstarc2783^^^adjvexnext5v5641^51282^v6v7v8678736354^^^V3?V7?V6?V2?V5?V8?V4思考題：按圖的存儲(chǔ)結(jié)構(gòu)如何遍歷？鄰接矩陣如何？思想同算法vi=v11.訪問(wèn)V1。2.求Vi的鄰接點(diǎn)Vj。3.若vj未被訪問(wèn)過(guò)，則以vj為新的初始出發(fā)點(diǎn)，重復(fù)⑴若vj已被訪問(wèn)過(guò)，則返回到vi另一個(gè)鄰接點(diǎn)，重復(fù)⑶ 43V1V2V4V5V3V7V6V8例12341342vexdatafirstarc2783^^^adjvexnext556^482^6786787^^^深度遍歷：V1?V3?V7?V6?V2?V4?V8?V5 44從上頁(yè)的遍歷過(guò)程可見(jiàn):1.深度優(yōu)先搜索遍歷連通圖的過(guò)程類(lèi)似于樹(shù)的先根遍歷；解決的辦法是：為每個(gè)頂點(diǎn)v設(shè)立一個(gè)“訪問(wèn)標(biāo)志visited[v]”。2.如何判別V的鄰接點(diǎn)是否被訪問(wèn)？3.如何求V的鄰接點(diǎn)？解決的辦法是：根據(jù)圖的存儲(chǔ)結(jié)構(gòu)來(lái)確定。對(duì)于鄰接表而言，通過(guò)頂點(diǎn)向量和對(duì)應(yīng)的單鏈表查找鄰接點(diǎn)。 45深度優(yōu)先遍歷算法-遞歸算法開(kāi)始訪問(wèn)V0,置標(biāo)志求V0鄰接點(diǎn)有鄰接點(diǎn)w？求下一鄰接點(diǎn)w→V0W訪問(wèn)過(guò)？返回NYNYDFS開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪問(wèn)過(guò)DFSVi=Vi+1Viv2,V1->v3的路徑長(zhǎng)度為1；V1->v4,V1->v5,V1->v6,V1->v7的路徑長(zhǎng)度為2；V1->v8的路徑長(zhǎng)度為3。V1V2V4V5V3V7V6V8例例如：廣度遍歷序列：V1V2V3V4V5V6V7V8 54為避免重復(fù)訪問(wèn),需要一個(gè)輔助數(shù)組visited[n]，給被訪問(wèn)過(guò)的頂點(diǎn)加標(biāo)記。為了實(shí)現(xiàn)逐層（按頂點(diǎn)的路徑長(zhǎng)度遞增）訪問(wèn),算法中需使用了一個(gè)隊(duì)列,以記憶正在訪問(wèn)的這一層和下一層的頂點(diǎn),以便于向下一層訪問(wèn)。 5512341342vexdatafirstarc5543^^^adjvexnext551^51143^220123451fr遍歷序列：10123454fr遍歷序列：1401234543fr遍歷序列：143先訪問(wèn)后入隊(duì)1出隊(duì)，依次得到其所有鄰接點(diǎn)，輸出并進(jìn)隊(duì)例14235 5612341342vexdatafirstarc5543^^^adjvexnext551^51143^22012345432fr遍歷序列：1432012345325fr遍歷序列：143251的鄰接點(diǎn)入隊(duì)完畢，4出隊(duì)，依次得到其所有未被訪問(wèn)的鄰接點(diǎn)，輸出并進(jìn)隊(duì)例14235 5701234525fr遍歷序列：143250123455fr遍歷序列：14325012345fr遍歷序列：14325例1423512341342vexdatafirstarc5543^^^adjvexnext551^51143^22 58廣度優(yōu)先搜索遍歷圖算法流程圖開(kāi)始訪問(wèn)V,置標(biāo)志求U鄰接點(diǎn)WW存在嗎U下一鄰接點(diǎn)?WW訪問(wèn)過(guò)結(jié)束NYNY初始化隊(duì)列V入隊(duì)隊(duì)列空嗎隊(duì)頭出隊(duì)?U訪問(wèn)W,置標(biāo)志W(wǎng)入隊(duì)NaaYBFS開(kāi)始標(biāo)志數(shù)組初始化Vi=0Vi訪問(wèn)過(guò)？BFSVi=Vi+1Vi8?30?32V2:813-------1330?32V1:13--------------13302220V3:13---------------------192220V4:19終點(diǎn)從V0到各終點(diǎn)的最短路徑及其長(zhǎng)度V1V2V3V4V5V6Vj--------------------------------2120V6:20516432085623013717329求最短路徑示例2： 83i<=G.vexnum初始化過(guò)程;(i=1;)EndNYw，則對(duì)應(yīng)元素為權(quán)值；否則為?逐步試著在原直接路徑中增加中間頂點(diǎn)（依次為v0,v1,…），若加入中間點(diǎn)后路徑變短，則修改之；否則，維持原值所有頂點(diǎn)試探完畢，算法結(jié)束二、每一對(duì)頂點(diǎn)之間的最短路徑 85例ACB26431104116023?0初始：路徑：ABACBABCCA046602370加入B：路徑：ABABCBABCCACAB0411602370加入A：路徑：ABACBABCCACAB046502370加入C：路徑：ABABCBCABCCACAB求每一對(duì)頂點(diǎn)之間的最短路徑的示例： 86算法實(shí)現(xiàn)圖用鄰接矩陣存儲(chǔ)length[][]存放最短路徑長(zhǎng)度path[i][j]是從Vi到Vj的最短路徑上Vj前一頂點(diǎn)序號(hào)算法描述例132264311初始：04116023?0length=011202300path=加入V1：0411602370length=011202310path=加入V2：046602370length=012202310path=加入V3：046502370length=012302310path=算法分析：T(n)=O(n3) 1給出如圖所示的無(wú)向圖G的鄰接矩陣和鄰接表兩種存儲(chǔ)結(jié)構(gòu)。作業(yè)2.假設(shè)圖的頂點(diǎn)是A、B……請(qǐng)根據(jù)下面的鄰接矩陣畫(huà)出相應(yīng)的無(wú)向圖或有向圖。 3.分別給出如圖所示G圖的深度優(yōu)先搜索和廣度優(yōu)先搜索得到的頂點(diǎn)訪問(wèn)序列。4.應(yīng)用prim算法求圖所示帶權(quán)連通圖的最小生成樹(shù)。 89圖存儲(chǔ)結(jié)構(gòu)遍歷鄰接矩陣鄰接表十字鏈表鄰接多重表深度優(yōu)先搜索DFS廣度優(yōu)先搜索DFS無(wú)向圖的應(yīng)用應(yīng)用圖的連通分量圖的生成樹(shù)最小生成樹(shù)Prim算法Kruskal算法有向(無(wú)環(huán))圖的應(yīng)用最短路徑Dijkstra算法Floyd算法（利用DFS）本章小結(jié)-體系結(jié)構(gòu)圖(利用DFS和BFS)AOV網(wǎng),AOE網(wǎng)拓?fù)渑判蜿P(guān)鍵路徑 901.熟悉圖的各種存儲(chǔ)結(jié)構(gòu)及其構(gòu)造算法，了解實(shí)際問(wèn)題的求解效率與采用何種存儲(chǔ)結(jié)構(gòu)和算法有密切聯(lián)系。2.熟練掌握?qǐng)D的兩種搜索路徑的遍歷：遍歷的邏輯定義、深度優(yōu)先搜索和廣度優(yōu)先搜索的算法。在學(xué)習(xí)中應(yīng)注意圖的遍歷算法與樹(shù)的遍歷算法之間的類(lèi)似和差異。3.應(yīng)用圖的遍歷算法求解各種簡(jiǎn)單路徑問(wèn)題。4.理解教科書(shū)中討論的各種圖的算法。本章小結(jié)（續(xù)）