內(nèi)蒙古大學(xué)《算法與數(shù)據(jù)結(jié)構(gòu)》課件第6章圖

1、6.1 圖的基本概念6.2 圖的存儲(chǔ)結(jié)構(gòu)6.3 圖的遍歷6.4 無(wú)向圖的應(yīng)用6.5 有向圖的應(yīng)用 6.6 最短路徑 第六章 圖 16.1 圖的基本概念圖定義 圖是由頂點(diǎn)集合(V)及頂點(diǎn)間的關(guān)系集合E所組成的一種數(shù)據(jù)結(jié)構(gòu)： Graph(V, E)其中 V = x | x 某個(gè)數(shù)據(jù)對(duì)象 是頂點(diǎn)的非空有限集合； E = (x, y) | x, y V /邊(Edge)集合 或 E = | x, y V /弧(Arc)集合 是頂點(diǎn)之間關(guān)系的有限集合.2無(wú)向圖無(wú)向圖G是由兩個(gè)集合V(G)和E(G)組成的其中：V(G)是頂點(diǎn)的非空有限集;E(G)是邊的有限集 合，邊是頂點(diǎn)的無(wú)序?qū)? 記為(v,w)或(w,

2、v)， 并且（v,w)=(w,v)有向圖有向圖G是由兩個(gè)集合V(G)和E(G)組成的 其中：V(G)是頂點(diǎn)的非空有限集;E(G)是有向邊(也稱 ?。┑挠邢藜?，弧是頂點(diǎn)的有序?qū)Γ洖?，v,w是頂點(diǎn)，v為弧尾(或始點(diǎn))， w為弧頭(終點(diǎn)). 6.1 圖的基本概念3例1245136G2圖G2：V(G2)=1,2,3,4,5,6 E(G2)=, , , , , , 例2157324G16圖G1：V(G1)=1,2,3,4,5,6,7E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)6.1 圖的基本概念4本章只討論簡(jiǎn)單圖,即有兩類圖形不在本章討論

3、之列：6.1 圖的基本概念5(無(wú)向)完全圖(Completed graph) : n個(gè)頂點(diǎn)的有n(n-1)/2條邊的簡(jiǎn)單無(wú)向圖.6.1 圖的基本概念有向完全圖: n個(gè)頂點(diǎn)的有n(n-1)條弧的簡(jiǎn)單有向圖. 稀疏圖(sparse graph)： 邊或弧很少的圖，通常邊數(shù)enlog2n稠密圖(Dense graph): 無(wú)向圖中，邊數(shù)接近n(n-1)/2 ； 有向圖中，弧數(shù)接近n(n-1)6有向網(wǎng)權(quán)與圖的邊或弧相關(guān)的數(shù).網(wǎng)帶權(quán)的無(wú)向圖稱為無(wú)向網(wǎng); 帶權(quán)的有向圖稱為有向網(wǎng);6.1 圖的基本概念無(wú)向網(wǎng)7子圖已知圖G(V,E)和圖G(V,E), 若滿足：VV且 EE 則稱G為G的子圖6.1 圖的基本概念

4、8鄰接點(diǎn)(或相鄰點(diǎn)),關(guān)聯(lián): 如果 e=(u, v) 是 E(G) 中的一條邊，則稱 u 與 v 互為鄰接點(diǎn)或相鄰點(diǎn);稱邊e與頂點(diǎn)u,v關(guān)聯(lián); 如果 a= 是 E(G) 中的一條弧，則稱u鄰接到v 或v鄰接于u,也稱弧a與頂點(diǎn)u,v關(guān)聯(lián).6.1 圖的基本概念9頂點(diǎn)的度（與樹中結(jié)點(diǎn)的度不同）:無(wú)向圖中，頂點(diǎn)v的度是與該頂點(diǎn)v關(guān)聯(lián)的邊數(shù), 記作TD(v)有向圖中，頂點(diǎn)v的度分成入度與出度入度：以該頂點(diǎn)v為終頭的弧的數(shù)目,記為ID(v)出度：以該頂點(diǎn)v為始點(diǎn)的弧的數(shù)目,記為OD(v)一個(gè)頂點(diǎn)v的度等于該頂點(diǎn)的入度與出度之和,即TD(v)=OD(v)+ID(v)6.1 圖的基本概念10(有向)路徑頂點(diǎn)

5、的序列(Vi0,Vi1 , , Vik)， 滿足(Vij-1,Vij)E 或 E，(1jk)路徑長(zhǎng)度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和。簡(jiǎn)單路徑序列中頂點(diǎn)不重復(fù)出現(xiàn)的路徑。回路第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)相同的路徑。簡(jiǎn)單回路除了第一個(gè)頂點(diǎn)和最后一個(gè)頂點(diǎn)外，其 余頂點(diǎn)不重復(fù)出現(xiàn)的回路。6.1 圖的基本概念11V0V1V3V2V0V1V3V0V1V2V0V1V3V06.1 圖的基本概念12連通圖與連通分量ABCDEHMFGIJLK無(wú)向圖G的三個(gè)連通分量ABCDEFGIJLHMK無(wú)向圖G6.1 圖的基本概念在無(wú)向圖中, 若從頂點(diǎn)v1到頂點(diǎn)v2有路徑, 則稱頂點(diǎn)v1與v2是連通的。如果圖中任意一對(duì)頂點(diǎn)都是

6、連通的, 則稱此圖是連通圖。非連通圖的極大連通子圖稱做連通分量。13強(qiáng)連通圖與強(qiáng)連通分量在有向圖中, 若對(duì)于每一對(duì)頂點(diǎn)vi和vj, 都存在一條從vi到vj和從vj到vi的有向路徑, 則稱此圖是強(qiáng)連通圖。非強(qiáng)連通圖的極大強(qiáng)連通子圖稱做強(qiáng)連通分量。強(qiáng)連通圖6.1 圖的基本概念非強(qiáng)連通圖G非強(qiáng)連通圖G兩個(gè) 強(qiáng)連通分量14生成樹：包含圖中全部n個(gè)頂點(diǎn)的一個(gè)極小連通子圖;如果在生成樹上添加1條邊，必定構(gòu)成一個(gè)回路.若圖中有n個(gè)頂點(diǎn)，卻少于n-1條邊，必為非連通圖。ABCDEHM無(wú)向圖G ABCDEHM無(wú)向圖G的生成樹 6.1 圖的基本概念15生成森林：由若干棵生成樹組成，含全部頂點(diǎn)，但構(gòu)成這些樹的邊是最

