1、Email:lidongmei李冬梅北京林業(yè)大學(xué)信息學(xué)院圖第6章數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）線性結(jié)構(gòu) 一個對一個，如線性表、棧、隊列樹形結(jié)構(gòu) 一個對多個，如樹集合 數(shù)據(jù)元素間除“同屬于一個集合”外，無其它關(guān)系圖形結(jié)構(gòu) 多個對多個，如圖邏輯結(jié)構(gòu)目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents掌握：圖的基本概念及相關(guān)術(shù)語和性質(zhì)熟練掌握：圖的鄰接矩陣和鄰接表兩種存儲表示方法熟練掌握：圖的兩種遍歷方法DFS和BFS熟練掌握：最短路算法（Dijkstra算法）掌握：最小生成樹的兩種算法及拓撲排序算法的思想

2、01OPTION02OPTION03OPTION04OPTION05OPTIONtarget目標圖的定義和術(shù)語 圖：Graph=(V,E)V：頂點(數(shù)據(jù)元素)的有窮非空集合；E：邊的有窮集合。無向圖：有向圖：每條邊都是無方向的每條邊都是有方向的完全圖：任意兩個點都有一條邊相連無向完全圖有向完全圖n(n-1)/2 條邊n(n-1) 條邊圖的定義和術(shù)語圖的定義和術(shù)語稠密圖有較多邊或弧的圖。鄰接有邊/弧相連的兩個頂點之間的關(guān)系。存在(vi, vj)，則稱vi和vj互為鄰接點；存在，則稱vi鄰接到vj， vj鄰接于vi 稀疏圖有很少邊或弧的圖。網(wǎng)邊/弧帶權(quán)的圖。關(guān)聯(lián)(依附)：邊/弧與頂點之間的關(guān)系。

3、存在(vi, vj)/ ， 則稱該邊/弧關(guān)聯(lián)于vi和vj頂點的度：與該頂點相關(guān)聯(lián)的邊的數(shù)目，記為TD(v)在有向圖中, 頂點的度等于該頂點的入度與出度之和。頂點 v 的入度是以 v 為終點的有向邊的條數(shù), 記作 ID(v) 頂點 v 的出度是以 v 為始點的有向邊的條數(shù), 記作OD(v)問：當有向圖中僅1個頂點的入度為0,其余頂點的入度均為1，此時是何形狀？答：是樹！而且是一棵有向樹！圖的定義和術(shù)語路徑：接續(xù)的邊構(gòu)成的頂點序列。路徑長度：路徑上邊或弧的數(shù)目/權(quán)值之和?；芈?環(huán))：第一個頂點和最后一個頂點相同的路徑。簡單路徑：除路徑起點和終點可以相同外，其余頂點均不相同的路徑。簡單回路(簡單環(huán))

4、：除路徑起點和終點相同外，其余頂點均不相同的路徑。圖的定義和術(shù)語 非連通圖 連通圖 強連通圖 非強連通圖 V0 V1 V2 V3 V0 V4 V3 V1 V2 V0 V1 V2 V3 V0 V2 V3 V1 V5 V4連通圖（強連通圖）在無（有）向圖G=( V, E )中，若對任何兩個頂點 v、u 都存在從v 到 u 的路徑，則稱G是連通圖（強連通圖）。圖的定義和術(shù)語(a)(b)(c)子圖設(shè)有兩個圖G=（V，E）、G1=（V1，E1），若V1 V，E1 E ，則稱 G1是G的子圖。例:(b)、(c) 是 (a) 的子圖權(quán)與網(wǎng)圖中邊或弧所具有的相關(guān)數(shù)稱為權(quán)。表明從一個頂點到另一個頂點的距離或耗費

5、。帶權(quán)的圖稱為網(wǎng)。圖的定義和術(shù)語連通分量（強連通分量）非連通圖 V0 V2 V3 V1 V5 V4無向圖G 的極大連通子圖稱為G的連通分量。極大連通子圖意思是：該子圖是 G 連通子圖，將G 的任何不在該子圖中的頂點加入，子圖不再連通。 V0 V2 V3 V1連通分量圖的定義和術(shù)語有向圖G 的極大強連通子圖稱為G的強連通分量。極大強連通子圖意思是：該子圖是G的強連通子圖，將D的任何不在該子圖中的頂點加入，子圖不再是強連通的。圖的定義和術(shù)語極小連通子圖：該子圖是G 的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。生成樹：包含無向圖G 所有頂點的極小連通子圖。生成森林：對非連通圖，由各個連通分量

6、的生成樹的集合。 連通圖 G1G1的生成樹圖的定義和術(shù)語目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents六度空間理論你和任何一個陌生人之間所間隔的人不會超過6個，也就是說，最多通過6個中間人你就能夠認識任何一個陌生人。目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents圖的類型定義CreateGraph(&G,V,VR) 初始條件：V是圖的頂點集，VR是圖中弧的集合。 操作結(jié)果：按V和VR的定義構(gòu)造圖G。

