第科技學院計算機學院

Office:9棟樓9-206（網(wǎng)絡教研室?: 課件PPT下載：第6章圖6.1圖6.1圖(注:頂點(Vertices)和邊V：頂點(數(shù)據(jù)元素)的有窮非空集合E：邊的有窮 表示圖形所有頂點的集合V(G)={V1,V2,V3,…,Vm}，其中表示圖形所有邊的集合E(G)={E1,E2,E3,…,En}，其中 無向圖(Undigraph)每條邊都是無方向 有向圖(Digraph

每條邊都是有方

圖的定義和基本圖的定義和基本案例引圖的類 圖結圖的遍圖的應案例分析與教學目1.掌握：圖的基本 熟練掌握：最短路算法（Dijkstra算法圖的定義和基圖的定義和基2.圖的基如果無向圖中任意兩個頂點間都存在邊，則稱之為無向完全圖(CompletedGraph)。在一個含有n個頂點的無向完全圖中，邊數(shù)為n(n-1)/2條。如果有向圖中任意兩個頂點間都存在方向互為相反的兩完全圖：任意兩個點都有一條邊無向完邊(Edges)是沒有方向性邊(V1,V2)與邊(V2,V1)是相同并且邊以()表示

有向完邊(Edges)是有方向性邊<V1,V2>與邊<V2,V1>是不相的。邊以<>表示。<V1,V2>，其中圖的定

圖的定義和基本2.圖的基 之間的連線記為有序偶對<vi，vj，其中頂點vi稱為初始點(弧E2={<v1,v2>,<v2,v1>,<v2,v3>,<v1,v3>}，以弧<v1,v3>【舉【舉例1】假設有一個無向圖形，如下圖所示ABCDE請問，此無向圖形的頂點(V)和邊(E)如何【解答E(G)={(A,B),(A,C),(B,A),(B,D),(C,A),(C,E),(D,B),(D,E),(E,C)有向【舉例2】假設有一個有向圖形，如下圖A

請問，此有向圖形的頂點(V)和邊(E)如何表示呢稀疏圖：有很少邊或弧的圖。當一個圖中含有較少的，則稱之為稀疏圖(SparseGraph)稠密圖：有較多邊或弧的圖。當一個圖接近完全圖時，稱之稠密圖(Dense網(wǎng)：邊/弧帶權的圖。在邊或者弧上的數(shù)據(jù)信息稱為邊的權Nwok。鄰接：有邊/弧相連的兩個頂點之間的關系。無向圖中存在(vi,vjvj鄰接于vi。無向

有向圖的定

圖的定義和基本2.圖的基

點v和w互為鄰接點；和頂點v關聯(lián)的邊的數(shù)目定義為v；頂點的入度(InDegree)是以頂點v為弧頭的弧的數(shù)目，記ID(v)；頂點的度記為TD(v)，例：ID(V2)=2，TD(v)=OD(v)+圖的2.圖的基本術vvPhvvvi,imv(，v,i，v)和(vi,j，vi,j+1)∈E，1≤j≤m-1都是圖中的邊。路徑的長度是路徑上的邊或弧的圖的定2.圖的基路徑：接續(xù)的邊構成的頂點序路徑長度：路徑上邊或弧的數(shù)目/權值之和回路(環(huán))：簡單路徑：簡單回路簡單環(huán)：path在圖形G中，相異兩點間所經(jīng)過的邊稱為路徑，如下圖中，A到E的徑有{(A,B),(B,E)}、{(A,C),(C,E)}或{(A,B),(B,D),(D,E)}等路徑，它有一條路徑A AAsimplepath指除了起點(第一個節(jié)點)與終點(最后一個節(jié)點)外的所有節(jié)點都不相同的路徑。亦即路徑不會有循環(huán)現(xiàn)象起點及終點的A中，{(,BDE,,A起點及終點，所以是一個。AABCBCDEDE圖圖上圖(B)的A為簡單路徑，路徑CEB為簡單路徑BDE,B就不是簡單路徑(即為循環(huán)路徑)循環(huán)循環(huán)cycle起點和終點皆相同的路徑。例如下圖的{B,D, ,B}起點及終點都是BAABBCDE圖的2.圖的基都是連通的，則稱圖G為連通圖(ConnectedGraph)。量(ConnectedComponent)；連通圖的連通分量是它本身圖的圖6.3連通圖 圖的定義和基圖的2.圖的基有向圖G中，如果從vi到vj有路徑，則稱頂點vi和頂點vj是連通的；若圖中任意兩個頂點之間都存都有路徑，則稱此有向圖為強連通圖。有向圖中的極大連通子圖稱作該有向圖的強連通分量。例如，圖6.5中的G5就是一個強連通圖。而G6就是非圖的定義和基圖的2.圖的基 圖G6及兩個連通分連通圖（強連通圖（Strongly在無（有）向圖GVE中，若對任何兩個頂點v、u存在從v到u的路徑，則連通圖（強連通圖（Strongly 圖 圖無向圖G的極大連通子圖( alconnectedsubgraph)稱極大連通子圖意思是：該子圖G通子圖，將G任何不該子圖中的頂點加入，子圖不再連通非 V1圖 V2

連通分 強連G的極大強連通子圖稱為G強連強連通分圖的定義和基圖的2.圖的基本術V2?V1，E2?E1，即V2為V1的子集，E2為E1子子兩GV，{）、G（V，E），若V V，E1稱G的。例:(b)、(ca子 圖的定義和基圖的2.圖的基連通圖G的生成樹，是包含G的全部n個頂點的一個極小連點之間有了第二條路徑。一棵有n個頂點的生成樹有且僅有(n-1)條邊。如果一個圖有n個頂點和小于(n-1)條邊，則是非連通圖。如果它多于(n-1)條邊，則一定有環(huán)。但圖的定義和基圖的定義和基2.圖的基本術如果一個有向圖有且僅有一個頂點的入度為0，其他頂點的入度均為1，則這個圖是一棵有向樹。當一個有向圖有多個頂點的入度為0時，它的生成森林則由多棵有向樹構成。這個生成森林含圖的定義和基圖的定2.圖的基圖6.7連通圖G3的生成 圖6.8有向圖G7及生成森極小連通子圖：該子圖是G的連通子圖，在該子刪除任何一條邊，子圖不再連通生成樹：包含無向圖G所有頂點的極小連通子圖。集合連通圖 G1的生成6.2圖的定義和基本圖的定義--2.圖的抽象數(shù)據(jù)類型定ADT類型標識符CreateGraph(&G,V,VR)//初始條件：V是圖的頂點集，VR是圖中弧(或InitGraph(&g); /*初始化圖即構造一個空圖*/) 圖的定義和基圖的定義圖的定義和基GetVex(G,x);//在圖G中查找到頂點x并返回x的值PutVex(&G,v,value);/*為頂點v賦值*/

圖的定義--2.圖的抽象數(shù)據(jù)類型定InsertArc(&G,v,w);//若G是有向圖，則增加弧//若G是無向圖，則增加弧<v,w>和DeleteArc(&G,v,w);//若G是有向圖，則刪除弧//若G是無向圖，則刪除弧<v,w>和 //返回v的第一//若沒有鄰接NextAdjVex(G,x,w);//返回v的(相對于w的)下一個鄰//若w是v的最后一個鄰接頂點圖的定義和基圖的定義--2.圖的抽象數(shù)據(jù)類型定}ADT

V(G)是頂點有限集合，常用字母或者自然數(shù)(頂點)來標識圖中頂點。規(guī)定第i個頂點，即為i的頂點用vi表示；E(G)是圖中邊的集合，它確定了圖G的數(shù)據(jù)元間的關系。6.36.3(5)圖的初始條件：圖G存在操作結果：對圖進行深度優(yōu)先遍初始條件：圖G操作結果：對圖進行廣度優(yōu)先遍6.4圖 順 結構 數(shù)組表示法（鄰接矩陣鏈 結構 多重鏈鄰鄰接鄰接多鏈鄰接矩陣(數(shù)組)表示鄰接鄰接矩

圖 與操–鄰接矩陣（AdjacencyMatrix）是用兩個數(shù)組來 數(shù)組（鄰接矩陣）表示 設圖AVEn個頂點，則圖的鄰接矩陣是一個二維數(shù)組A.Edge[n][n]，定義為：AA.Edge[i][j]<i,j>E或者(i,j否則無向圖的鄰接矩陣表示 頂點表：（v1v2v3v4 A.Edge 分析1：無向圖的鄰接矩陣是對稱分析2：頂點i的度＝第i1的個數(shù)；有向圖的鄰接矩陣表示 A

A.Edge=

(v1v2v3v4 注：注： 頂點的入度=第i列 頂點的度=第i行 和+第i列 圖圖與操鄰接矩法法網(wǎng)（ 圖）的鄰接矩陣表示 無邊（弧定義為：A.Edge[i][j <vi,vj>或（vi, 無邊（弧

(0

v2

v4v5v6 ∞

N.Edge

∞0 ∞∞8∞0∞∞∞ ∞∞∞ 03∞∞ 圖的與操鄰接矩陣--2.網(wǎng)的鄰接矩00000000 00 00 0圖 與操鄰接矩陣--3.鄰接矩陣表示法的特 。圖 與操鄰接4.鄰接矩陣表示法的優(yōu)缺–用鄰接矩陣方法圖，很容易確定圖中任意兩個頂點之間是否有邊相連（鄰接），但要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大，同時，鄰接矩陣空間為O(n2)，所以適用于稠密圖。鄰接矩陣 表//用兩個數(shù)組分 頂點表和鄰接矩#defineMaxInt#defineMVNum100typedefintArcType;typedefstruct{

//表示極大值，即//最大頂//假設頂點的數(shù)據(jù)類型為字//假設邊的權值類型為整 //

//鄰接//圖的當前點數(shù)和邊圖 與操鄰接矩陣--5.算法6.1 inti;if(G.vexs[i]==v)returni;return-1;}圖 與操鄰接矩陣--5.鄰接voidDisplayAdjMatrix(AMGraphG) int }//for

圖 與操鄰接矩陣--5.鄰接矩陣操voidCreateUndirectedGraphAdj(AMGraph intVerTexTypefor(k=0;k<pg- {//

//邊數(shù)圖 與操鄰接矩陣--5.voidCreateUndirectedGraphAdj(AMGraph //pg->arcs[i][j]=1;pg-pg->arcs[i][j]=w;pg-pg->arcs[i][j]=1;/*創(chuàng)建有向圖的鄰接矩陣*/pg->arcs[i][j]=w;*創(chuàng)建有向網(wǎng)的鄰接矩陣*/} 45ABCABA45ABCABACADBCCD【算法思輸入總頂點數(shù)和總邊數(shù)依次輸入點的信息存入頂點表初始化鄰接矩陣構造鄰接矩陣45A45ABCABACADBCCDStatusCreateUDN(AMGraph//采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng) for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(j=0;j<G.vexnum;++j)G.arcs[i][j]=MaxInt;for(k=0;

//輸入總頂點//依次輸入//初始化鄰接矩陣，邊的權值均置為極大//構造鄰接矩//輸入一條邊依附的頂點及iLocateVex(Gv1);jLocateVex(Gv2);//確定v1和v2在GG.arcs[i][j]=w;//邊<v1,v2>的權值置為return

//置<v1,v2>的對稱邊<v2,v1>的權值為45ABCA45ABCABACADBCCDinti;returni;return-1;}鄰接矩陣表 圖 與操圖的鄰接 鄰接表(AdjacencyList)是圖的一種順序 圖 與操鄰接表--1.圖的鄰接 的邊結點，info域和邊或弧相關的信息，如權值。圖6.11鄰接表（鏈式）表示 表結對每個頂點建立一個單鏈表表結頭結每個單鏈表有一個頭結點（設為2個域），存Vi信息每個單鏈表的頭結點另外用每個單鏈表有一個頭結點（設為2個域），存Vi信息每個單鏈表的頭結點另外用順結。儲頂點vi信

數(shù)據(jù)域，邊有關信（如權值無向圖的鄰接表 0 1

3 1^31^

注：鄰接表不唯一，因各個邊結點的鏈入順序是任空間效率為O(n+2e)若是稀疏圖(e<<n2)，比鄰接矩陣表示法O(n2)省空TD(Vi)=單鏈表 的結點個圖 與操鄰接表--3.無向圖的鄰接 法的特（1）第i個鏈表中結點的數(shù)目為第i 圖 與操鄰接表--–有向圖的鄰接表不方便查找以vi為弧頭的節(jié)點數(shù)，為2121102002 102002 (a)無向圖G1的鄰接 1

01無向圖01

10(c有10

有向圖–僅以頂 作為信息輸入，時間復雜度為O(n+e)^有向圖的鄰接表^空間效率為

鄰接^ 2 1^210^0^

逆鄰接3^0^0^2^^3^3出度OD(Vi)＝單鏈出邊表中 入度ID(Vi)＝鄰接點域為Vi的弧個數(shù)度：TD(ViODVi+IDVi圖 與操鄰接表--4.有向圖的鄰接 法的性 已知某網(wǎng)的鄰接（出邊）表，請畫出該網(wǎng)1152

鄰接表 表#defineMVNum //最大typedefenum{DG,DN,UDG,UDN}typedef int ode*OtherInfo typedefstructode*}VNode,typedefAdjListint GraphType

//邊結//該邊所指向的頂點的//指向下一條邊的指//和邊相關的//頂點信//指向第一條依附該頂點的邊的//AdjList表示鄰接表類//鄰接//圖的當前頂點數(shù)和//圖的類型采用鄰接表表示法創(chuàng)【算法思NU。 for(i=0;i<G.vexnum;++i){cin>>G.vertices[i].data;for(k=0; i=LocateVex(G,v1);j=LocateVex(G,//將新結點

////////生成一個新的邊結點//鄰接點序號為p1->nextarc=G.vertices[i].firstarc;//將新結點

//鄰接點序號為p2->nextarc=G.vertices[j].firstarc;return鄰接表表示法的特 優(yōu)點：空間效率高，容易尋找頂點的鄰接鄰接矩陣與鄰接表表示法的^1^123^024^134^024^1312（v1v2v3v4 0101010101010111010101110鄰接矩陣與鄰接表表示法的關 區(qū)別 接矩陣的空間復雜度為O(n2),而鄰接表的空間復圖 與操鄰接表--鄰接表intLocateVex(ALGraphG,VerTexType inti;if(G.AdjList[i].data==v)returni;return-1;圖 與操voidCreateUndirectedGraphLink(ALGraph intVerTexTypeodefor(i=0;i<=pg- /*n為頂點數(shù) scanf("%c",&pg->AdjList[i].data);/*構造頂點信息pg- }//forfor(k=0;k<pg-

/*e為邊數(shù)/*確定兩個頂點在圖G中的位置 /*創(chuàng)建無向圖的鄰接表 ode ode));s-s->nextarc=pg->AdjList[i].firstarc;pg-圖 與操)voidCreateUndirectedGraphLink(ALGraph ode ode));s-s->nextarc=pg->AdjList[j].firstarc;pg-/*創(chuàng)建有向圖的鄰接表 ode ode));s-s->nextarc=pg->AdjList[i].firstarc;pg-/*創(chuàng)建有向圖的逆鄰接表 ode ode));s-s->nextarc=pg->AdjList[j].firstarc;pg-}//for圖 與操voidDisplayAdjList(ALGraph intodeprintf("for(i=0;i<G.vexnum;i++){while(p!=NULL){printf("->%d",p->adjvex);p=p-鏈表(OrthogonalList)--用于頂點結點表中的結(節(jié))vex:頂點的數(shù)據(jù)域，保存頂點的數(shù)firstin:頂點的指針域，指向第一個以為弧頭(head)的弧結

firstout:頂點的指針域，指向第一個vex為弧尾(tail)的info:弧的數(shù)據(jù)域(如權值)，保存弧的權值等tailvex:弧尾結點(tail)的位(地址)headvex:弧頭結點(head)的位(地址)

hlink:指向相同弧頭結點(head)下一個弧結點tlink:指向相同弧尾結點(tail)下一個弧結點鏈表(Orthogonal鏈表(OrthogonalList)--圖 與操 typedefstruct inttailvex,headvex;odechar VexInfo

/*最大頂點數(shù)/*標記和邊(或弧)的相關信息/*頂點的信息ode*firstin,*firstout;//標記vi的第一}VexNode /*頂點數(shù)和邊數(shù)圖 與操鏈表--圖 /*建立有向圖 鏈表。{ for(i=0;i<G.vexnum;i++){

um;j++){

}//for ode ode}; G.vexs[n].firstout=p;}}

//for

//將p連 建 鏈表的時間復雜度是O(n+e)圖 與操 #defineMAX_VERTEX_NUMintstructArcBox

/*最大頂點數(shù)infoTypetypedefstructVexNode{VextexTypevex;

/*標記和邊(或弧)的相關信息//頂點的信息 稱用ArcBox*firstin,*firstout;//標記vi的第一個鄰接節(jié)點的指VexNode /*頂點數(shù)和邊數(shù)鄰接多重表---用于無data:結點的數(shù)據(jù)域，保存結點的數(shù)據(jù)值firstedge:結點的指針域，給出自該結點出的第一條邊的邊結點的地址邊結ivex:本條邊依附的一個結點的地址ilink:依附于該結點（地址由ivex給出）jvex:本條邊依附的另一個結點的地

info:邊結點的數(shù)據(jù)域，保存邊的過過鄰接多重6.56.5 以及船上傳教士人數(shù)不能少于野人以及船上傳教士人數(shù)不能少于野人在每一次渡河后，都會有幾種渡河方案供，究竟哪種方案最有利？這就是搜依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，

解路搜索空全狀態(tài)空 8在一個3×3的方框內放有8個的小方塊，緊鄰空位的小方塊2323765搜索引擎的兩種基本抓

搜索引擎蜘蛛通 網(wǎng)頁，獲得頁 后 爬行索排序返搜索引擎的搜索引擎的兩種基本抓位的繼搜索引擎的兩種基本抓

的規(guī)兩種策略結合=先廣后深 URL的權重高，就采用深URL權重低，就采用寬度優(yōu)先或者不 初始狀態(tài)為i ，改visited[i]為1，防止被多圖圖常用的遍深度廣度深度優(yōu)先搜DFSDepth_First基本思想：——仿樹的先序起起DFSv1→v2→v4→v8→v5→v3→v6→v7深度優(yōu)先搜索的步 簡單起始點 深度優(yōu)先搜索練 142142365深度優(yōu)先搜索的步 詳細在圖中某一起始頂點v，由v出發(fā)，它的任一鄰接起 點再從w1出發(fā)，與w1接但還未被過的頂點然后再從w2出發(fā)，進行類似的鄰接頂點都被過的頂點u深度優(yōu)先搜索的步 詳細 過的頂點，看是否還有起 它沒有 的鄰接頂點如果有， 此頂點，之 如果沒有，就再退回一步進圖中所有頂點都 過為止123456101110123456101110021000103100010410000150110006000100123456

——開輔助數(shù)組visited[n0001110101110000000000111010111000000010000110000111110111111鄰鄰142365DFSDFS討論2：DFS算法如何編程？——可以用遞歸算voidDFS(AMGraphG,intv){cout<<v;visited[v]=true;for(w=0;w<G.vexnum;w++)

//圖G為鄰接矩陣 第v//依次檢查鄰接矩陣v所在的if((G.arcs[v][w]!=0)&&(!visited[w]))DFS(G,w);//w是v的鄰接點，如果w ，則遞歸調用}討論3：在圖的鄰接表中如何進行DFS？—照樣借用visited[n0起 23DFSv0→v1→DFSv0→v1→v2→00001000001000110011101111123討論4：鄰接表的DFS算法如何編voidDFS(ALGraphG,intv){cout<<v;visited[v]=true;

——仍可用遞歸算//圖G為鄰//第v個頂if(!visited[w])DFS(G,w);}}

//邊結點//表示w是v的鄰接//如果w未，則遞歸調用//p指向下一個邊結DFS算法效率分 用鄰接表來表示圖，雖然有2e個表結點，但只需掃描e個結點即可完成遍歷，加 問n個廣度優(yōu)先搜BFSBreadth_First基本思想：——仿樹的層次遍歷過起B(yǎng)FSv1→v2→v3→vvv6→v→v8廣度優(yōu)先搜索的步 簡單 了起始點v之后，依 v的鄰接點然后再依 這些頂點中未 過的鄰接點直到所有頂點都 過為止 1從圖中某個頂點v出發(fā) v，并visited[v]的值為true，然后將v進隊②依次檢查u的所有鄰接點w，如果 輔助隊還需再開一輔助隊起入隊鄰鄰接v2 過BFS歷【算法描述voidBFS(GraphG,intcout<<v;visited[v]=true;EnQueue(Q,DeQueue(Q,

第v個頂//輔助隊列Q初始化，置//v//隊列非//隊頭元素出隊并置為 //w為u的尚 的鄰接頂cout<<w;visited[w]=

EnQueue(QwwBFS算法效率分 如果使用鄰接矩陣，則BFS對于每一個 到的頂，都要循環(huán)檢測矩陣中的整整一行（n個元素），總用鄰接表來表示圖，雖然有2e個表結點，但只需掃描e個結點即可完成遍歷，加問n個頭結點的時間，練 深度先搜索從頂點3121256^2^14^^1^3562345^6^DFS與BFS算法效率比 空間復雜度相同，都是O(n)(借用了堆?；蜿犃?補充：ACM算法設計-- 6.66.6最短拓撲關鍵最小生成 生成樹：包含圖G所有頂點的極小連通子圖（n-1條邊）連通

G1的生成畫出下圖^1^123^024^134^024^13鄰接表無向無向連4生

生 求最小生成 首先明確有n個頂點、n-1條邊。目目標構造最小生成樹的準 必須只使用該網(wǎng)中的邊必須使用且僅使用n-1條邊來聯(lián)結網(wǎng)絡中的n個不能使用產生回路最小生成樹的典型用 城市可能有n(n-1)/2條線路，那么，如何選擇n–1條線路，使總費用最顯然是一個生成樹數(shù)學補充：貪心算法(Greedy。找零錢問題這就是在使用Knapsack問題(0/1 假設小偷的背包可裝30物價重單6371以貪婪算法的觀念來看,第一步要最佳效益的商品2我們知道,物品1最劃算,故5公斤全背包.(背包還可以裝25公斤3再來考慮物品3,一樣全部放入背中.(背包還可以裝5公斤4最后考慮物品2,再放入5公斤的物品即完5最大利益為220物價重單637若此若此時商品改成不可分割,也就是說,對一個商品來要不就是全取,要不就是不此時,貪婪算法不一定能求得最大利因為：小偷的背包可以裝下30因為：小偷的背包可以裝下30物價重1523貪貪婪算法:先取物品1,再取物品3;但物品2,不可再選否則背包會斷故以貪婪算法所得到的最好的利益為190但最佳的利益為物品2+物品3=200Knapsack問題(0/1 (Knapsack– fractionalknapsackproblem(OptimalKnapsack問題(0/1 Knapsack問題(0/1 Approximatesolutions,選取C選取CABE-D選取CEDBA--選取ABCDE--123Prim（普里姆）Kruskal（克魯斯卡爾）Prim算法:歸并頂點，與邊數(shù)無關，適于Kruskal算法：歸并邊，適于稀疏普里姆算法的基本思想－－歸并頂 NVE1.從某頂點u0出發(fā)，選擇與它關聯(lián)的具有最小權值的邊(u0,v)，將其頂點加入到生成樹的頂點集合2.每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權值最小的邊(u,v),把它的頂點3.直到所有頂點都加入到生成樹頂點集合UT(G)=應用普里姆(Prim)算法構造最小生成ExampleforExamplefor克魯斯卡爾(Kruskal)算法的基本思想－NVE1.n個頂點，沒有邊T={V,},每個頂點自 通分量2.E中選最小權值的邊,若該邊的兩個頂點落在不同的連通分量上，則加入T中；否則舍去，重3.重復下去，直到所有頂點在同一連通分量上T(G)=O(|e|log應用克魯斯卡爾算法構造最小生成樹 √ExampleforExamplefor ysisofAlgorithms-Chapter BB）兩種常見的最短

EdsgerW.一、單源最短路徑—用Dijkstra（迪杰斯特拉）算RobertW.二、所有頂點間的最短路徑—用Floyd（弗洛伊RobertW.一頂點到余各頂

最短路 型應用--計算機網(wǎng)絡路最短路 型應用—機器人探型應用—游戲型應用—游戲開最短路DijkstraDijkstra算A*算Dijkstra算法的改進—A*算法（靜Dijkstra算法的改進—A*算法（靜態(tài)環(huán)境

Dijkstra算法的改進—D*算法（動態(tài)環(huán)境 學D*

型應用—火星探測從v0到其余各點的最短路徑--按路徑長度遞增次序求 (v0,(v0,(v0,v4,(v0,v4,v3,無∞504315 504315

1060

0Dijkstra算法的思 504315 504315 選擇：從這些路徑中找出一長度最短的路徑（v0,u）若在圖中存在?。╱,vk）則以路徑（v0,u,vk）（v0,vk）在調整后的各條路徑中，再找度最短的路徑，依此類推結構結構（頂點個數(shù)為主：鄰接矩陣G[n][n](或者鄰輔–數(shù)組S[n]：記錄相應頂點是否已被確–數(shù)組D[n]：記錄源點到相應頂點路徑長 –數(shù)組Path[n]：記錄相應頂點的前驅

0 1

5 5算法初始化結

212v=v=v=v=v=v=SD0∞∞?0?00【算法思初始化將v0D[i]=G.arcs[v0][vi]，(vi∈V?如果v0和頂點vi之間有弧，則將vi的前驅置為v0Path[iv0，否則Path[i1②選擇下一條最短路徑的終點vkD[k]=Min{D[i]|vi∈V?【算法思想】 i

k若S[i]=falseD[k]+G.arcs[k][i]<D[i]，則D[i]=D[k]+G.arcs[k][i];Path[i]=k;。⑤重復②～n?1次，即可按照路徑長度的遞增，逐個求得從v0到圖上其余各頂點的最短路徑Dijkstra算法的思 ABCABCDEFGH例5例504315 (v0,v2)+(v0,v2)+ 從v0到各終點的長度和最短路∞∞∞∞∞{v0,{v0,{v0,v4,s{v0,v200 30

S之外的當前短路徑之頂S之外的當前短路徑之頂 0算法流程求最短長度

初始化過程初始化過程 minmin=INFINTY;w< ! D[w]<v=w;v=w; 更新v0到V-S中頂點的

w<G.vexnum S[v]=true;!S[w] S[v]=true;Y【算法描voidShortestPath_DIJ(AMGraphG,int//用Dijkstra算法求有向網(wǎng)G的v0頂點到其余頂點的最短for(v=0;v<n;++v){S[v]=false;D[v]=

//n為G中頂點//n個頂點依次初始//S初始//將v0到各個終點的最短路徑長度初if(D[v]<MaxInt)Path[v]=v0;//v0和v之間有弧，將v的前驅置為elsePath[v]=-

//如果v0和v之間無弧，則將v的前驅置為-//將v0加入//源點到源點的距離為

時間復雜度/*―開始主循環(huán)，每次求得v0到某個頂點v的最短路徑，將v加到S集for(i=1;i<n;++i){min=MaxInt;{v=w;

//對其余n?1個頂點，依次進行計//選擇一條當前的最短路徑，終點為//將v加入for(w=0;w<n;++w)//更新從v0出發(fā)到集合V?S上所有頂點的最短路徑長Path

//更新//更改w的前驅為AllpairsshortestFloyd’sAlgorithm:AllpairsshortestInaweightedgraph,findshortestpathsbetweeneverypairofSameidea:constructsolutionthroughseriesofmatricesD(0),D(1),…usinganinitialsubsetoftheverticesasintermediaries.43164316115234Floyd’sFloyd’sAlgorithm:AllpairsshortestBottom-upapproachObjectivefunction:LetAk(i,j)=lengthofashortestpathfromvertexitovertexjwithintermediatenodevk.RecurrencerelationAk(i,j)=Min{Ak-1(i,j),Ak-1(i,k)+Ak-1(k,j)Boundarycondition:A0(i,j)=c(i,j) i,j.Answer:An(i,Timecomplexity:Spacecomplexity:Floyd’sFloyd’s59ExampleforFloyd’s59ExampleforFloyd’s469469ExampleExampleforFloyd’s77用有向圖來描述一個工程或系統(tǒng)的進行一個工程可以分為若干個子工程，只要完成了這些子（活動），就可以導致整個工程的完①AOV網(wǎng)Vertices)—用頂點表示活動的網(wǎng)②AOE網(wǎng)Edges)—用邊表示活比比如教學計劃的哪些課程是必須先修的，哪些課程是可以并行學習的在游戲的情中，描述各個分支情節(jié)之間的關分支情節(jié)之間，存在著一定的先決條件約束，即有些情節(jié)必須在其他情節(jié)完成后方可開始發(fā)展，而有些分在AOV網(wǎng)中，不應該出現(xiàn)有向環(huán)路，否則，頂點的后關系就會進入死循環(huán)。即情節(jié)將不能正確發(fā)情情情先決條遭遇強無受買看醫(yī)治情 情 先決條遭遇無受買治教學計劃的高等C1,C2C3,C2C5,C4C4,C9對學生選課工程圖進行拓撲排序，得到的拓撲有序序C1,C2,C3,C4,C5,C6,C8,C9,或C1C8C9C2C5C3C4C7離散

數(shù)據(jù)程序學生課程學習工SourceremovalalgorithmforTopologicalsorting拓撲拓撲排序算法的思想－重復選擇沒有直接前思想－思想－重復選擇沒有直接前驅的頂點，即V(in-(i.e.source-removal輸入AOV網(wǎng)絡。令n為頂點在AOV網(wǎng)絡中選一個沒有直接前驅的頂點,并輸出之從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊重復以上2、3步直到AO拓撲排序的過 最后得到拓撲C4C0,C3,C2,C1C5。滿足圖Solutionfor1-(1).ApplytheDFS-basedalgorithmtosolvethesortingproblemforthefollowingdigraphs:(a)andSolutionfor1-(1).ApplytheDFS-basedalgorithmtosolvethesortingproblemforthefollowingdigraphs:(a)andSolutionfor1-(2).Applythesource-removalalgorithmtosolvethesortingproblemforthefollowingdigraphs:(a)andSolutionfor Applythesource-removalalgorithmtosolvethetopologicalsortingproblemforthefollowingdigraphs:(a)and(b).關鍵AOE網(wǎng)絡：定義結點為事件，有向邊的指向表示事件的執(zhí)行次序。單位是術語ABAB活動（有向邊）：它的權值定義為活動進行所需要的時間。方起始結點事事件的最早發(fā)生時間（Ve(j)）：從起點到本結點的最長的路徑。意味事件的最遲發(fā)生時間（Vl(j)）：不影響工程的如期完工，本結點事件必jjk活動的最早開始時間：eaiVej活動的最遲開始時間：laiVlkdutjk關鍵事件的最早發(fā)生時間（Ve(j)）：從起點到本結點的最長的路徑。意味著事件能夠發(fā)生的時(AB的AB活動的最早開始時間：e(aiVejjk活動的最遲開始時間laiVlkdutjjk關鍵活動：最早開始時間＝最遲開始時間2437Vn關鍵路徑：從源點到收點的最長的一條路徑，或者全部由2437Vn1起點 Ve(Vj)881、5、12、88的最大值

Vl(Vj)=取10-2、10-4、10-3、10-7小值310長路徑起點

Ve(j)及Vl(j)）的求 收

37

VnVe(Vj)=3、5、12、88的最大值

Vl(Vj10-2、10-4、10-

、10-7的最小值

收

Vj

Vn Ve(Vj)=Vj的起始結點的最早發(fā)生時間+各自的邊的權值中的和的最大值88

Vl(Vj終止結點的最遲發(fā)生時間-各自的邊的權值的差的最小值3 0 0 0

10V15

131

212

57、

1、設每個結點的最早發(fā)生時間為0，將入為零的結點進2、將棧中入度為零的結點V取出，并一棧，用于形成逆向拓撲排序的序列。3、根據(jù)鄰接表找到結點V的所有的鄰，將結點V的最早發(fā)生時間+活動的權值得較；如果該值大，則用該值取代原最早發(fā) 55正向拓撲排序

4、反復執(zhí)行2、3；直至?？諡? 0 V1350

0StatusTopologicalsort（StatusTopologicalsort（ALGraphG,Stack{//對各頂點求入度，建立入度為零的棧Initstack（T）；count=0;ve[0..G.vexnum-1]=0;whilefor（p=G.vertices[i].firstarc;p;p=p-{k=p-if（!（--indegree[k]））Push（S,k）;if（ve[j]+*（p->info）>ve[k]）ve[k]=ve[j]+*（p->info）;}}if（count<G.vexnum）returnERROR;elsereturnOK;}//棧T為求事件的最遲發(fā)生時間11 13

21

3257V15

15

22正向拓撲排序8 28 8

利用V1358

22

遲發(fā)生時間的執(zhí)行步1、設每個結點的最遲發(fā)生時間為收點10、00V1、5

V243、1V3、165

V5 22

V6

的最早發(fā)生2、將棧中的結點V3、根據(jù)逆鄰接表找到結點V的所有的起始結點，將結點V的最遲發(fā)生時間-4、反復執(zhí)行2、3；直至?？漳嫦蛲負渑判颍簩嵗氖录Y點的最早發(fā)生時

最早

最遲Vl(k)-dut(j,k21 26 3

關鍵活V1355

23261011V1 3261011V1 2 2551

關鍵活關鍵活 11 3

216 V13 5 55關鍵例8-7對于圖8-17所示的AOE網(wǎng)，要求計算各個事件vk的最早開始時間計算各個事件vk的最晚發(fā)生時間計算各個活動ai的最早開始時間計算各個活動ai的最晚開始時間

v3v

關鍵例8-7對于圖8-17所示的AOE網(wǎng)，要求計算各個事件vk的最早開始時間最早開始時間事057給出整個工關鍵例8-7對于圖8-17所示的AOE網(wǎng)，要求計算各個事件vk的最晚發(fā)生時間最晚發(fā)生時間事07關鍵例8-7對于圖8-17所示的AOE網(wǎng)，要求計算各個活動ai的最早開始時間最早開始時間活00577關鍵例8-7對于圖8-17所示的AOE網(wǎng)，要求計算各個活動ai的最晚開始時間最晚開始時間活507關鍵例8-7對于圖8-17所示的AOE找出所有 關鍵活動有a2,a4,a6,a9,a13a2,a4,a6,a10,a14關鍵路徑為(v0,v2,v3,v4,v6,v9)和(v0,v2,v3,v4,v7,v9)6.7用圖G中的一個頂點表示一個人，兩個人“認識”與否，用代表這兩個人的頂95）99.5%以上的頂點都存在一條路徑長度不超過7的路徑①ViiNm70；SrtvittrtutrSr隊頭頂點u出隊依次檢查u的所有鄰接點w，如果visited[w]的值為false，則將w標記為六度頂路徑長度不超過7的頂點個數(shù)Visit_Num加將w③退出循環(huán)時輸出從頂點Start出發(fā)，到其他頂點長度不超過7的路徑的百分【算法描voidSixDegree_BFS(GraphG,int visited[Start]=true;//置頂點 標志數(shù)組相應分量值為InitQueue(Q輔助隊列Q初始化，置空EnQueue(Q,Start);//Start進隊for(len=1;len<=7&&!QueueEmpty(Q);len++)//統(tǒng)計路徑長度不超過7的頂點個{DeQueue(Q,u);//隊頭頂點u//依次檢查u的所有鄰接點w，F(xiàn)irstAdjVex(G,u)表示u的第一個鄰接//NextAdjVex(G,u,w)表示u相對于w的下一個鄰接點，w≥0表示存在鄰{

//w為u的尚 的鄰接頂

//將w//路徑長度不超過7的頂點個數(shù)加//w}//結束至多7次for//輸出從頂點Start出發(fā)，到其他頂點長度不超過7}有向圖有向圖

Dijkstra算Floyd算鄰接應無向圖的應無向圖的應

廣度優(yōu)先搜索最小生

掌握：圖的基本概念及相關術語和 熟練掌握：圖的兩種遍歷方法DFS和BFSDFS算法熟練掌握：最短路算法（Dijkstra算法）Howtoconstruct ysisadynamicprogrammingIngeneral,dynamicprogrammingmethodhastwoForwardBackwardHowtoconstruct ysisadynamicObjectivefunction(optimalRecurrenceBoundaryTimeSpace19F