7、少的。6.1 圖的基本概念FGIJLK生成森林ABCDEFGIJLHMK無(wú)向圖GABCDEHM16class Graph /圖是由一個(gè)頂點(diǎn)的非空有限集合和一個(gè)邊或弧的集合組成。 public: Graph ( ); /建立一個(gè)空?qǐng)D void InsertVertex ( Type & vertex ); / 在圖中插入一個(gè)頂點(diǎn)vertex void InsertEdge(int v1，int v2 ); / 在圖中插入一條邊(v1，v2)或一條弧 void RemoveVertex ( int v ); / 刪除一個(gè)頂點(diǎn)v void RemoveEdge ( int v1，int v2 );

8、/刪除一條邊(v1，v2)或一條弧 int IsEmpty ( ); / 判斷圖中是否有頂點(diǎn)，若無(wú)則返回1，否則返回0 DataType GetWeight ( int v1，int v2 ); / 函數(shù)返回邊(v1，v2)或弧的權(quán)值 int GetFirstNeighbor ( int v ); / 函數(shù)返回頂點(diǎn)位置v的第一個(gè)鄰接頂點(diǎn)的位置，若找不到，則函 / 數(shù)返回-1 int GetNextNeighbor ( int v1，int v2 ); / 函數(shù)返回頂點(diǎn)位置v1相對(duì)于v2的下一個(gè)鄰接頂點(diǎn)的位置,若找不到， /則函數(shù)返回-1圖的抽象數(shù)據(jù)類型說(shuō)明：176.2 圖的存儲(chǔ)表示設(shè)圖 G =

9、 (V, E)是一個(gè)有 n 個(gè)頂點(diǎn)的圖，則G的鄰接矩陣是如下定義的n*n的矩陣AG=Aijn*n：6.2.1 鄰接矩陣或相鄰矩陣若(vi，vj)E或E0 反之Aij=18無(wú)向圖的鄰接矩陣是對(duì)稱的，有向圖的鄰接矩陣不一定對(duì)稱的。19在無(wú)向圖中, 第 i 行 (列) 1 的個(gè)數(shù)即為頂點(diǎn)i 的度。在有向圖中, 第 i 行 1 的個(gè)數(shù)即為頂點(diǎn) i 的出度，第 j 列1 的個(gè)數(shù)即為頂點(diǎn) j 的入度。在鄰接矩陣中：20網(wǎng)（帶權(quán)圖）的鄰接矩陣Aij= 0 i=j 其它 wij 若(vi，vj)E 或 E 21用鄰接矩陣表示的圖的類的定義class AdjMatrix / 非帶權(quán)圖 int n； / 頂點(diǎn)的個(gè)

10、數(shù) int matrixMaxSize MaxSize； / 鄰接矩陣 public: AdjMatrix(int m) n=m； ; / AdjMatrix class AdjMatrix / 帶權(quán)圖 const int INFINITE=； int n； /頂點(diǎn)的個(gè)數(shù) float matrixMaxSizeMaxSize； / 鄰接矩陣 public: AdjMatrix(int m) n=m； 22 void CreateGraph() ; / 建立一個(gè)圖G的鄰接矩陣matrix void LocateVex(v) ; / 確定圖G中頂點(diǎn)v在頂點(diǎn)中的位置 void GetVex(v);

11、/ 得到圖G中頂點(diǎn)v的值 int FirstAdjVex(v); / 確定圖G中頂點(diǎn)出v的第一個(gè)鄰接點(diǎn) int NextAdjVex(v,w); / 確定圖G中頂點(diǎn)出v相對(duì)于w的下一個(gè)鄰接點(diǎn) void DFSTraverse(int v)； / 從頂點(diǎn)v開始對(duì)圖進(jìn)行深度優(yōu)先遍歷 void BFSTraverse(int v)； / 從頂點(diǎn)v開始對(duì)圖進(jìn)行廣度優(yōu)先遍歷; / AdjGraph23假定圖以鄰接矩陣G存儲(chǔ):int AdjMatrix :FirstAdjVex(int v) int w=0; while(wn & matrixvw=0)w+; if(wn) return w; else

12、-1; 算法的時(shí)間復(fù)雜度為：(n)24假定圖以鄰接矩陣G存儲(chǔ) int NextAdjVex(int v,int w) u=w+1; while(un & matrixvu=0)u+; if(ufirstout) /書上沒(méi)有 return gheadv-firstout.adjvex； else return -1; /書上沒(méi)有/ FirstAdjVex轉(zhuǎn)int NextAdjVex(int v，int w) p=gheadv-firstout；while (p & p-adjvex!=w) p=p-link；if (!p | !p-link) return -1； /書上為0else retu

13、rn p-link-adjvex；/ NextAdjVex326.2.3 鄰接多重表表示法 鄰接多重表是只用來(lái)存儲(chǔ)無(wú)向圖的另一種存儲(chǔ)結(jié)構(gòu) .在鄰接多重表表示法中每一條邊只對(duì)應(yīng)一個(gè)邊結(jié)點(diǎn)（EdgeNode），每一個(gè)頂點(diǎn)也對(duì)應(yīng)一個(gè)頂點(diǎn)結(jié)點(diǎn)（VNode）。在邊結(jié)點(diǎn)中，每一條邊對(duì)應(yīng)的邊結(jié)點(diǎn)有五個(gè)域：EdgeNode mark vex1 vex2 link1 link2 33其中：mark是標(biāo)志域，標(biāo)記該邊是否被遍歷 過(guò)；vex1與vex2是該邊所關(guān)聯(lián)的兩個(gè)頂點(diǎn)在圖中的序號(hào)；link1是指向下一條與頂點(diǎn)vex1相關(guān)聯(lián)的邊；link2是指向下一條與頂點(diǎn)vex2相關(guān)聯(lián)的邊。其中：data是存放該頂點(diǎn)相關(guān)信息

14、；firstEdge是指向第一條與頂點(diǎn)相關(guān)聯(lián)的邊。VNode data firstEdge 34鄰接多重表類型說(shuō)明如下：class EdgeNode / 邊結(jié)點(diǎn) Tag mark； /訪問(wèn)標(biāo)記 int vex1,vex2； / 該邊所指向的頂點(diǎn)的序號(hào) EdgeNode *link1，*link2； / 指向下一條邊的指針 public: EdgeNode(int adj) ;/ EdgeNodeclass VNode / 頂頭結(jié)點(diǎn)DataType data； / 頂點(diǎn)的信息EdgeNode *firstEdge / 指向與該頂點(diǎn)所關(guān)聯(lián)的一條的指針35public: VNode (DataTyp

15、e e) data=e; firstEdge=NULL;/ VNodeclass MulistGragh /鄰接多重表 int n； / 頂點(diǎn)的個(gè)數(shù)Node VheadMaxSize； public: MulistGragh (int m) n=m； void CreateGraph(g ) ； / 建立圖gvoid LocateVex(u) ； / 得到頂點(diǎn)v在圖中的序號(hào) void GetVex(v) ； / 得到頂點(diǎn)v的值void PutVex(v，value) ； / 把v的值賦為value void FirstAdjVex(v) ； / 得到頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn) void NextA