7、 DFSTraverse(G) 初始條件：圖G存在。 操作結(jié)果：對圖進行深度優(yōu)先遍歷。 BFSTraverse(G) 初始條件：圖G存在。 操作結(jié)果：對圖進行廣度優(yōu)先遍歷。 目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents圖的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)數(shù)組表示法（鄰接矩陣）鏈式存儲結(jié)構(gòu)多重鏈表鄰接矩陣(數(shù)組)表示法鄰接表(鏈式)表示法重點介紹鄰接表鄰接多重表十字鏈表 建立一個頂點表（記錄各個頂點信息）和一個鄰接矩陣（表 示各個頂點之間關(guān)系）。 設(shè)圖 A = (V, E) 有 n 個頂點，則圖的鄰接矩陣是

8、一個二維數(shù) 組 A.Edgenn，定義為：數(shù)組（鄰接矩陣）表示法鄰接矩陣：A.Edge =（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 00 0 0 0 0分析1：無向圖的鄰接矩陣是對稱的；分析2：頂點i 的度第 i 行 (列) 中1 的個數(shù)；特別：完全圖的鄰接矩陣中，對角元素為0，其余1。0 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 00 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0頂點表：無向圖的鄰接矩陣表示法分析1：有向圖的鄰

9、接矩陣可能是不對稱的。分析2：頂點的出度=第i行元素之和 頂點的入度=第i列元素之和 頂點的度=第i行元素之和+第i列元素之和v1v2v3v4A鄰接矩陣：A.Edge =( v1 v2 v3 v4 )v1v2v3v40 0 0 00 0 0 0 0 0 0 0 0 0 0 0 注：在有向圖的鄰接矩陣中， 第i行含義：以結(jié)點vi為尾的弧(即出度邊）； 第i列含義：以結(jié)點vi為頭的弧(即入度邊）。頂點表：0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 0 1 1 00 0 0 0 0 0 0 1 1 0 0 0 有向圖的鄰接矩陣表示法13定義為：A.Edge i j =Wij 或（v

10、i, vj）VR 無邊（?。﹙1v2v3v4Nv5v65489755鄰接矩陣： N.Edge =( v1 v2 v3 v4 v5 v6 )頂點表： 5 7 4 8 9 5 6 5 3 1 5 7 4 8 9 5 6 5 3 1 網(wǎng)（即有權(quán)圖）的鄰接矩陣表示法6容易實現(xiàn)圖的操作，如：求某頂點的度、判斷頂點之間是否有邊、找頂點的鄰接點等等。n個頂點需要n*n個單元存儲邊;空間效率為O(n2)。 對稀疏圖而言尤其浪費空間。鄰接矩陣表示法的特點缺點：優(yōu)點：/用兩個數(shù)組分別存儲頂點表和鄰接矩陣#define MaxInt 32767 /表示極大值，即#define MVNum 100 /最大頂點數(shù) ty

11、pedef char VerTexType; /假設(shè)頂點的數(shù)據(jù)類型為字符型 typedef int ArcType; /假設(shè)邊的權(quán)值類型為整型 typedef struct VerTexType vexsMVNum; /頂點表 ArcType arcsMVNumMVNum; /鄰接矩陣 int vexnum,arcnum; /圖的當前點數(shù)和邊數(shù) AMGraph; 鄰接矩陣的存儲表示【算法思想】采用鄰接矩陣表示法創(chuàng)建無向網(wǎng)4 5A B C DA B 500A C 200A D 150B C 400C D 600輸入總頂點數(shù)和總邊數(shù)。依次輸入點的信息存入頂點表中。初始化鄰接矩陣，使每個權(quán)值初始化為

12、極大值。構(gòu)造鄰接矩陣。 Status CreateUDN(AMGraph &G) /采用鄰接矩陣表示法，創(chuàng)建無向網(wǎng)G cinG.vexnumG.arcnum; /輸入總頂點數(shù)，總邊數(shù) for(i = 0; iG.vexsi; /依次輸入點的信息 for(i = 0; iG.vexnum;+i) /初始化鄰接矩陣，邊的權(quán)值均置為極大值 for(j = 0; jG.vexnum;+j) G.arcsij = MaxInt; for(k = 0; kv1v2w; /輸入一條邊依附的頂點及權(quán)值 i = LocateVex(G, v1); j = LocateVex(G, v2); /確定v1和v2在G

13、中的位置 G.arcsij = w; /邊的權(quán)值置為w G.arcsji = G.arcsij; /置的對稱邊的權(quán)值為w /for return OK; /CreateUDN 【算法描述】4 5A B C DA B 500A C 200A D 150B C 400C D 600 int LocateVex(MGraph G,VertexType u) /存在則返回u在頂點表中的下標;否則返回-1 int i; for(i=0;iG.vexnum;+i) if(u=G.vexsi) return i; return -1; 4 5A B C DA B 500A C 200A D 150B C 4

14、00C D 600【算法描述】對每個頂點vi 建立一個單鏈表，把與vi有關(guān)聯(lián)的邊的信息鏈接起來，每個結(jié)點設(shè)為3個域；每個單鏈表有一個頭結(jié)點（設(shè)為2個域），存vi信息；adjvexnextarcinfodatafirstarc表結(jié)點頭結(jié)點鄰接點域，表示vi一個鄰接點的位置鏈域，指向vi下一個邊或弧的結(jié)點數(shù)據(jù)域，與邊有關(guān)信息（如權(quán)值）數(shù)據(jù)域，存儲頂點vi 信息鏈域，指向單鏈表的第一個結(jié)點 每個單鏈表的頭結(jié)點另外用順序存儲結(jié)構(gòu)存儲。鄰接表（鏈式）表示法01234注：鄰接表不唯一，因各個邊結(jié)點的鏈入順序是任意的v1v2v3v4v5無向圖的鄰接表表示空間效率為O(n+2e)。若是稀疏圖(eG.vexnu

15、mG.arcnum; /輸入總頂點數(shù)，總邊數(shù) for(i = 0; i G.verticesi.data; /輸入頂點值 G.verticesi.firstarc=NULL; /初始化表頭結(jié)點的指針域為NULL /for 【算法描述】采用鄰接表表示法創(chuàng)建無向網(wǎng)for(k = 0; kv1v2; /輸入一條邊依附的兩個頂點 i = LocateVex(G, v1); j = LocateVex(G, v2); p1=new ArcNode; /生成一個新的邊結(jié)點*p1 p1-adjvex=j; /鄰接點序號為j p1-nextarc= G.verticesi.firstarc; G.vertic

16、esi.firstarc=p1; /將新結(jié)點*p1插入頂點vi的邊表頭部 p2=new ArcNode; /生成另一個對稱的新的邊結(jié)點*p2 p2-adjvex=i; /鄰接點序號為i p2-nextarc= G.verticesj.firstarc; G.verticesj.firstarc=p2; /將新結(jié)點*p2插入頂點vj的邊表頭部 /for return OK; /CreateUDG 采用鄰接表表示法創(chuàng)建無向網(wǎng)鄰接表表示法的特點優(yōu)點：空間效率高，容易尋找頂點的鄰接點；判斷兩頂點間是否有邊或弧，需搜索兩結(jié)點對應(yīng)的單鏈表，沒有鄰接矩陣方便。缺點：v1v2v3v5v4v4432101334

17、1420v5v4v3v2v1231420（ v1 v2 v3 v4 v5 ）v1v2v3v4v50 1 0 1 01 0 1 0 10 1 0 1 11 0 1 0 10 1 1 1 0鄰接矩陣與鄰接表表示法的關(guān)系1. 聯(lián)系：鄰接表中每個鏈表對應(yīng)于鄰接矩陣中的一行，鏈表中結(jié)點個數(shù)等于一行中非零元素的個數(shù)。 對于任一確定的無向圖，鄰接矩陣是唯一的（行列號與頂點編號一致），但鄰接表不唯一（鏈接次序與頂點編號無關(guān)）。 鄰接矩陣的空間復(fù)雜度為O(n2),而鄰接表的空間復(fù)雜度為O(n+e)。鄰接矩陣與鄰接表表示法的關(guān)系2. 區(qū)別：3. 用途：鄰接矩陣多用于稠密圖；而鄰接表多用于稀疏圖結(jié)點表中的結(jié)點的表示

18、：data：結(jié)點的數(shù)據(jù)域，保存結(jié)點的數(shù)據(jù)值。firstin: 結(jié)點的指針域，給出自該結(jié)點出發(fā)的的第一條邊的邊結(jié)點的地址。firstout：結(jié)點的指針場，給出進入該結(jié)點的第一條邊的 邊結(jié)點的地址。十字鏈表-用于有向圖datafirstinfirstout邊結(jié)點表中的結(jié)點的表示：info:邊結(jié)點的數(shù)據(jù)域，保存邊的權(quán)值等。tailvex: 本條邊的出發(fā)結(jié)點的地址。headvex:本條邊的終止結(jié)點的地址。hlink:終止結(jié)點相同的邊中的下一條邊的地址。tlink:出發(fā)結(jié)點相同的邊 中的下一條邊的地址。十字鏈表-用于有向圖infotailvexheadvexhlinktlink十字鏈表十字鏈表-用于無向

19、圖結(jié)點表中的結(jié)點的表示：data:結(jié)點的數(shù)據(jù)域，保存結(jié)點的數(shù)據(jù)值。firstedge: 結(jié)點的指針域，給出自該結(jié)點出發(fā)的的第一條邊的邊結(jié)點的地址。datafirstedge十字鏈表-用于無向圖邊結(jié)點表中的結(jié)點的表示：ivex: 本條邊依附的一個結(jié)點的地址。ilink: 依附于該結(jié)點（地址由ivex給出）的邊中的下一條邊的的地址。jvex: 本條邊依附的另一個結(jié)點的地址。jlink: 依附于該結(jié)點（地址由jvex給出）的邊中的下一條邊的的地址。info: 邊結(jié)點的數(shù)據(jù)域，保存邊的權(quán)值等。mark:邊結(jié)點的標志域，用于標識該條邊是否被訪問過。markivexilinkjvexjlinkinfo十字

20、鏈表目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents圖的遍歷遍歷實質(zhì)找每個頂點的鄰接點的過程圖的特點圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經(jīng)訪問過的頂點。遍歷定義從已給的連通圖中某一頂點出發(fā)，沿著一些邊訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，就叫做圖的遍歷，它是圖的基本運算。人工智能-搜索問題有3個傳教士和3個野人來到河邊準備渡河，河岸有一條船，每次最多可坐2個人。問傳教士為安全起見，應(yīng)如何規(guī)劃擺渡方案，使得在任何時刻，在河兩岸以

21、及船上傳教士人數(shù)不能少于野人人數(shù)？在每一次渡河后，都會有幾種渡河方案供選擇，究竟哪種方案最有利？ 這就是搜索問題。適用情況：難以獲得求解所需的全部信息；更沒有現(xiàn)成的算法可供求解使用。人工智能-搜索問題概念： 依靠經(jīng)驗，利用已有知識，根據(jù)問題的實際情況，不斷尋找可利用知識，從而構(gòu)造一條代價最小的推理路線，使問題得以解決的過程稱為搜索對這類問題，一般我們都轉(zhuǎn)換為狀態(tài)空間的搜索問題。人工智能-搜索問題如傳教士和野人問題，可用在河左岸的傳教士人數(shù)、野人人數(shù)和船的情況來表示。即，初始時狀態(tài)為（3，3，1），結(jié)束狀態(tài)為（0，0，0），而中間狀態(tài)可表示為（2，2，0）、（3，2，1）等等。這類問題的解，就是

22、一個合法狀態(tài)的序列，其中序列中第一個狀態(tài)是問題的初始狀態(tài)，而最后一個狀態(tài)則是問題的結(jié)束狀態(tài)。SgS0解路徑搜索空間全狀態(tài)空間人工智能-搜索問題在一個33的方框內(nèi)放有8個編號的小方塊，緊鄰空位的小方塊可以移入到空位上，通過平移小方塊可將某一布局變換為另一布局。請給出從初始狀態(tài)到目標狀態(tài)移動小方塊的操作序列。2318476512384765例: 8數(shù)碼難題搜索引擎的兩種基本抓取策略預(yù)處理爬行和抓取排名搜索引擎蜘蛛通過跟蹤鏈接訪問網(wǎng)頁，獲得頁面HTML代碼存入數(shù)據(jù)庫。索引程序?qū)ψト淼捻撁鏀?shù)據(jù)進行文字提取、中文分詞、索引等處理，以備排名程序調(diào)用用戶輸入關(guān)鍵詞后，排名程序調(diào)用索引庫數(shù)據(jù)，計算相關(guān)性，然

23、后按一定格式生成搜索結(jié)果頁面。爬行抓取索引排序返回搜索引擎的兩種基本抓取策略搜索引擎的兩種基本抓取策略 -深度優(yōu)先如封建帝位的繼承。不能深入的情況下才考慮其他分支的策略搜索引擎的兩種基本抓取策略 -廣度優(yōu)先類似長幼有序的規(guī)則兩種策略結(jié)合=先廣后深 +權(quán)重優(yōu)先先把這個頁面所有的鏈接都抓取一次再根據(jù)這些URL的權(quán)重來判定URL的權(quán)重高，就采用深度優(yōu)先，URL權(quán)重低，就采用寬度優(yōu)先或者不抓取 。圖常用的遍歷：解決思路：設(shè)置輔助數(shù)組 visited n ，用來標記每個被訪 問過的頂點。初始狀態(tài)為0i 被訪問，改 visited i為1，防止被多次訪問怎樣避免重復(fù)訪問？深度優(yōu)先搜索廣度優(yōu)先搜索基本思想：

24、仿樹的先序遍歷過程。v1v1v2v3v8v7v6v4v5DFS 結(jié)果v2v4v8v5v3v6v7起點深度優(yōu)先搜索( DFS Depth_First Search)深度優(yōu)先搜索的步驟簡單歸納：訪問起始點v;若v的第1個鄰接點沒訪問過，深度遍歷此鄰接點；若當前鄰接點已訪問過，再找v的第2個鄰接點重新遍歷。213456213546深度優(yōu)先搜索練習(xí)深度優(yōu)先搜索的步驟詳細歸納：在訪問圖中某一起始頂點 v 后，由 v 出發(fā)，訪問它的任一鄰接頂點 w1；再從 w1 出發(fā)，訪問與 w1鄰接但還未被訪問過的頂點 w2；然后再從 w2 出發(fā)，進行類似的訪問， 如此進行下去，直至到達所有的鄰接頂點都被訪問過的頂點

25、u 為止。起點深度優(yōu)先搜索的步驟詳細歸納：接著，退回一步，退到前一次剛訪問過的頂點，看是否還有其它沒有被訪問的鄰接頂點。 如果有，則訪問此頂點，之后再從此頂點出發(fā)，進行與前述類似的訪問； 如果沒有，就再退回一步進行搜索。重復(fù)上述過程，直到連通圖中所有頂點都被訪問過為止。起點213546討論1：計算機如何實現(xiàn)DFS？123456100000020000003000000400000050000006000000000000123456010000110000111000111010111110111111鄰接矩陣A輔助數(shù)組 visited n 開輔助數(shù)組 visited n ！123456101

26、110021000103100010410000150110006000100討論1：計算機如何實現(xiàn)DFS？DFS 結(jié)果213456213546void DFS(AMGraph G, int v) /圖G為鄰接矩陣類型 coutv; visitedv = true; /訪問第v個頂點 for(w = 0; w G.vexnum; w+) /依次檢查鄰接矩陣v所在的行 if(G.arcsvw!=0)& (!visitedw) DFS(G, w); /w是v的鄰接點，如果w未訪問，則遞歸調(diào)用DFS 討論2：DFS算法如何編程？可以用遞歸算法！討論3：在圖的鄰接表中如何進行DFS？v0 v1 v2

27、v3DFS 結(jié)果00000123輔助數(shù)組 visited n 1000110011101111照樣借用visited n ！起點0123討論4：鄰接表的DFS算法如何編程？void DFS(ALGraph G, int v) /圖G為鄰接表類型 coutadjvex; /表示w是v的鄰接點 if(!visitedw) DFS(G, w); /如果w未訪問，則遞歸調(diào)用DFS p=p-nextarc; /p指向下一個邊結(jié)點 仍可用遞歸算法用鄰接矩陣來表示圖，遍歷圖中每一個頂點都要從頭掃描該頂點所在行，時間復(fù)雜度為O(n2)。用鄰接表來表示圖，雖然有 2e 個表結(jié)點，但只需掃描 e 個結(jié)點即可完成遍

28、歷，加上訪問 n個頭結(jié)點的時間，時間復(fù)雜度為O(n+e)。結(jié)論：稠密圖適于在鄰接矩陣上進行深度遍歷；稀疏圖適于在鄰接表上進行深度遍歷。DFS算法效率分析基本思想：仿樹的層次遍歷過程廣度優(yōu)先搜索( BFS Breadth_First Search)v1v1v2v3v8v7v6v4v5BFS 結(jié)果v2v3v4v5v6v7v8起點簡單歸納： 廣度優(yōu)先搜索是一種分層的搜索過程，每向前走一步可能訪問一批頂點，不像深度優(yōu)先搜索那樣有回退的情況。 因此，廣度優(yōu)先搜索不是一個遞歸的過程，其算法也不是遞歸的。廣度優(yōu)先搜索的步驟在訪問了起始點v之后，依次訪問 v的鄰接點；然后再依次訪問這些頂點中未被訪問過的鄰接點

29、；直到所有頂點都被訪問過為止。從圖中某個頂點v出發(fā)，訪問v，并置visitedv的值為true，然后將v進隊。只要隊列不空，則重復(fù)下述處理。【算法思想】 隊頭頂點u出隊。 依次檢查u的所有鄰接點w，如果visitedw的值為false，則訪問w，并置visitedw的值為true，然后將w進隊。討論1：計算機如何實現(xiàn)BFS？鄰接表除輔助數(shù)組visited n 外，還需再開一輔助隊列起點輔助隊列v2已訪問過了BFS 遍歷結(jié)果入隊！void BFS (Graph G, int v) /按廣度優(yōu)先非遞歸遍歷連通圖G cout=0; w = NextAdjVex(G, u, w) if(!visite

30、dw) /w為u的尚未訪問的鄰接頂點 coutw; visitedw = true;EnQueue(Q, w); /w進隊 /if /while /BFS 【算法描述】如果使用鄰接矩陣，則BFS對于每一個被訪問到的頂點，都要循環(huán)檢測矩陣中的整整一行（ n 個元素），總的時間代價為O(n2)。用鄰接表來表示圖，雖然有 2e 個表結(jié)點，但只需掃描 e 個結(jié)點即可完成遍歷，加上訪問 n個頭結(jié)點的時間，時間復(fù)雜度為O(n+e)。BFS算法效率分析已知圖的鄰接表，分別給出用深度優(yōu)先搜索和廣度優(yōu)先搜索從頂點3出發(fā)的遍歷序列。 1 2 4 1 3 6 2 4 6 5 3 5 1 6 5 2 1 深度：3，6

31、，5，1，2，4 廣度：3，6，2，5，1，4練習(xí)空間復(fù)雜度相同，都是O(n)(借用了堆棧或隊列）；時間復(fù)雜度只與存儲結(jié)構(gòu)（鄰接矩陣或鄰接表）有關(guān)，而與搜索路徑無關(guān)。DFS與BFS算法效率比較補充：ACM算法設(shè)計-DFS&BFS.ppt目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents圖的應(yīng)用最小生成樹最短路徑拓撲排序關(guān)鍵路徑極小連通子圖：該子圖是G 的連通子圖，在該子圖中刪除任何一條邊，子圖不再連通。生成樹：包含圖G所有頂點的極小連通子圖（n-1條邊）。G1的生成樹連通圖 G1 V0 V4 V3

32、V1 V2 V0 V4 V3 V1 V2 V0 V4 V3 V1 V2最小生成樹v2v4v1v3DFS生成樹鄰接表0123413341420v4v3v2v1v0231420v0v2v1v4v3BFS生成樹v0無向連通圖畫出下圖的生成樹v0v1v2v4v4v3求最小生成樹首先明確：目標：在網(wǎng)的多個生成樹中，尋找一個各邊權(quán)值之和最小的生成樹。使用不同的遍歷圖的方法，可以得到不同的生成樹從不同的頂點出發(fā)，也可能得到不同的生成樹。按照生成樹的定義，n 個頂點的連通網(wǎng)絡(luò)的生成樹有 n 個頂點、n-1 條邊。12必須只使用該網(wǎng)中的邊來構(gòu)造最小生成樹；構(gòu)造最小生成樹的準則必須使用且僅使用n-1條邊來聯(lián)結(jié)網(wǎng)絡(luò)

33、中的n個頂點不能使用產(chǎn)生回路的邊欲在n個城市間建立通信網(wǎng)，則n個城市應(yīng)鋪n-1條線路；但因為每條線路都會有對應(yīng)的經(jīng)濟成本，而n個城市可能有n(n-1)/2 條線路，那么，如何選擇n1條線路，使總費用最少？數(shù)學(xué)模型：頂點表示城市，有n個；邊表示線路，有n1條；邊的權(quán)值表示線路的經(jīng)濟代價；連通網(wǎng)表示n個城市間通信網(wǎng)。顯然此連通網(wǎng)是一個生成樹！最小生成樹的典型用途補充：貪心算法(Greedy Algorithm)算法原理以當前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪心法不要回溯。算法優(yōu)點因為省去了為尋找解而窮盡所有可能所必須耗費的大量時間，因此算法效率高。注意貪婪算法的精神就是“只顧

34、如何獲得眼前最大的利益”,有時不一定是最優(yōu)解。平時購物找錢時，為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當不足大面值幣種的金額時才去考慮下一種較小面值的幣種。 這就是在使用貪心法。找零錢問題補充：貪心算法(Greedy Algorithm)一個小偷，背著一個可載重W公斤的背包行竊.店內(nèi)有數(shù)種不同的商品，不同商品有不同的重量及價值?？紤]商品可以分割的情形(例如，可以只取1/2或1/3個商品)。目的在于求出如何偷到最大利益價值的商品。Knapsack問題假設(shè)小偷的背包可裝30公斤的物品假設(shè)商品價格/重量如下:

35、 物品價值重量單價1505102601063140207Knapsack問題1 以貪婪算法的觀念來看，第一步要找到最佳效益的商品。2 我們知道，物品1最劃算，故5公斤全放入背包。(背包還可以裝25公斤)3 再來考慮物品3，一樣全部放入背包中。(背包還可以裝5公斤)4 最后考慮物品2，再放入5公斤的物品2，即完成工作。5 最大利益為220元。 物品價值重量單價1505102601063140207Knapsack問題物品價值重量150526010314020貪婪算法：先取物品1，再取物品3；但物品2，不可再選取，否則背包會斷裂。故以貪婪算法所得到的最好的利益為190元。但最佳的利益為物品2+物品

36、3=200元。因為：小偷的背包可以裝下30公斤的物品 若此時商品改成不可分割，也就是說,對一個商品來說，要不就是全取,要不就是不取。此時，貪婪算法不一定能求得最大利益。Knapsack問題Prim（普里姆）算法 Kruskal（克魯斯卡爾）算法如何求最小生成樹Prim算法歸并頂點，與邊數(shù)無關(guān)，適于稠密網(wǎng)。Kruskal算法歸并邊，適于稀疏網(wǎng)。設(shè)連通網(wǎng)絡(luò) N = V, E 普里姆算法的基本思想歸并頂點從某頂點 u0 出發(fā)，選擇與它關(guān)聯(lián)的具有最小權(quán)值的邊(u0, v)，將其頂點加入到生成樹的頂點集合U中每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權(quán)值最小的邊(u, v),把它的頂點加

37、入到U中直到所有頂點都加入到生成樹頂點集合U中為止應(yīng)用普里姆算法構(gòu)造最小生成樹的過程設(shè)連通網(wǎng)絡(luò) N = V, E 克魯斯卡爾算法的基本思想歸并邊A構(gòu)造一個只有 n個頂點，沒有邊的非連通圖 T = V, , 每個頂點自成一個連通分量C重復(fù)下去，直到所有頂點在同一連通分量上為止。B在 E 中選最小權(quán)值的邊,若該邊的兩個頂點落在不同的連通分量上，則加入 T 中；否則舍去，重新選擇應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程典型用途：交通問題。如：城市A到城市B有多條線路，但每條線路的交通費（或所需時間）不同，那么，如何選擇一條線路，使總費用（或總時間）最少？問題抽象：在帶權(quán)有向圖中A點（源點）到達B點（終

38、點）的多條路徑中，尋找一條各邊權(quán)值之和最小的路徑，即最短路徑。（注：最短路徑與最小生成樹不同，路徑上不一定包含n個頂點）最短路徑一頂點到其余各頂點兩種常見的最短路徑問題：一、 單源最短路徑用Dijkstra（迪杰斯特拉）算法二、所有頂點間的最短路徑用Floyd（弗洛伊德）算法任意兩頂點之間最短路徑最短路算法典型應(yīng)用-計算機網(wǎng)絡(luò)路由最短路算法典型應(yīng)用機器人探路最短路算法典型應(yīng)用游戲開發(fā)Dijistra算法A*算法+估價值估價值=0靜態(tài)環(huán)境求解最短路最有效的方法 Dijistra算法的改進A*算法（靜態(tài)環(huán)境）Dijistra算法的改進D*算法（動態(tài)環(huán)境）D*算法典型應(yīng)用火星探測器012345554

39、0312100603010102050從v0到其余各點的最短路徑-按路徑長度遞增次序求解源 點終 點最 短 路 徑路 徑 長 度v0v2(v0, v2)10v4(v0, v4)30v3(v0, v4, v3)50v5(v0, v4, v3, v5)60v1無1.初始化：先找出從源點v0到各終點vk的直達路徑（v0,vk），即通過一條弧到達的路徑。2.選擇：從這些路徑中找出一條長度最短的路徑（v0,u）。3.更新：然后對其余各條路徑進行適當調(diào)整：Dijkstra算法的思想5540312100603010102050若在圖中存在?。╱,vk），且（v0,u）+（u,vk）（v0,vk）,則以路徑（

40、v0,u,vk）代替（v0,vk）。在調(diào)整后的各條路徑中，再找長度最短的路徑，依此類推。主：鄰接矩陣Gnn (或者鄰接表)輔：數(shù)組Sn：記錄相應(yīng)頂點是否已被確定最短距離數(shù)組Dn：記錄源點到相應(yīng)頂點路徑長度數(shù)組Pathn：記錄相應(yīng)頂點的前驅(qū)頂點存儲結(jié)構(gòu)（頂點個數(shù)為n）5540312100603010102050v=0v=1v=2v=3v=4v=5StruefalsefalsefalsefalsefalseD01030100Path110100算法初始化結(jié)果 初始化：將源點v0加到S中，即Sv0=true；將v0到各個終點的最短路徑長度初始化為權(quán)值，即Di=G.arcsv0vi，(viVS)；如果

41、v0和頂點vi之間有弧，則將vi的前驅(qū)置為v0，即Pathi=v0，否則Pathi=1。 選擇下一條最短路徑的終點vk，使得：Dk=MinDi|viVS【算法思想】 將vk加到S中，即Svk=true。 更新從v0出發(fā)到集合VS上任一頂點的最短路徑的長度，同時更改vi的前驅(qū)為vk。若Si=false 且 Dk+G.arcskiDi，則Di=Dk+ G.arcski; Path i=k;。 重復(fù)n1次，即可按照路徑長度的遞增順序，逐個求得從v0到圖上其余各頂點的最短路徑?！舅惴ㄋ枷搿縮ikDiDk【算法思想】(v0,v2)+ (v2,v3)(v0,v3)終點 從v0到各終點的長度和最短路徑v1v

42、2v3v4v5vjS之外的當前最短路徑之頂點60v0,v2,v350v0,v4,v330v0,v490v0,v4, v560v0,v4,v3,v55540312100603010102050sv0,v2v0 ,v2 ,v4v0 ,v2 ,v4 ,v3v0 ,v2 ,v4 ,v3 ,v510v0,v230v0,v4100v0, v5例v2v4v3v5100v0, v5012345Dw0 1 2 3 4 510v0,v250v0,v4,v330v0,v4【算法思想】iG.vexnum初始化過程; (i=1;)EndNYw G.vexnummin = INFINTY; (w=0;)w G.vexnu

43、mNY! SwDw minv=w; min=Dw;YN +wN! Sw &(min+G.arcsv,wDw)Dw=min+G.arcsv,w; Pathw=v; +w;NNYYN +i; Sv =true; (w=0;)更新v0 到V- S 中頂點的Dist求最短路徑長度Dist算法流程圖void ShortestPath_DIJ(AMGraph G, int v0) /用Dijkstra算法求有向網(wǎng)G的v0頂點到其余頂點的最短路徑 n=G.vexnum; /n為G中頂點的個數(shù) for(v = 0; vn; +v) /n個頂點依次初始化 Sv = false; /S初始為空集 Dv = G.a

44、rcsv0v; /將v0到各個終點的最短路徑長度初始化 if(Dv MaxInt) Path v=v0; /v0和v之間有弧，將v的前驅(qū)置為v0 else Path v=-1; /如果v0和v之間無弧，則將v的前驅(qū)置為-1 /for Sv0=true; /將v0加入S Dv0=0; /源點到源點的距離為0 【算法描述】時間復(fù)雜度：O(n2)/*開始主循環(huán)，每次求得v0到某個頂點v的最短路徑，將v加到S集*/ for(i=1;in; +i) /對其余n1個頂點，依次進行計算 min= MaxInt; for(w=0;wn; +w) if(!Sw&Dwmin) v=w; min=Dw; /選擇一條

45、當前的最短路徑，終點為v Sv=true; /將v加入S for(w=0;wn; +w) /更新從v0出發(fā)到集合VS上所有頂點的最短路徑長度 if(!Sw&(Dv+G.arcsvwnextarc）; k = p-adjnexr; if （!（- - indegree k ） Push（S, k）; if （ve j + *（ p-info） ve k ） ve k = ve j + *（ p-info）; if （count G.vexnum）return ERROR; else return OK; / 棧 T 為求事件的最遲發(fā)生時間的時候用。實例：求事件結(jié)點的最早發(fā)生時間V1V3V2V5V

46、6V413511222216、568V1V2V3V4V5V6逆向拓撲排序：利用逆向拓撲排序算法求事件結(jié)點的最遲發(fā)生時間的執(zhí)行步驟：1、設(shè)每個結(jié)點的最遲發(fā)生時間為收點的最早發(fā)生時間。2、將棧中的結(jié)點V取出。3、根據(jù)逆鄰接表找到結(jié)點V的所有的起始結(jié)點，將結(jié)點V的最遲發(fā)生時間 - 活動的權(quán)值得到的差同起始結(jié)點的原最遲發(fā)生時間進行比較；如果該值小，則用該值取代原最遲發(fā)生時間。4、反復(fù)執(zhí)行 2、3；直至?？諡橹?。888888V1V3V2V5V6V413511222216、4、40、0、03實例：求事件結(jié)點的最遲發(fā)生時間V1V3V2V5V6V4 實例的事件結(jié)點的最遲發(fā)生時間1351122221304568

47、V1V3V2V5V6V4 實例的事件結(jié)點的最早發(fā)生時間1351102222113568V1V2V1V3V1V4V2V3V3V4V3V6V4V5V4V6V5V6V2V5邊最早發(fā)生時間Ve( j )最遲發(fā)生時間V l( k ) - dut( j , k )00011335562103446566關(guān)鍵活動關(guān)鍵活動關(guān)鍵活動實例：求事件結(jié)點的最遲發(fā)生時間304568V1V3V2V5V6V4實例的關(guān)鍵路徑（粗大的黑色箭頭所示）1351102222113568注意：關(guān)鍵路徑可有多條縮短工期必須縮短關(guān)鍵活動所需的時間目錄導(dǎo)航6.16.26.36.46.56.66.7圖的定義和基本術(shù)語案例引入圖的類型定義圖的存儲結(jié)構(gòu)圖的遍歷圖的應(yīng)用案例分析與實現(xiàn)Contents【案例分析】把六度空間理論中的人際關(guān)系網(wǎng)絡(luò)圖抽象成一個不帶權(quán)值的無向圖G用圖G中的一個頂點表示一個人，兩個人“認識”與否，用代表這兩個人的頂點之間是否有一條邊來表示。這樣六度空間理論問