16、djVex(v, w); / 確定圖G中頂點(diǎn)出v相對(duì)于w的下一個(gè)鄰接點(diǎn)36void DFSTraverse(int v)； / 從頂點(diǎn)v開始對(duì)圖進(jìn)行深度優(yōu)先遍歷void BFSTraverse(int v); / 從頂點(diǎn)v開始對(duì)圖進(jìn)行廣度優(yōu)先遍歷; /MulistGragh376.2.4 十字鏈表十字鏈表是只用來(lái)存儲(chǔ)有向圖的另一種存儲(chǔ)結(jié)構(gòu)?？梢园咽宙湵砜闯墒菍⒂邢驁D的鄰接表和逆鄰接表結(jié)合起來(lái)而得到的一種鏈表 有向圖中每一條弧對(duì)應(yīng)于一個(gè)弧結(jié)點(diǎn)（ArcNode），每個(gè)頂點(diǎn)也對(duì)應(yīng)于一個(gè)頂點(diǎn)結(jié)點(diǎn)（Vnode）。在弧結(jié)點(diǎn)中，每一條弧對(duì)應(yīng)的弧結(jié)點(diǎn)有五個(gè)域。弧結(jié)點(diǎn) mark hvex tvex hlink

17、tlink38其中：mark表示是否遍歷過(guò)，hvex表示該弧的弧尾頂點(diǎn)在圖中的位置，tvex表示該弧的弧頭頂點(diǎn)在圖中的位置，hlink指向弧頭相同的下一條弧，tlink指向弧尾相同的下一條弧。其中：data存放該頂點(diǎn)相關(guān)信息，firstin指向該頂點(diǎn)為弧頭的第一個(gè)弧結(jié)點(diǎn)，firstout指向該頂點(diǎn)為弧尾的第一個(gè)弧結(jié)點(diǎn)。頂點(diǎn)結(jié)點(diǎn) ：datafirstinfirstout39有向圖以及十字鏈表 40十字鏈表類型說(shuō)明如下：class ArcNode / 弧結(jié)點(diǎn) Tag mark； /訪問(wèn)標(biāo)記 int hvex,tvex; /與該弧所關(guān)聯(lián)的兩個(gè)頂點(diǎn)的序號(hào) ArcNode *hlink,*tlink；

18、/ 分別指向與該弧所關(guān)聯(lián)的兩個(gè)頂點(diǎn)的下一條弧 public: ArcNode(int adj); ;/ ArcNodeclass VNode / 頂頭結(jié)點(diǎn) DataType data； / 頂點(diǎn)的信息 ArcNode *firstin,*firstout； /分別指向該頂點(diǎn)第一條入弧和出弧public: VNode (DataType e) data=e;firstin=firstout=NULL;/ VNode 41class MulistGragh / 十字鏈表 int n； / 頂點(diǎn)的個(gè)數(shù) Node VheadMaxSize； public: MulistGragh (int m) n=

19、m； void CreateGraph(g)； / 建立圖g void LocateVex(v)； / 得到頂點(diǎn)v在圖中的序號(hào) void GetVex(v)； / 得到頂點(diǎn)v的值 void PutVex(v，value)； / 把v的值賦為value void FirstAdjVex(v) / 得到頂點(diǎn)v的第一個(gè)鄰接點(diǎn) void NextAdjVex(v / 得到頂點(diǎn)v的下一個(gè)鄰接點(diǎn) void DFSTraverse(int v)； / 從頂點(diǎn)v開始對(duì)圖進(jìn)行深度優(yōu)先遍歷 void BFSTraverse(int v)； / 從頂點(diǎn)v開始對(duì)圖進(jìn)行廣度優(yōu)先遍歷;/ MulistGragh426.3

20、 圖的遍歷從圖中某一頂點(diǎn)出發(fā)，按照某種搜索路徑訪問(wèn)圖中所有的頂點(diǎn)，使得每個(gè)頂點(diǎn)被訪問(wèn)一次且僅被訪問(wèn)一次，這個(gè)過(guò)程稱為圖的遍歷。深度優(yōu)先遍歷(搜索)廣度優(yōu)先遍歷(搜索)圖的兩種遍歷方法43從圖中某一起始點(diǎn) v 開始，訪問(wèn)v，然后從 v 出發(fā)，訪問(wèn)它的第一個(gè)鄰接點(diǎn) w1；再?gòu)?w1 出發(fā)，訪問(wèn)與 w1鄰 接但還沒(méi)有訪問(wèn)過(guò)的頂點(diǎn) w2；然后再?gòu)?w2 出發(fā)，進(jìn)行類似的訪問(wèn)， 如此進(jìn)行下去，直到某一頂點(diǎn)所有的鄰接點(diǎn)都被訪問(wèn)完。則退回到上一步剛訪問(wèn)過(guò)的頂點(diǎn)，看是否還有其它沒(méi)有被訪問(wèn)的鄰接點(diǎn)。如果有，則訪問(wèn)此頂點(diǎn)，之后再?gòu)拇隧旤c(diǎn)出發(fā)，進(jìn)行與前述類似的訪問(wèn)；如果沒(méi)有，就再退回上一步進(jìn)行搜索。重復(fù)上述過(guò)程，直

21、到連通圖中所有頂點(diǎn)都被訪問(wèn)過(guò)為止。6.3.1 深度優(yōu)先遍歷DFS ( Depth First Search )DFS算法思想：44深度優(yōu)先遍歷DFS ( Depth First Search )深度優(yōu)先搜索的示例深度優(yōu)先搜索過(guò)程 深度優(yōu)先生成樹DFS序列：ABEGCFDHI45 為了避免重復(fù)訪問(wèn),設(shè)置一個(gè)輔助數(shù)組 visitedn. 它的初始狀態(tài)為 0，在圖的遍歷過(guò)程中，一旦某一個(gè)頂點(diǎn) i 被訪問(wèn)，就把 visitedi置為 1，以防它多次被訪問(wèn)。圖中可能存在回路，且圖的任一頂點(diǎn)都可能與其它頂點(diǎn)相鄰，在訪問(wèn)完某個(gè)頂點(diǎn)之后可能會(huì)沿著某些邊又回到了曾經(jīng)訪問(wèn)過(guò)的頂點(diǎn)。深度優(yōu)先遍歷DFS算法思想:46

22、連通圖的深度優(yōu)先遍歷算法如下: void DFS(int v) /從頂點(diǎn)v出發(fā)訪問(wèn)包含該頂點(diǎn)v的最大連通子圖中的所有頂點(diǎn) visitedv=1； visit(v)； /或coutv; for (w=FirstAdjVex(v)；w!=-1；w=NextAdjVex(v,w) if (!visitedw) DFS(w)； / DFS47 圖的深度優(yōu)先遍歷算法如下:void DFSTraverse( ) /深度優(yōu)先求圖的連通分量 int visitedn； /設(shè)置訪問(wèn)標(biāo)志數(shù)組 for (v=0；vn；v+) visitedv=0； /初始化訪問(wèn)標(biāo)志數(shù)組 for (v=0；vn；v+) if (!v

23、isitedv) DFS(v)； /每次從尚未訪問(wèn)過(guò)的頂點(diǎn)中選取一個(gè)頂點(diǎn)v，從頂點(diǎn)/v出發(fā)進(jìn)行調(diào)用DFS(v)/ DFSTraverse48假定圖以鄰接矩陣G存儲(chǔ):int FirstAdjVex(int v) int w=0; while(wn & matrixvw=0)w+; if(wn) return w; else -1; 算法的時(shí)間復(fù)雜度為：(n)49假定圖以鄰接矩陣G存儲(chǔ) int NextAdjVex(int v,int w) u=w+1; while(un & matrixvu=0)u+; if(ufirstout) return gheadv-firstout.adjvex； e

24、lse return -1;/ FirstAdjVex算法的時(shí)間復(fù)雜度為：(1)51int NextAdjVex(int v，int w) p=gheadv-firstout； while (p & p-adjvex!=w) p=p-link； if (!p | !p-link) return -1； else return p-link-adjvex；/ NextAdjVex假定圖以鄰接表G存儲(chǔ)：算法的時(shí)間復(fù)雜度為：(TD(v)52算法分析：圖中有 n 個(gè)頂點(diǎn)，e 條邊。如果用鄰接矩陣存儲(chǔ)圖，則查找每一個(gè)頂點(diǎn)的所有相鄰頂點(diǎn)，所需時(shí)間為O(n)，則遍歷圖中所有的頂點(diǎn)所需的時(shí)間為O(n2)。 如

25、果用鄰接表存儲(chǔ)圖，在每一個(gè)單鏈 表中可以找到某個(gè)頂點(diǎn) v 的所有鄰接頂點(diǎn) w。由于總共有 2e 個(gè)邊結(jié)點(diǎn)(無(wú)向圖)，所以掃描邊的時(shí)間為O(e)。而且對(duì)所有頂點(diǎn)遞歸訪問(wèn)1次，所以遍歷圖的時(shí)間復(fù)雜性為O(n+e)。53在訪問(wèn)了起始頂點(diǎn) v 之后，由 v 出發(fā)，依次訪問(wèn) v 的所有未被訪問(wèn)過(guò)的鄰接點(diǎn) w1, w2, , wt，然后再順序訪問(wèn) w1, w2, , wt 的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)。再?gòu)倪@些訪問(wèn)過(guò)的頂點(diǎn)出發(fā)，再訪問(wèn)它們的所有未被訪問(wèn)過(guò)的鄰接點(diǎn)， ，如此重復(fù),直到圖中所有頂點(diǎn)都被訪問(wèn)完為止。6.3.2 廣度優(yōu)先遍歷BFS ( Breadth First Search )54廣度優(yōu)先遍歷的示例

26、 廣度優(yōu)先搜索過(guò)程 廣度優(yōu)先生成樹BFS序列：ABCDEFGFI55為了實(shí)現(xiàn)逐層訪問(wèn)，算法中使用了一個(gè)隊(duì)列，以保存正在訪問(wèn)的頂點(diǎn)，以便向下一層訪問(wèn)。廣度優(yōu)先遍歷是一種分層的搜索過(guò)程，每向前走一步可能訪問(wèn)一批頂點(diǎn)，不像深度優(yōu)先搜索那樣有往回退的情況。因此，廣度優(yōu)先遍歷不是一個(gè)遞歸的過(guò)程，其算法也不是遞歸的。與深度優(yōu)先遍歷過(guò)程一樣，為避免重復(fù)訪問(wèn)，需要一個(gè)輔助數(shù)組 visitedn，對(duì)被訪問(wèn)過(guò)的頂點(diǎn)加以標(biāo)記。56圖的廣度優(yōu)先遍歷（BFS）算法思想：（1）清隊(duì)列Q；（2）對(duì)出發(fā)頂點(diǎn)v做：v入隊(duì)；標(biāo)記v；（3）當(dāng)隊(duì)列Q不空反復(fù)做： (a) 出隊(duì)頭元素到u；訪問(wèn)u; (b) 將u的未被訪問(wèn)的鄰接點(diǎn)w入隊(duì)

27、；標(biāo)記w；57圖的廣度優(yōu)先搜索算法：void BFS(int v) /廣度優(yōu)先求圖的連通分量 Q=new Queue( )； /清隊(duì)列Q Q.Enter(v)； /將起始頂點(diǎn)v入隊(duì) visitedv=1； /標(biāo)記v while (!Q.IsEmpty() /隊(duì)列Q不空 u=Q.Leave()； /出隊(duì)頭元素到u visited(u)； /訪問(wèn)u for (w=FirstAdjVex(u)；w!=-1；w=NextAdjVex(u，w) if (!visitedw) Q.Enter(w)； /將u的每個(gè)未被訪問(wèn)的鄰接點(diǎn)w 入隊(duì) visitedw=1； / BFS58BFS從出發(fā)點(diǎn)只能遍歷一個(gè)連通

28、分量，若對(duì)任意圖的遍歷需要對(duì)每個(gè)分量中一個(gè)未被訪問(wèn)的頂點(diǎn)為出發(fā)點(diǎn)進(jìn)行BFS遍歷。算法如下：void BFSTraverse() /廣度優(yōu)先求圖的連通分量 int visitedn； /設(shè)置訪問(wèn)標(biāo)志數(shù)組 for (v=0；vn；v+) visitedv=0； /初始化訪問(wèn)標(biāo)志 for (v=0；v n; /輸入頂點(diǎn)個(gè)數(shù) G = new gheadn; /創(chuàng)建頂點(diǎn)表數(shù)組 for ( int i = 0; i data; G.gheadi.data=data; VertexPosi=data; cin head tail weight; /weight可省 while(head!=-1) j = L

29、ocateVex ( head ); k = LocateVex ( tail ); InsertEdge ( k, j, weight );/weight可省 616.4 無(wú)向圖的應(yīng)用6.4.1 最小生成樹(MST)( Minimum-cost Spanning Tree )生成樹： 包含連通無(wú)向圖中全部頂點(diǎn)的極小連通子圖。 按照生成樹的定義，n 個(gè)頂點(diǎn)的連通無(wú)向圖的生 成樹有 n 個(gè)頂點(diǎn)、n-1 條邊。 生成樹不唯一。最小生成樹(MST): 連通無(wú)向網(wǎng)中邊權(quán)之和最小的生成樹。62假設(shè)在n個(gè)城市之間要建立通信網(wǎng)絡(luò)線，要求使得每個(gè)城市之間連通且費(fèi)用最少。MST典型用途：數(shù)學(xué)模型：頂點(diǎn)表示城市，

30、有n個(gè)；邊表示線路；邊的權(quán)值表示線路的經(jīng)濟(jì)代價(jià)；連通網(wǎng)表示n個(gè)城市間通信網(wǎng)。問(wèn)題抽象： n個(gè)頂點(diǎn)的生成樹很多，需要從中選一棵代價(jià)最小的生成樹，即該樹各邊的代價(jià)之和最小。此樹便稱為最小生成樹MST281234567101614181225242263求一個(gè)連通無(wú)向網(wǎng)中最小生成樹的方法: Prim算法 Kruskal算法都是利用MST的性質(zhì)構(gòu)造最小生成樹64MST性質(zhì)內(nèi)容如下：設(shè)G=（V，E）是連通無(wú)向網(wǎng)，對(duì)V的非空真子集U V，若（u，v）是一條具有最小權(quán)值的邊，其中uU，vV-U，則必存在一棵包含邊(u，v)的最小生成樹。uvUV-UV圖G65證明：（反證法:假設(shè)滿足條件的邊（u，v）不在任一

31、最小生成樹中）設(shè)G的任何MST都不包含（u,v）。設(shè)T是G的一棵MST，將（u,v）加入T，形成回路。去掉（u,v）得到T , 因 wuvwuv，所以T 的邊權(quán)之和小于T 的邊權(quán)之和，與T是MST矛盾。UuuV-UvvMST的性質(zhì)：66Prim算法的基本思想： （1）設(shè)T是G上最小生成樹中邊的集合，初始為空. 選取任意一個(gè)頂點(diǎn)u加入U(xiǎn)；（2）在所有uU，vV-U的邊 (u，v)E中找一條權(quán) 最小的邊 (u，v) 加入集合T中，同時(shí)v加入U(xiǎn)； （3）重復(fù)（2），直到U=V為止。671237456281612222510251418Prim算法過(guò)程示例 T= U=168Prim算法過(guò)程示例1237

32、456281612222510251518 Min10, 28=10 T=(1,6) U=1,6691237456281612222510251518Prim算法過(guò)程示例 Min25, 28=25 T=(1,6),(6,5) U=1,6,5701237456281612222510251518Prim算法過(guò)程示例 Min28，25，22=22 T=(1,6),(6,5),(5,4) U=1,6,5,4712812374561612222510251518Prim算法過(guò)程示例 Min28，25，18，12=12 T=(1,6),(6,5),(5,4),(4,3) U=1,6,5,4,372123

33、7456281612222510251518Prim算法過(guò)程示例 Min15，25，18=15 T=(1,6),(6,5),(5,4),(4,3),(3,2),(2,7) U=1,6,5,4,3,2,7731237456281612222510251518Prim算法過(guò)程示例 Min28，25，18，16=16 T=(1,6),(6,5),(5,4),(4,3),(3,2) U=1,6,5,4,3,2741237456281612222510251518Prim算法過(guò)程示例 U=V, 算法結(jié)束 T=(1,6),(6,5),(5,4),(4,3),(3,2),(2,7)75在構(gòu)造過(guò)程中，還設(shè)置了

34、一個(gè)輔助數(shù)組closedgen，每個(gè)元素closedgev有兩個(gè)域： lowcost 存放生成樹頂點(diǎn)集合內(nèi)頂點(diǎn)到生成樹外各頂點(diǎn)的各 邊上的當(dāng)前最小權(quán)值； adjvex 記錄生成樹頂點(diǎn)集合外各頂點(diǎn)距離集合內(nèi)哪個(gè)頂點(diǎn)最近(即權(quán)值最小)。存儲(chǔ): 鄰接矩陣。Prim算法的實(shí)現(xiàn):lowcostadjvex76利用Prim算法求最小生成樹的算法:class AddArray int adjvex; float lowcost; ;/ AddArrayvoid MinSpanTree_Prim(int u,AddArray closedge, AddArray edge,AdjMatrix G)/ 設(shè)圖以鄰

35、接矩陣存儲(chǔ)，用Prim算法從頂點(diǎn)u出發(fā)構(gòu)造網(wǎng)G的最小生/成樹且保存到數(shù)組edge中 for(v=0；vn；v+) Uv=0； Uu=1； for (v=0；v n；v+) /初始化輔助數(shù)組closedge if（u!=v) closedgev.adjvex=u; closedgev.lowcost=G.matrixuv; 77 for (t=1；tn；t+) /選擇其余的n-1個(gè)頂點(diǎn) k=minimum(closedge)； /求出T的下一個(gè)頂點(diǎn)k頂點(diǎn) u=closedgek.adjvex； edgek.lowcost=matrixku; /保存選中邊的權(quán)值 edgek.adjvex=u; /

36、保存選中邊的頂點(diǎn) Uk=1； for (j=0；jn；j+) if (Uj=0 & G.matrixkjclosedgej.lowcost) closedgej.lowcost=matrixkj； closedgej.adjvex=k； / for / MinSpanTree_Prim78 iclosedge1 23456UV-UedgeAdjvexLowcost 028000010001，2，3，4，5，6510AdjvexLowcost 0280052501000，51，2，3，4，6425AdjvexLowcost 02804225250104240，5，41，2，36322Adjvex

37、Lowcost 028312422525v0103180，5，4，31，2，6212AdjvexLowcost 2163124225240103180，5，4，3，21，6116AdjvexLowcost 2163124225240101140，5，4，3，2，16614AdjvexLowcost 2163124225240101140，5，4，3，2，1，6 表6.1 從頂點(diǎn)0出發(fā)利用Prim算法構(gòu)造最小生成樹過(guò)程中輔助數(shù)組各分量的值的變化79設(shè)連通無(wú)向網(wǎng)有 n 個(gè)頂點(diǎn), 則該算法的時(shí)間復(fù)雜度為O(n2)。Prime算法分析它適用于邊稠密的網(wǎng)絡(luò)。802、Kruscal 算法基本思想: 先構(gòu)造

38、一個(gè)只含 n 個(gè)頂點(diǎn)的零圖 ST ，然后從權(quán)值最小的邊開始，若它的添加不使 ST 產(chǎn)生回路，則在 ST上加上這條邊，如此重復(fù)，直至加上 n-1 條邊為止。81已知連通無(wú)向網(wǎng)G = ，初始 ST=; k = 0; / k 記選中的邊數(shù) while (kn-1) 從邊集 E 中選取權(quán)值最小的邊(u,v); 若(u,v)加入ST后不使ST中產(chǎn)生回路，則將 邊(u,v)加入到TE中，從E中去掉邊(u,v) ； k+;Kruscal 算法思想描述:8250461321025152422161812285046132504613210504613210121550461321012155046132101

39、216應(yīng)用Kruscal算法構(gòu)造最小生成樹的過(guò)程原圖83155046132101216222515504613210121622應(yīng)用Kruscal算法構(gòu)造最小生成樹的過(guò)程原圖5046132102515242216181228846.5 有向圖的應(yīng)用 有向圖可以用來(lái)表示工程的實(shí)施、產(chǎn)品的流 圖、程序流程和學(xué)生的課程安排等。6.5.1 拓?fù)渑判?圖可以用來(lái)描述一個(gè)工程或一個(gè)系統(tǒng)的進(jìn)行過(guò)程。除最簡(jiǎn)單的工程外，幾乎所有的工程都可分成若干個(gè)活動(dòng)的子工程，完成了這些子工程也就完成了整個(gè)工程。 85例如在工程的實(shí)施中，一個(gè)工程往往由若干個(gè)子工程組成，除了很小的工程外，一般都把工程分為若干個(gè)稱做“活動(dòng)”的子工

40、程。完成了這些活動(dòng)，該工程就可以結(jié)束。而這些子工程間有兩種關(guān)系：一是它們之間有先后順序關(guān)系，即一個(gè)工程結(jié)束后另一個(gè)子工程才能開始；二是它們之間無(wú)先后順序關(guān)系，即兩個(gè)子工程誰(shuí)先誰(shuí)后都互不影響。6.5.1 拓?fù)渑判?6例如學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求有先修課程，有些則不要求。即有的課程之間有先后順序關(guān)系，而有的課程可以并行地學(xué)習(xí)。AOV (Activity On Edges）網(wǎng): 用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)。6.5.1 拓?fù)渑判?7 C1 高等數(shù)學(xué) C2 計(jì)算機(jī)基礎(chǔ) C3 離散數(shù)學(xué) C1, C2 C4 數(shù)

41、據(jù)結(jié)構(gòu) C3, C2 C5 高級(jí)語(yǔ)言 C2 C6 編譯原理 C5, C4 C7 操作系統(tǒng) C4, C9 C8 普通物理 C1 C9 計(jì)算機(jī)原理 C8 課程代號(hào)課程名稱先修課程88學(xué)生課程學(xué)習(xí)工程圖6.5.1 拓?fù)渑判?9拓?fù)?有序)序列：在AOV網(wǎng)中若將各個(gè)頂點(diǎn) (代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列v1,v2,vn，使得若從頂點(diǎn)vi到vj有一條有向路徑,則在序列中頂點(diǎn)vi必須排在頂點(diǎn)vj之前。拓?fù)渑判蛟贏OV網(wǎng)中找一個(gè)拓?fù)湫蛄械倪^(guò)程。6.5.1 拓?fù)渑判?0例如，對(duì)學(xué)生選課工程圖進(jìn)行拓?fù)渑判?，得到的拓?fù)溆行蛐蛄袨?C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9

42、, C7或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6拓?fù)湫蛄胁⒉晃ㄒ?1BDAC對(duì)于有向圖不能求得它的拓?fù)溆行蛐蛄?。因?yàn)閳D中存在一個(gè)有向回路 B, C, D6.5.1 拓?fù)渑判?2拓?fù)渑判虻乃惴ㄋ枷耄狠斎胍粋€(gè)AOV網(wǎng)。令 n 為頂點(diǎn)個(gè)數(shù)。(1) 在AOV網(wǎng)中選一個(gè)沒(méi)有前驅(qū)的頂點(diǎn), 并輸出之.(2) 從圖中刪去該頂點(diǎn), 同時(shí)刪去與該頂點(diǎn)關(guān)聯(lián)的弧.(3) 重復(fù)以上 (1)、(2) 步, 直到全部頂點(diǎn)均已輸出，拓?fù)湫蛄行纬?，拓?fù)渑判蛲瓿?或圖中還有未輸出的頂點(diǎn)，這說(shuō)明圖中還剩下一些頂點(diǎn)，它們都有直接前驅(qū)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)說(shuō)明AOV網(wǎng)中一定存

43、在有向回路。93拓?fù)渑判虻倪^(guò)程94拓?fù)渑判虻倪^(guò)程95拓?fù)渑判虻倪^(guò)程96拓?fù)渑判虻倪^(guò)程最后得到的拓?fù)湫蛄袨?C4 ,C0,C3 ,C2 ,C1 ,C5 。97在算法中增設(shè)一個(gè)數(shù)組indegree ,記錄各個(gè)頂點(diǎn)的 入度。(2) 算法思想中第2步提到的“刪去頂點(diǎn)”和“刪去弧”在算法實(shí)現(xiàn)中并不真正刪除。而“刪去頂點(diǎn)”只是作刪除標(biāo)記，“刪去弧”是把與該弧相關(guān)聯(lián)的弧頭頂點(diǎn)的入度減1。拓?fù)渑判蛩惴▽?shí)現(xiàn)98圖的存儲(chǔ)：鄰接表(出邊表)。建立鄰接表：每輸入一條弧，就需要建立一個(gè)弧結(jié)點(diǎn)，并將它鏈入第 i個(gè)鏈表中，并統(tǒng)計(jì)頂點(diǎn)k的入度。 EArcNode * p = new EArcNode(k);/建立弧結(jié)點(diǎn), d

44、est 域?yàn)?k plink = ghead i. firstout ;ghead i. firstout = p; /鏈入頂點(diǎn) i 的鏈表的前端indegreek+; /頂點(diǎn) k 入度加1 99在拓?fù)渑判蛩惴ㄖ?，為了減少判斷入度為零的頂點(diǎn)，使用一個(gè)存放入度為零的頂點(diǎn)的鏈?zhǔn)綏＃┻x擇和輸出無(wú)前驅(qū)的頂點(diǎn)。只要出現(xiàn)入度為零的頂點(diǎn)，就將它加入棧中。使用頂點(diǎn)棧的拓?fù)渑判蛩惴梢悦枋鋈缦拢?(1) 建立入度為零的頂點(diǎn)棧; int top = -1; /入度為零的頂點(diǎn)棧初始化 for ( int i = 0; i int top = -1; for ( int i = 0; i ik; /讀入一條弧 wh

45、ile(i!=-1) EArcNode * p = new EArcNode(k); /建立弧結(jié)點(diǎn), adjvex域?yàn)?k plink = ghead i. firstout ; ghead i. firstout = p; /鏈入頂點(diǎn) i 的邊鏈表的前端 indegreek+; /頂點(diǎn) k 入度加1 cinik; 拓?fù)渑判虻乃惴椋?04 top=-1; /建立初始頂點(diǎn)入度為0棧 for(i=0；i-1) i=top; top=indegreetop; coutlink) k=p-adjvex； if(!(-indegreek) indegreek=top；top=k; /for/while

46、if(countn) return false；return true；/TopologicalSort106 建立有向圖的鄰接表和入度數(shù)組indegree 107int top = -1; for ( int i = 0; i 事件弧活動(dòng)權(quán)值活動(dòng)的持續(xù)時(shí)間AOE網(wǎng)112AOE網(wǎng)在某些工程預(yù)算方面非常有用。 它可以使人們了解到： (1) 完成整個(gè)工程至少需要多少時(shí)間(假設(shè) 網(wǎng)中沒(méi)有有向回路)? (2) 為縮短完成工程所需的時(shí)間, 應(yīng)當(dāng)加快 哪些活動(dòng)? 從源點(diǎn)到各個(gè)頂點(diǎn)，以至從源點(diǎn)到匯點(diǎn)的有向路徑可能不止一條。這些路徑的長(zhǎng)度也可能不同。完成不同路徑的活動(dòng)所需的時(shí)間雖然不同，但只有各條路徑上所有活

47、動(dòng)都完成了，整個(gè)工程才算完成。113(源點(diǎn))(匯點(diǎn))完成整個(gè)工程所需的時(shí)間取決于從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑長(zhǎng)度(最長(zhǎng)路徑可能不止一條)，即在這條路徑上所有活動(dòng)的持續(xù)時(shí)間之和。解決問(wèn)題(1)(完成工程的最短時(shí)間)114路徑長(zhǎng)度最長(zhǎng)的路徑稱為關(guān)鍵路徑(Critical Path)。關(guān)鍵路徑上的所有活動(dòng)稱為關(guān)鍵活動(dòng)。關(guān)鍵路徑為: (v0,v1,v4,v6,v8 )或(v0,v1,v4,v7,v8 )關(guān)鍵路徑為長(zhǎng)度為18關(guān)鍵活動(dòng)為：a1, a4, a7, a9, a10, a8, a11115解決問(wèn)題(2)(為縮短工程所需時(shí)間, 應(yīng)當(dāng)加快哪些活動(dòng))要找出關(guān)鍵路徑，必須找出關(guān)鍵活動(dòng)，只有提高關(guān)鍵活動(dòng)的功效，

48、才可能縮短整個(gè)工期。116定義幾個(gè)與計(jì)算關(guān)鍵活動(dòng)有關(guān)的量：1. eei-事件Vi 的最早開始時(shí)間ee4=7ee5=7 從源點(diǎn)V0 到頂點(diǎn)Vi 的最長(zhǎng)路徑長(zhǎng)度。1172. lei-事件Vi 的最遲開始時(shí)間 在保證匯點(diǎn)Vn-1 在不推遲整個(gè)工程完成的前提下，事件Vi 允許的最遲開始時(shí)間。le5=18-4-4 10ee5=7ee4=7le4=18-11 =7它等于een-1 減去從Vi到Vn-1的最長(zhǎng)路徑長(zhǎng)度。118 3. ek-活動(dòng)ak 的最早開始時(shí)間 設(shè)活動(dòng)ak 在弧上，則ek是從源點(diǎn)V0到頂點(diǎn)Vi 的最長(zhǎng)路徑長(zhǎng)度。 因此, ek = eei。 i j ake9=ee5=7e7=ee4=7119

49、4. lk-活動(dòng)ak 的最遲開始時(shí)間 lk是在不推遲整個(gè)工程完成的前提下，該活動(dòng)允許的最遲開始時(shí)間. lk = lej - dur()。其中，dut()是完成ak 所需的時(shí)間。 i j akl5=le4- a5 =7-1=6e5=ee2=4l4=le4-1 =7-1=6e4=ee1=6120 表示活動(dòng)ak 的最遲開始時(shí)間和最早開始時(shí)間的時(shí)間余量。lk = ek表示活動(dòng)ak 是沒(méi)有時(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 的 eei 和 lei。5. lk-ek-時(shí)間余量lk

50、= lej - dut()ek = eei i j ak121（1）求eei（2）求lei（3）求ek（4）求lk（5）計(jì)算lk-ek求關(guān)鍵活動(dòng)的步驟122（1）如何求eei？其中P(j)表示以頂點(diǎn)j為弧頭的所有弧的尾頂點(diǎn)集合。 eei是從源點(diǎn)V0 到頂點(diǎn)Vi 的最長(zhǎng)路徑長(zhǎng)度。123（2）如何求lei？其中S(j)是以頂點(diǎn)j為弧尾的所有弧的弧頭頂點(diǎn)集合。124（4）求li li = lev - dut()（3）求ei ei =eeuu vaiv（5）計(jì)算lk-ek eeu=lev - dut()？125876534210a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a

51、10=2a11=4V0V1V2V3V4V5V6V7V80645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活動(dòng) ek lk l-e00002266046258377077071031616014140033頂點(diǎn) eei leiek = eeilk = lej - dut()AOE網(wǎng)126（1）建立AOE網(wǎng)（存儲(chǔ)結(jié)構(gòu)為鄰接表）。（2）從源點(diǎn)V0出發(fā)，令ee0=0，一邊進(jìn)行拓?fù)渑判?，一邊?jì)算其余各頂點(diǎn)的eei。若圖中有回路則算法結(jié)束.（3）從匯點(diǎn)Vn-1出發(fā), len-1=een-1,按逆拓?fù)溆行虻捻樞蚯?lei, i=n-2, , 0。求AOE網(wǎng)中關(guān)

52、鍵活動(dòng)的算法思想127（4）根據(jù)各頂點(diǎn)的ee和le值，求每條弧的最早開始時(shí)間ek和最遲開始時(shí)間 lk。 若某條弧滿足條件 ek=lk，則該條弧是關(guān)鍵活動(dòng)。128求關(guān)鍵活動(dòng)算法如下：bool TopologicalSort(Stack &T) /求以鄰接表存儲(chǔ)的有向圖中各頂點(diǎn)事件的最早發(fā)生時(shí)間ee。/S是入度為零頂點(diǎn)棧，T為拓?fù)湫蛄许旤c(diǎn)棧。若該有向圖無(wú)回路，/則該算法返回true且棧T返回該有向圖的一個(gè)拓?fù)湫蛄?，否則返回 /false。 Stack S; FindInGegree(indegree)； /求各頂點(diǎn)的入度indegree0.n-1且建立入度為零頂點(diǎn)棧S count=0; ee0.n

53、-1=0; /初始化 for (k=0; klink) /對(duì)頂點(diǎn)j的每個(gè)后繼頂點(diǎn)入度減1 k=p-adjvex; if(-indegreek=0) S.Push(k); /若入度為0，則入棧S if(eej+ p-cost )eek) eek=eej+ p-cost ; /對(duì)j的每個(gè)后繼頂點(diǎn)k修改eek if(countlink;) k=p-adjvex; if (lek-p-cost)cost; 131for(j=0;jlink) k=p-adjvex; tag=(eej=lek-p-cost )?*: ; coutjkcost)eejcost )tag; /CriticalPath132關(guān)

54、鍵路徑算法分析:第一個(gè)for 語(yǔ)句O(n)；第二個(gè)for 語(yǔ)句O(n+e)；第三個(gè)for 語(yǔ)句O(n)；第四個(gè)for 語(yǔ)句O(n+e)；總共花費(fèi)時(shí)間為O(n+e)。1336.6 最短路徑 (Shortest Path)134 6.6.2 每一對(duì)頂點(diǎn)之間的最短路徑 Floyd算法 6.6.1 求從某個(gè)源點(diǎn)到其余各點(diǎn)的最短路徑 Dijkstra算法6.6 最短路徑 (Shortest Path)135問(wèn)題的提法： 給定一個(gè)網(wǎng)G = 與源點(diǎn)v0，求從v0到G中其它頂點(diǎn)的最短路徑。 規(guī)定各邊(或弧)上的權(quán)值大于或等于0。6.6.1 求單源最短路徑Dijkstra算法Dijkstra算法的基本思想 按照

55、路徑長(zhǎng)度遞增的次序產(chǎn)生各條最短路徑。136 這條路徑必定只含一條弧，并且這條弧的權(quán)值最小。第一條最短路徑長(zhǎng)度的求法:6.6.1 求單源最短路徑Dijkstra算法137 它只可能有兩種情況: 或者是直接從源點(diǎn)到某頂點(diǎn)v2(只含一條弧)； 或者是，從源點(diǎn)經(jīng)過(guò)頂點(diǎn)v1，再到達(dá)該頂點(diǎn)v2(由兩條弧組成)。第二條最短路徑長(zhǎng)度的求法:138 其余最短路徑的求法： 它或者是直接從源點(diǎn)到某頂點(diǎn)vk(只含一條弧)或者是從源點(diǎn)經(jīng)過(guò)已求得最短路徑的頂點(diǎn)，再到達(dá)該頂點(diǎn)。139例： Min10,30,100=106.6.1 求單源最短路徑Dijkstra算法602010305010003421101406020103

56、05010003421例：10 Min60,30,100=306.6.1 求單源最短路徑Dijkstra算法14160201030501003421100 Min50,90=506.6.1 求單源最短路徑Dijkstra算法14260201030501003421100 Min60=606.6.1 求單源最短路徑Dijkstra算法143602010305010034211006.6.1 求單源最短路徑Dijkstra算法0-1: 100-3: 300-3-2: 500-3-2-4: 60按照路徑長(zhǎng)度遞增的次序產(chǎn)生各條最短路徑。144引入一個(gè)輔助數(shù)組dist。它的每一個(gè)分量disti表示當(dāng)前找

57、到的從源點(diǎn)v0到終點(diǎn)vi 的最短路徑的長(zhǎng)度。初始狀態(tài)：若從源點(diǎn)v0到頂點(diǎn)vi有邊或弧，則disti為該邊或弧上的權(quán)值若從源點(diǎn)v0到頂點(diǎn)vi 沒(méi)有邊或弧，則disti為+ 。每次求得一條最短路徑之后，其終點(diǎn)vk 加入集合U，然后對(duì)所有的vi V-U，修改其disti值。Dijkstra算法思想：145在算法中，還應(yīng)引入兩個(gè)輔助數(shù)組find和path。findi=1當(dāng)且僅當(dāng)已求得從v0到vi的最短路徑。初始find0=1， find1.n-1=0；pathi用來(lái)記錄從v0到vi的最短路徑上vi的前驅(qū)頂點(diǎn)。若pathi=i-1， pathi-1=i-2， path1=0， 則逆序列v0 ，v1，v2

58、，vi 就是v0vi的最短路徑上的頂點(diǎn)序列。 Dijkstra算法思想：146Dijkstra算法可描述如下：(1) 初始化： 設(shè)源點(diǎn)為v0，則find0=1; 其它find1.n-1=0; disti cost0i, i= 1, 2, , n-1; (2) 求出最短路徑的長(zhǎng)度： distk min disti , i V- U ; findk=1;(3) 修改： 對(duì)于每一個(gè) i V- U; /即findi=0 disti min disti, distk + costki , 若U = V, 則算法結(jié)束，否則轉(zhuǎn)(2)。存儲(chǔ)：鄰接矩陣147計(jì)算最短路徑的圖鄰接矩陣類的定義const int n

59、 =20； /圖中最大頂點(diǎn)個(gè)數(shù)Const int Max=9999; /9999表示無(wú)窮大class Graph /圖的類定義 float costnn； float dist n； /最短路徑長(zhǎng)度數(shù)組 int pathn； /最短路徑頂點(diǎn)序列數(shù)組 int findn； /最短路徑頂點(diǎn)集public: void ShortestPath_DIJ (int，int，int)； int mininum ( int )；/ Graph148用Dijkstra描述的單源最短路徑算法為：void ShortestPath_DIJ(int v0，int dist，int path) /求從源點(diǎn)為v0從到其它頂點(diǎn)的最短路經(jīng)。for(v=0；vn；v+) findv=0； pathv=0； distv=costv0v； findv0=1；for(i=1；i n；i+)