數(shù)據(jù)結(jié)構(gòu)第6章

1、JYP1第6章 圖 本章學(xué)習(xí)一種更普遍的非線性結(jié)構(gòu)圖，特別是圖的基本表示和基本問題的解決方法。 JYP26.1 圖的基本定義 圖G由集合V和集合E組成，記為G = (V, E)。其中，V(G) 是頂點(diǎn)的有限集合，且V ；E(G) 是邊的有限集合，邊由V中的不同頂點(diǎn)對構(gòu)成。一個圖的頂點(diǎn)和邊可附加額外信息，并用于計(jì)算機(jī)應(yīng)用建模。例如，一個用頂點(diǎn)表示城市，邊表示城市間距離的圖可用于交通網(wǎng)絡(luò)的研究。圖的典型應(yīng)用領(lǐng)域：電路分析、尋找最短路由，通信網(wǎng)絡(luò)、項(xiàng)目規(guī)劃，鑒別化合物、統(tǒng)計(jì)力學(xué)、遺傳學(xué)、控制論、語言學(xué)，以及社會科學(xué)等。JYP3 圖可分為無向圖和有向圖：在無向圖中，E = (u, v) | u, v

2、V，頂點(diǎn)對 (u, v) 是無序的，(u, v) 和 (v, u) 表示同一條邊。在有向圖中，E = | u, v V，頂點(diǎn)對 是有序的，表示一條從u到v的有向邊；u和v分別是邊的尾（tail）和頭（head）。因此， 和 表示兩條不同的邊。JYP4 下面給出了三個圖。其中，G1和G2是無向圖，G3是有向圖。注意有向圖的邊用帶箭頭的線段表示。 JYP5 這些圖的頂點(diǎn)集合與邊集合分別為：V(G1) = 0, 1, 2, 3E(G1) = (0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)V(G2) = 0, 1, 2, 3, 4, 5, 6E(G2) =

3、 (0, 1), (0, 2), (1, 3), (1, 4), (2, 5), (2, 6)V(G3) = 0, 1, 2E(G3) = , , 。JYP6 限制：（1） 圖中不能有從一個頂點(diǎn)v到其自身的邊。（2） 圖中同一條邊不可以出現(xiàn)多次。在n個頂點(diǎn)的無向圖中，不同的頂點(diǎn)對 (u, v)（u v）最多有n (n 1)/2個。具有n個頂點(diǎn)，n (n 1)/2條邊的無向圖稱為完全無向圖，如G1。n個頂點(diǎn)的有向圖則最多有n (n 1) 條邊。JYP7 如果 (u, v) 是 E(G) 中的一條邊，則稱頂點(diǎn)u與v互為鄰接，邊 (u, v) 與頂點(diǎn)u和v相關(guān)聯(lián)。在G2中，與頂點(diǎn)1鄰接的頂點(diǎn)為0，3

4、和4，與頂點(diǎn)2相關(guān)聯(lián)的邊為(0, 2), (2, 5) 和 (2, 6)。如果 是一條有向邊，則稱頂點(diǎn)u鄰接到頂點(diǎn)v，v鄰接自u，邊 與頂點(diǎn)u和v相關(guān)聯(lián)。在G3中，與頂點(diǎn)1相關(guān)聯(lián)的邊為 , 和 。在許多應(yīng)用中，可以給圖的邊分配權(quán)重。這些權(quán)重可以表示距離、時間以及代價等信息。這類圖稱為加權(quán)圖。JYP8 設(shè)G和G為兩個圖。如果V(G) V(G)且E(G) E(G)，則G是G的子圖。 G1的一些子圖如下：JYP9 G3的一些子圖如下：JYP10 對于無向圖G，如果 (u, i1), (i1, i2), , (ik, v) 是屬于E(G)的邊，則稱頂點(diǎn)序列 u, i1, i2, , ik, v是從u到

5、v的路徑。對于有向圖G，如果 , , , 是屬于E(G)的邊，則稱頂點(diǎn)序列 u, i1, i2, , ik, v是從u到v的路徑。對于不加權(quán)圖，一條路徑的長度是該路徑上邊的條數(shù)。對于加權(quán)圖，一條路徑的長度是該路徑上各邊的權(quán)重之和。JYP11 若在一條路徑的頂點(diǎn)序列中，除了起點(diǎn)和終點(diǎn)以外，所有頂點(diǎn)都互不相同，則稱該路徑為簡單路徑。 例如，在G1中，0, 1, 3, 2 是簡單路徑，而0, 1, 3, 1卻不是；在G3中，0, 1, 2是簡單有向路徑，而1, 0, 1, 2卻不是。起點(diǎn)和終點(diǎn)相同的簡單路徑稱為環(huán)。 例如，0, 1, 2, 0 是G1中的一個環(huán)，0, 1, 0是G3中的一個有向環(huán)。J

6、YP12 在無向圖G中，稱兩個頂點(diǎn)u和v是連通的當(dāng)且僅當(dāng)G中存在一條從u到v的路徑。稱無向圖G是連通的當(dāng)且僅當(dāng)對于V(G) 中的每一對不同的頂點(diǎn)u和v，G中都存在一條從u到v的路徑。JYP13 G1和G2是連通的，而下面的G4卻不是：JYP14 無向圖G的一個連通分量H是其最大連通子圖。這里最大是指，G中不存在既連通又真包含H的子圖。 例如，G4有兩個連通分量：H1和H2。稱有向圖G是強(qiáng)連通的當(dāng)且僅當(dāng)對于V(G) 中的每一對不同的頂點(diǎn)u和v，G中不僅存在一條從u到v的有向路徑而且存在一條從v到u的有向路徑。 G3不是強(qiáng)連通的，因?yàn)槠渲胁淮嬖趶捻旤c(diǎn)2到1的路徑。有向圖G的一個強(qiáng)連通分量是其最大強(qiáng)

7、連通子圖。JYP15 G3的兩個強(qiáng)連通分量是：一個頂點(diǎn)的度是與該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)。在G是有向圖的情況下，頂點(diǎn)v的入度是以v為頭的邊的條數(shù)，頂點(diǎn)v的出度是以v為尾的邊的條數(shù)。 例如，G1中頂點(diǎn)0的度是3。G3的頂點(diǎn)1的入度為1，出度為2，度為3。 JYP16 設(shè)圖G有n個頂點(diǎn)，e條邊，di是頂點(diǎn)i的度，則樹是一個連通的無環(huán)圖。JYP17無向圖的抽象數(shù)據(jù)類型定義：template class Graph / 對象: 由一個非空的頂點(diǎn)集合和一個無向邊/集合構(gòu)成，每條邊是一個頂點(diǎn)對public: Graph ( );/ 建立一個空圖 void InsertVertex (Vertex v); /

8、將頂點(diǎn)v插入圖中，v無/ 相關(guān)聯(lián)的邊 void InsertEdge (Vertex u,Vertex v); / 將邊 (u, v) 插入圖中 void DeleteVertex (Vertex v); / 刪除頂點(diǎn)v 及所有關(guān)聯(lián)的邊 void DeleteEdge (Vertex u,Vertex v); / 刪除邊 (u, v) Boolean IsEmpty ( ); / 判斷圖的頂點(diǎn)集合是否為空 List Adjacent(Vertex v); / 返回由所有與v鄰接的頂/ 點(diǎn)構(gòu)成的表; JYP186.2 圖的表示 下面討論三種最常用的表示，即鄰接矩陣，鄰接表和鄰接多表。具體采用何種

9、表示取決于實(shí)際應(yīng)用對圖的功能的需求。6.2.1 鄰接矩陣 設(shè)G = (V, E) 是一個有n個頂點(diǎn)的圖，n1。G的鄰接矩陣A是一個n n的二維數(shù)組，且滿足： 1 當(dāng)且僅當(dāng) (i, j)（或）是E(G)中 的一條邊Aij = 0 否則JYP19 G1和G3的鄰接矩陣： 注意，無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣則不一定是對稱的。JYP20 G4的鄰接矩陣：JYP21 根據(jù)鄰接矩陣，很容易判斷是否存在一條關(guān)聯(lián)任意兩個頂點(diǎn)i和j的邊。 對于無向圖，頂點(diǎn)i的度是矩陣的第i行元素之和。 對于有向圖，頂點(diǎn)i的出度是第i行元素之和，入度則是第i列元素之和。 在邊(i, j)（或）加權(quán)的情況下，Aij既

10、可用于表示邊的存在，又可用于保存權(quán)重信息。JYP22 采用鄰接矩陣，即使回答“圖G中有多少條邊？”這樣的基本問題也需要O(n2)時間。 設(shè)e是圖G中邊的條數(shù)，當(dāng)e n2時，如果采用只存儲圖G中存在的邊的表示方法，則可使求解上述問題所需的時間減少為O(e+n)。 由此產(chǎn)生了鄰接表。JYP236.2.2 鄰接表 將鄰接矩陣的n行表示為n個鏈接表。圖G中的每一個頂點(diǎn)都有一個表。表i的結(jié)點(diǎn)表示頂點(diǎn)i所鄰接到的所有頂點(diǎn)，如下所示： 每個結(jié)點(diǎn)至少有兩個字段：data和link。data存放鄰接自頂點(diǎn)i的頂點(diǎn)號。JYP24G1的鄰接表：JYP25G3的鄰接表：JYP26G4的鄰接表：JYP27 注意，每個表

11、中的頂點(diǎn)不必有序。每個表有一個頭結(jié)點(diǎn)。全部頭結(jié)點(diǎn)順序存儲，以便隨機(jī)訪問任意頂點(diǎn)的鄰接表。 基于鄰接表的類Graph：class Graph private: List* HeadNodes; int n;public: Graph (const int vertices = 0): n(vertices) HeadNodes = new Listn; ;JYP28設(shè)有n個頂點(diǎn)和e條邊無向圖需要n個頭結(jié)點(diǎn)和2e個表結(jié)點(diǎn)。頂點(diǎn)i的度可通過計(jì)數(shù)表i中的結(jié)點(diǎn)個數(shù)確定。整個圖的邊數(shù)可用O(e+n)時間確定。JYP29有向圖需要n個頭結(jié)點(diǎn)和e個表結(jié)點(diǎn)。頂點(diǎn)i的出度可通過計(jì)數(shù)表i中的結(jié)點(diǎn)個數(shù)確定。為了確定任

12、意頂點(diǎn)的入度，可先將數(shù)組cn初始化為0，然后遍歷鄰接表。每訪問到一個data值為i的結(jié)點(diǎn)，就將ci累加1。遍歷完成后，ci即為頂點(diǎn)i的入度，0in1。整個圖的邊數(shù)也可用O(e+n)時間確定。JYP30 如果經(jīng)常需要訪問鄰接到頂點(diǎn)i的頂點(diǎn)，則可以再建立圖的反向鄰接表。每一個頂點(diǎn)都有一個表。表i表示鄰接到頂點(diǎn)i的所有頂點(diǎn)，如下所示：JYP31G3的反向鄰接表如下所示：JYP32 還可以簡化稀疏矩陣的鏈表表示結(jié)構(gòu)，用于表示圖。這時，每個結(jié)點(diǎn)表示一條邊，并有四個字段。結(jié)點(diǎn)結(jié)構(gòu)為：其中，tail和head分別表示邊的尾頂點(diǎn)和頭頂點(diǎn)。通過col，將具有相同頭的邊結(jié)點(diǎn)鏈接起來（起反向鄰接表作用）；通過row

13、，將具有相同尾的邊結(jié)點(diǎn)鏈接起來（起鄰接表作用）。頭結(jié)點(diǎn)仍然順序存儲。 JYP33采用這種方法，G3表示為下面的正交表結(jié)構(gòu)： 在以上表示中，當(dāng)需要保存邊的權(quán)重信息時，可以在結(jié)點(diǎn)中增加字段weight。JYP346.2.3 鄰接多表 鄰接表用于無向圖時，每條邊 (u, v) 表示為兩個結(jié)點(diǎn)。 在有的應(yīng)用中，要求不論從哪個頂點(diǎn)訪問一條邊，都要將這條邊打上已訪問標(biāo)記。為此，可以以邊為中心，構(gòu)建圖的鄰接表，從而形成鄰接多表。 在鄰接多表中，一個結(jié)點(diǎn)正好與一條邊對應(yīng)，但每個結(jié)點(diǎn)處于兩個表中（分別為邊的兩個頂點(diǎn)相應(yīng)的鄰接表）。此結(jié)點(diǎn)結(jié)構(gòu)為：JYP35其中，m是邊的訪問標(biāo)記，path1用于鏈接含頂點(diǎn)verte

14、x1的邊的結(jié)點(diǎn)，path2用于鏈接含頂點(diǎn)vertex2的邊的結(jié)點(diǎn)。基于鄰接多表的類Graph可如下定義：enum Boolean FALSE, TRUE;class Graph;/ 向前聲明class GraphEdge friend Graph;private: Boolean m; int vertex1, vertex2; GraphEdge *path1, *path2;JYP36typedef GraphEdge *EdgePtr;class Graph private: EdgePtr *HeadNodes; int n;public: Graph(const int);Graph

15、:Graph(const int vertices = 0) : n(vertices) HeadNodes = new EdgePtrn; / 建立頭結(jié)點(diǎn)數(shù)組 for (int i = 0; i n; i+) HeadNodesi = 0;JYP37G1的鄰接多表如下： JYP38 假設(shè)結(jié)點(diǎn)p表示的邊含頂點(diǎn)u和v，則已知u求v需要如下判斷： if ( pvertex1 = u ) v = pvertex2; else v = pvertex1; 將一條邊加入鄰接多表的操作只需要O(1)時間，如下列程序所示：void Graph:InsertEdge (int u, int v ) / 將邊(

16、u, v) 加入/ 鄰接多表 GraphEdge *p = new GraphEdge;/ 建立一個新的邊結(jié)點(diǎn) pm = FALSE; pvertex1 = u; pvertex2 = v; ppath1 = HeadNodes u; ppath2 = HeadNodes v; HeadNodes u = HeadNodes v = p;JYP396.3 連通圖的遍歷 給定一個有n個頂點(diǎn)的連通圖G = (V, E) 和V(G) 中的一個頂點(diǎn)v，對圖G的遍歷是指，從v出發(fā)，訪問V(G) 中所有從v（經(jīng)過E(G) 中的邊）可到達(dá)的頂點(diǎn)，且只訪問每個頂點(diǎn)一次。 由于圖中可能存在環(huán)路，為防止重復(fù)訪問頂

17、點(diǎn)，需設(shè)置一個訪問標(biāo)記數(shù)組visitedn。JYP40連通圖遍歷的兩種最基本的方法： 深度優(yōu)先搜索 廣度優(yōu)先搜索 雖然這些方法既適用于無向圖又適用于有向圖，但為了簡化分析，假設(shè)下面討論的是無向圖。JYP416.3.1 深度優(yōu)先搜索 深度優(yōu)先搜索: 首先訪問起始頂點(diǎn)v; 接著在與v鄰接的頂點(diǎn)中選一個未被訪問過的頂點(diǎn)w，再以w為起始頂點(diǎn)啟動新的深度優(yōu)先搜索; 當(dāng)?shù)竭_(dá)一個所有鄰接頂點(diǎn)都被訪問過的頂點(diǎn)u時，則回退到最近剛被訪問過并有一個未被訪問過的鄰接頂點(diǎn)x的頂點(diǎn)，再以x為起始頂點(diǎn)啟動新的深度優(yōu)先搜索; 當(dāng)不存在從任何已訪問過的頂點(diǎn)可到達(dá)的未被訪問頂點(diǎn)時，搜索結(jié)束。JYP42 下列程序給出了實(shí)現(xiàn)以上過

18、程的遞歸算法:void Graph:DFS ( ) / 驅(qū)動程序 visited = new Booleann;/ 設(shè)visited已說明為Graph的/ Boolean* 數(shù)據(jù)成員 for (int i = 0; i n; i+) visitedi = FALSE; / 初始化，所有/ 頂點(diǎn)都未被訪問 DFS (0);/ 從頂點(diǎn)0開始搜索 delete visited; JYP43void Graph:DFS (const int v) / 遞歸核心，訪問所有先前未 / 被訪問過，且可從v到達(dá)的頂點(diǎn) visitedv = TRUE; for (每一個與v鄰接的頂點(diǎn)w) / 具體代碼與圖的表示

19、有關(guān) if (!visitedw ) DFS (w);JYP44 例6.1 考慮下面的圖G5：JYP45 假設(shè)DFS(v) 按頂點(diǎn)號升序選取與v鄰接的頂點(diǎn)w。如果從頂點(diǎn)0出發(fā)作深度優(yōu)先搜索，則G中頂點(diǎn)被訪問的順序?yàn)椋?，1，3，7，4，5，2，6。 如果用頂點(diǎn)編號表示被訪問頂點(diǎn)，（頂點(diǎn)編號）表示檢查先前已被訪問過的頂點(diǎn)，（回退到x）表示回退到頂點(diǎn)x，則實(shí)際的搜索軌跡為： 0，1，（0），3，（1），7，（3），4，（1），（7），（回退到7），5，2，（0），（5），6，（2），（7），（回退到2），（回退到5），（7），（回退到7），（6），（回退到3），（回退到1），（4），（回退到0），

20、（2）。JYP46 分析：假設(shè)圖G有e條邊，由于G是連通的，所以en1。 若采用鄰接表表示，算法可順著頂點(diǎn)v的鄰接表找到所有與v鄰接的頂點(diǎn)w。在每個頂點(diǎn)v上只調(diào)用DFS一次，需要O(dv)時間，這里dv是頂點(diǎn)v的度。 整個搜索訪問n個頂點(diǎn)，所需時間為O( ) = O(e)。 若采用鄰接矩陣表示，確定所有與v鄰接的頂點(diǎn)w需要O(n)時間，總的搜索時間為O(n2)。 JYP476.3.2 廣度優(yōu)先搜索 廣度優(yōu)先搜索: 首先訪問起始頂點(diǎn)v； 接著依次訪問所有與v鄰接的未被訪問過的頂點(diǎn)； 然后再依次訪問所有與這些新被訪問的頂點(diǎn)鄰接的未被訪問過的頂點(diǎn)，如此繼續(xù)，直到所有頂點(diǎn)都被訪問為止。JYP48 可用

21、一個隊(duì)列q保存需要訪問的頂點(diǎn)，下列程序給出了實(shí)現(xiàn)以上過程的算法：void Graph:BFS (int v) / 從頂點(diǎn)v開始 visited = new Booleann; / 設(shè)visited已說明為Graph的/ Boolean* 數(shù)據(jù)成員 for (int i = 0; i n; i+) visitedi = FALSE; / 初始化， / 所有頂點(diǎn)都未被訪問 visitedv = TRUE; Queue q;/ q是一個隊(duì)列 q.Add(v); / 將頂點(diǎn)v加到隊(duì)列q中JYP49while (!q.IsEmpty ( ) v = *q.Delete(v); / 從隊(duì)列q中刪除頂點(diǎn) f

22、or (每一個與v鄰接的頂點(diǎn)w) / 具體代碼與圖的表示有關(guān) if (!visitedw ) visitedw = TRUE; q.Add(w); / while結(jié)束 delete visited; JYP50 例6.2 仍然考慮圖G5，并假設(shè)其鄰接表的結(jié)點(diǎn)按相應(yīng)頂點(diǎn)號升序排列。 如果從頂點(diǎn)0出發(fā)作廣度優(yōu)先搜索，則首先訪問頂點(diǎn)0，接著訪問頂點(diǎn)1和2，然后訪問頂點(diǎn)3，4，5和6，最后訪問頂點(diǎn)7。JYP51 分析：每個頂點(diǎn)加入隊(duì)列一次，所以while循環(huán)迭代n次。 若采用鄰接表表示，該循環(huán)的總代價為O( ) = O(e)，這里dv是頂點(diǎn)v的度。 若采用鄰接矩陣表示，確定所有與v鄰接的頂點(diǎn)w需要O(

23、n)時間，總的時間為O(n2)。 JYP526.3.3 生成樹 由于圖G是連通的，所以從任意頂點(diǎn)出發(fā)的深度優(yōu)先或廣度優(yōu)先搜索都將訪問G中所有頂點(diǎn)，并將E(G)劃分為兩個集合：T和N。 T是搜索過程中所用到的邊的集合，又稱為樹邊集合；N是圖中其余邊的集合，又稱為非樹邊集合。 初始設(shè)置T = ，并將語句 T = T (v, w) 插入DFS和BFS的if子句中，可求得T。 T中的邊構(gòu)成了一棵包含G的所有頂點(diǎn)的樹。任何只由G的邊構(gòu)成，并包含G的所有頂點(diǎn)的樹稱為G的生成樹。JYP53 由深度優(yōu)先搜索形成的生成樹稱為深度優(yōu)先生成樹，下圖是從G5的頂點(diǎn)0開始作深度優(yōu)先搜索形成的生成樹：JYP54 由廣度優(yōu)

24、先搜索形成的生成樹稱為廣度優(yōu)先生成樹，下圖是從G5的頂點(diǎn)0開始作廣度優(yōu)先搜索形成的生成樹：JYP55 若將非樹邊 (v, w) 加入任何生成樹T中，則會形成環(huán)路。該環(huán)路由邊 (v, w) 和T中從w到v的路徑構(gòu)成。 例如，將 (1, 4) 加入前面的深度優(yōu)先生成樹中后形成的環(huán)為1，3，7，4，1。 此性質(zhì)可用于建立獨(dú)立的電路方程式。 作為第二個性質(zhì)，生成樹是G的最小子圖G，使得V(G) = V(G) 且G是連通的。任何有n個頂點(diǎn)的連通圖至少有n1條邊，而有n1條邊的連通圖都是樹。JYP566.4 圖的連通性 6.4.1 連通分量 對于可能不連通的無向圖G，可以通過調(diào)用DFS或BFS并檢查是否存

25、在任何未被訪問的頂點(diǎn)來判定G是否連通。 設(shè)v是尚未被訪問的頂點(diǎn)，反復(fù)調(diào)用DFS(v) 或BFS(v) 即可生成G的連通分量。JYP57 下面是生成G的連通分量的算法：void ponents ( ) / 求圖的連通分量 visited = new Booleann;/ 設(shè)visited已說明為Graph/ 的Boolean* 數(shù)據(jù)成員 for (int i = 0; i n; i+) visitedi = FALSE; / 初始化，/ 所有頂點(diǎn)都未被訪問 for ( i = 0; i n; i+) if (!visitedi ) DFS (i); / 求包含頂點(diǎn)i的連通分量 ponent( )

26、; delete visited; JYP58 函數(shù) ponent輸出最近一次調(diào)用DFS訪問的所有頂點(diǎn)，以及關(guān)聯(lián)這些頂點(diǎn)的所有邊。 分析：若采用鄰接表表示，DFS的總時間為O(n + e)。如果DFS產(chǎn)生一個本次搜索新訪問的頂點(diǎn)表，再利用鄰接表，則輸出連通分量的頂點(diǎn)以及相關(guān)聯(lián)的邊的總時間為O(n + e)。for循環(huán)的控制和判斷需要O(n)時間。因此，生成全部連通分量的時間為O(n + e)。 若采用鄰接矩陣表示，算法所需要的時間為O(n2)。JYP596.4.2 雙連分量 雙連分量在連通性方面比一般的連通分量具有更高的要求，生成雙連分量的操作也更復(fù)雜一些。 假設(shè)無向圖G是連通的，下面給出雙連

27、分量的正式定義。 定義：G的頂點(diǎn)v是一個關(guān)節(jié)點(diǎn)當(dāng)且僅當(dāng)從G中刪除v及其關(guān)聯(lián)的邊后，剩下的圖至少有兩個連通分量。JYP60 例如，在下面的連通圖G6中，頂點(diǎn)1，4和7是關(guān)節(jié)點(diǎn)。JYP61 定義：雙連通圖是沒有關(guān)節(jié)點(diǎn)的連通圖。 圖G5是雙連通的，但圖G6不是雙連通的。 在表示通信網(wǎng)絡(luò)的圖中，邊表示通信鏈路，頂點(diǎn)表示通信站點(diǎn)，關(guān)節(jié)點(diǎn)顯然是薄弱環(huán)節(jié)。 定義：一個連通圖G的雙連分量是G的最大雙連通子圖。 JYP62 圖G6包含四個雙連分量，如下所示： JYP63 不難發(fā)現(xiàn)，同一個圖的兩個雙連分量最多有一個共同頂點(diǎn)。由此可推出，一條邊不可能出現(xiàn)在兩個或兩個以上的雙連分量中。因此，圖G的雙連分量劃分E(G)

28、。 圖G的雙連分量可利用G的任何深度優(yōu)先生成樹求得。JYP64 圖G6的以頂點(diǎn)0為根的深度優(yōu)先生成樹如下：JYP65其中，非樹邊用虛線表示。頂點(diǎn)旁的數(shù)字稱為該頂點(diǎn)的深度優(yōu)先數(shù)，簡稱為dfn。一個頂點(diǎn)的dfn表示該頂點(diǎn)在深度優(yōu)先搜索中被訪問的順序。 例如，在前面的G6生成樹中，dfn(0) = 1，dfn(1) = 2，以及dfn(7) = 5。 注意，在深度優(yōu)先生成樹中，如果頂點(diǎn)u是v的祖先，則dfn(u) dfn(v)。JYP66 相對于生成樹T，當(dāng)且僅當(dāng)u是v的祖先或v是u的祖先時，非樹邊 (u, v) 才是一條回邊。 例如，(4, 1) 和 (6, 7) 是回邊。 不是回邊的非樹邊稱為橫

29、邊。根據(jù)深度優(yōu)先搜索的規(guī)律，相對于任意一個圖的任何深度優(yōu)先生成樹，該圖不可能有橫邊。JYP67 因此，深度優(yōu)先生成樹的根是關(guān)節(jié)點(diǎn)的充分必要條件是它至少有兩個子女。 任何其它頂點(diǎn)u是關(guān)節(jié)點(diǎn)的充分必要條件是u至少有一個子女w，使得經(jīng)過只由w，w的后代以及一條回邊構(gòu)成的路徑不可能到達(dá)u的祖先，因?yàn)閯h除頂點(diǎn)u及其關(guān)聯(lián)的邊將使w及其后代與u的祖先斷開聯(lián)系。JYP68 假設(shè)頂點(diǎn)w的祖先包括w本身。 為了表示一個頂點(diǎn)經(jīng)過其后代以及一條回邊所能到達(dá)的最高祖先，對于圖G的每個頂點(diǎn)w，定義low(w) 為從w經(jīng)過其后代以及一條回邊所能到達(dá)的最高祖先的dfn。 顯然，low(w)是從w經(jīng)過其后代以及一條回邊所能到達(dá)

30、的頂點(diǎn)的dfn中最低的，并可由以下公式計(jì)算： low(w) = min dfn(w), min low(x)| x是w的一個子女, min dfn(x)| (w, x) 是一條回邊JYP69 于是，u是關(guān)節(jié)點(diǎn)的充分必要條件是：u或者是至少有兩個子女的深度優(yōu)先生成樹的根，或者u不是根結(jié)點(diǎn)但有一個子女w，使得low(w)dfn(u)。 下面是G6的以頂點(diǎn)0為根的深度優(yōu)先生成樹中各頂點(diǎn)的dfn和low值： 頂點(diǎn)01234567 dfn12734685 low12522555JYP70 修改DFS可得到計(jì)算一個連通圖各頂點(diǎn)的dfn和low值的函數(shù)DfnLow：void Graph:DfnLow (co

31、nst int x ) / 在頂點(diǎn)x開始DFS num = 1; / num是Graph 的類型為int的數(shù)據(jù)成員 dfn = new intn; low = new intn; / dfn和low都是Graph 的 / 類型為int *的數(shù)據(jù)成員 for ( int i = 0; i n; i+ ) dfni = lowi = 0; DfnLow ( x, -1 ); / x是根，其雙親是偽頂點(diǎn)-1 delete dfn; delete low;JYP71void Graph:DfnLow ( int u, int v ) / 從u開始深度優(yōu)先搜索并 / 計(jì)算dfn和low。v是u的雙親 d

32、fnu = lowu = num+; for (每一個與u鄰接的頂點(diǎn)w) / 具體代碼與圖的表示有關(guān) if (dfnw = 0) / w 是未被訪問頂點(diǎn) DfnLow (w, u); lowu = min2 (lowu, loww); / min2(x,y)返回x和y的 / 較小者 else if (w != v) lowu = min2 ( lowu, dfnw ); / 回邊。注 / 意(v, u)不是回邊JYP72 注意，在深度優(yōu)先生成樹中，若v是u的雙親，則 (u, v) 一定不是回邊。 函數(shù)DfnLow(u, v)的參數(shù)v就是為區(qū)分這種情況而設(shè)的。 深度優(yōu)先搜索的第一個頂點(diǎn)x無雙親，

33、因此對其的調(diào)用形式為DfnLow(x, 1)。 函數(shù)DfnLow(u, v)用到的另一個函數(shù)min2返回其兩個參數(shù)的較小者。JYP73 在DfnLow的基礎(chǔ)上進(jìn)一步處理，可以將連通圖的邊劃分為雙連分量。 注意，當(dāng)DfnLow(w, u)返回后，loww已計(jì)算好。如果lowwdfnu，則可確定一個新的雙連分量。 通過將搜索時首次遇到的邊存入棧中，可以求得一個雙連分量的全部邊。JYP74 設(shè)深度優(yōu)先搜索最近訪問的頂點(diǎn)是u，且頂點(diǎn)w與u鄰接，則在以下兩種情況中，(u, w)是首次遇到的邊： （1）w是未被訪問的頂點(diǎn) （2）w是已被訪問的頂點(diǎn)而且是u的祖先 由于未被訪問的頂點(diǎn)的dfn值初始化為0，祖先

34、的dfn值小于后代的，所以兩種情況都可歸結(jié)為dfnw dfnu。 JYP75 函數(shù)Biconnected實(shí)現(xiàn)了上述過程：void Graph:Biconnected ( ) num = 1; dfn = new intn; low = new intn; for ( int i = 0; i 1。 dfnu = lowu = num+;JYP76 for (每一個與u鄰接的頂點(diǎn)w) / 具體代碼與圖的表示有關(guān) if (v != w & dfnw = dfnu) cout “新雙連分量：” endl; do 從棧S刪除一條邊; 設(shè)此邊為 (x, y); cout x , y 0個頂點(diǎn)，e條邊。

35、最典型的構(gòu)造最小生成樹的算法： 克魯斯卡爾（Kruskal）算法 普瑞姆（Prim）算法JYP79 這兩個算法都采用了一種稱為貪心方法的設(shè)計(jì)策略。 貪心方法分階段構(gòu)造最優(yōu)解。 在每個階段，根據(jù)一定的準(zhǔn)則做出當(dāng)時可能的最佳決策。由于后續(xù)階段不可更改本階段的決策，所以必須保證該決策將導(dǎo)致可行的解，即滿足問題規(guī)定的約束。JYP80 具體應(yīng)用到構(gòu)造最小生成樹的情況，應(yīng)采用最小代價準(zhǔn)則，而問題的解必須滿足下列約束： （1）只能選用圖中的邊 （2）正好用n 1條邊 （3）所選用的邊不形成環(huán)路。JYP816.5.1 克魯斯卡爾算法 設(shè)T是構(gòu)造中的最小生成樹，克魯斯卡爾算法通過每次往T中加入一條邊構(gòu)造最小生成

36、樹。 加入T的邊按代價不減少的順序選擇。 如果一條邊與已在T中的邊不形成環(huán)路，則將其加入T中。 如果G是連通的，則選入T中的邊正好是n 1條。JYP82 例6.3 構(gòu)造下圖的最小生成樹JYP83初始時未選任何邊： 加入邊 (1, 6) 后：JYP84加入邊(4, 5)后： 加入邊(1, 2)后：JYP85加入邊 (5, 6) 后： 這時，在尚未考慮的邊中，(2, 6) 的代價最小，但 (2, 6) 的加入將在生成樹中形成環(huán)路，因此將其放棄。JYP86加入邊(0, 5)后： 下一條需考慮的邊是 (4, 6)，由于 (4, 6) 的加入將在生成樹中形成環(huán)路，因此將其放棄。JYP87最終，加入邊(3

37、, 4) 后：JYP88 克魯斯卡爾算法的框架 ：T = ;while (T包含的邊少于n-1條) & (E非空) 從E中選一條代價最小的邊 (v, w); 從E中刪除 (v, w); if (v, w)不會在T中形成環(huán)路) 將 (v, w) 加入T中; else 放棄 (v, w);if (T包含的邊少于n-1條) cout “不存在最小生成樹” endl;JYP89 初始時，集合E包含圖G的全部邊。 如果將E組織為最小堆，則選擇并刪除代價最小的邊可用O(log e) 時間完成。構(gòu)造最小堆只需O(e) 時間。 算法最多選擇并刪除e條邊，其總代價為O(e log e)。 將T中同一個連通分量的

38、頂點(diǎn)組織為一個集合。如果兩個頂點(diǎn)v和w處于同一個集合，則邊 (v, w) 的加入將在T中形成環(huán)路。利用并查集算法，判斷e條邊的總時間為O(e.(e, n)。 因此，算法的時間復(fù)雜性為O(e log e)。JYP90 定理6.1：對于任意給定的無向連通圖G，克魯斯卡爾算法構(gòu)造G的一棵最小代價生成樹。 證明：我們需要證明：（a）只要存在生成樹，克魯斯卡爾算法就能構(gòu)造一棵生成樹；（b）所構(gòu)造的生成樹代價最小。 對于（a），注意克魯斯卡爾算法只放棄形成環(huán)路的邊，而刪除一個連通圖的環(huán)路中的一條邊所得到的圖仍然是連通的。 因此，如果G一開始是連通的，則T和E的邊總是構(gòu)成一個連通圖，算法不可能以E = 且|

39、T| 0）。注意k也是在U中而不在T中的邊的條數(shù)。 可通過將U轉(zhuǎn)換為T證明T和U代價相同。JYP92 這種轉(zhuǎn)換經(jīng)過k個步驟。每經(jīng)過一個步驟，在T中而不在U中的邊的條數(shù)減少1，且轉(zhuǎn)換后U的代價不變。最終，經(jīng)過k步轉(zhuǎn)換，U的代價和初始時相同，但已完全由T的邊構(gòu)成。這意味著T具有最小代價。 每一步轉(zhuǎn)換需將T中的一條邊e加到U中，并從U刪除一條邊f(xié)。邊e和f按下列方法選擇： （1） 設(shè)e是在T中而不在U中的代價最小的邊。由于k 0，這樣的邊一定存在。 （2） e加入U后將形成唯一的環(huán)路。設(shè)f是該環(huán)路中不在T中的邊。由于T中無環(huán)路，此環(huán)路一定存在一條不在T中的邊。JYP93 按照e和f的選擇方法，V =

40、 U + e f是一棵生成樹，且T有k 1條邊不在V中。 下面需要證明代價(V) = 代價(U)。 顯然，代價(V) =代價(U) + 代價(e) 代價(f)。 代價(e)不會小于代價(f)，否則生成樹V的代價比U的還小，而這是不可能的。JYP94 假設(shè)代價(e) 代價(f)，則克魯斯卡爾算法在e之前考察f。由于f不在T中，算法在考察時一定放棄了f。因此，f與T中代價小于等于代價(f) 的邊一定形成了環(huán)路。由于e是在T中而不在U中的代價最小的邊，T中代價小于等于代價(f) 的邊都在U中，因而U中存在環(huán)路。但U是生成樹，不可能有環(huán)路?？梢?，假設(shè)代價(e) 代價(f)導(dǎo)致矛盾。 于是，唯一可能的是

41、代價(e) = 代價(f)。 因此，代價(V) = 代價(U)。JYP956.5.2 普瑞姆算法 設(shè)TV是最小生成樹的已選頂點(diǎn)集合，T是最小生成樹的已選邊集合。普瑞姆算法首先任選圖G中一個頂點(diǎn)u，將u加入TV中。 然后將一條代價最小的邊 (u, v) 加入T中，使得T (u, v)仍然是一棵樹。 重復(fù)上述步驟，直到T包含n 1條邊為止。 注意，(u, v) 關(guān)聯(lián)的兩個頂點(diǎn)必有一個在TV中，另一個不在TV中。JYP96 普瑞姆算法的框架:TV = 0;/ 從頂點(diǎn)0開始構(gòu)造，假設(shè)G至少有一個頂點(diǎn)for (T = ; T包含的邊少于n -1條; 將(u, v)加入T) 令 (u, v) 為滿足 u

42、TV 且 v TV 的代價最小的邊; if (不存在這樣的邊) break; 將v加入TV;if (T包含的邊少于n-1條) cout “不存在最小生成樹” endl ;JYP97 用普瑞姆算法構(gòu)造下圖的最小生成樹的過程：JYP98JYP99JYP100JYP101 設(shè) 是不屬于TV的頂點(diǎn)集合。 對于任何v ，定義nearv為TV中使 cost(nearv, v)最小的頂點(diǎn)（若(v, w)E，則設(shè)cost(v, w) = ），則 cost(nearv,v) = 。 下一個加入TV的頂點(diǎn)v應(yīng)滿足：v ，且cost(nearv,v) = 。下一條加入T的邊自然是 (nearv,v)。JYP102

43、設(shè)w是 中與v鄰接的頂點(diǎn)。頂點(diǎn)v加入TV之后，如果cost(nearw,w) cost(v, w)，則將nearw改為v。 由此可以有效地實(shí)現(xiàn)普瑞姆算法。 如果用鄰接矩陣costij表示圖G，則算法的時間復(fù)雜性是O(n2)，因?yàn)樗惴偣策xn 1個頂點(diǎn)，每選一個頂點(diǎn)v及處理v對nearw（w 且w與v鄰接）的影響最多只需O(n)時間。JYP103 如果用鄰接表表示圖G并利用斐波納契堆，則可使算法的性能更好。對于v ，定義distv = cost(nearv,v)，可理解為頂點(diǎn)v到已構(gòu)造的部分最小生成樹的最近距離。 每次往TV中加入一個頂點(diǎn)，算法都需要確定頂點(diǎn)v，使得v ，且distv = 。這對

44、應(yīng)于 上的刪除最小元素操作。 由于v加入TV， 中與v鄰接的頂點(diǎn)的dist值可能減少。這對應(yīng)于 上的關(guān)鍵字減少操作。JYP104 關(guān)鍵字減少操作的總次數(shù)最多是圖中邊的條數(shù)。刪除最小元素操作的總次數(shù)是n 1。 初始時， 含n 1個頂點(diǎn)。如果以dist為關(guān)鍵字，將 組織為斐波納契堆，則需要n 1次插入操作初始化斐波納契堆。 接著需要執(zhí)行n 1次刪除最小元素操作和最多e次關(guān)鍵字減少操作。所有這些操作的代價是各操作的分?jǐn)偞鷥r之和，即 O(n log n + e)。 因此，算法的時間復(fù)雜性變?yōu)镺(n log n + e)。當(dāng)e遠(yuǎn)小于n2時，這顯然是一種改進(jìn)。JYP1056.6 最短路徑和傳遞閉包 一條路

45、徑的長度定義為該路徑的邊長之和。路徑的開始頂點(diǎn)稱為源點(diǎn)，最后一個頂點(diǎn)稱為終點(diǎn)。6.6.1 邊長非負(fù)時的單源點(diǎn)到所有終點(diǎn)的最短路徑 問題：給定一個有向圖G = (V, E)和一個源點(diǎn)v，以及圖中各條邊的長度length(i, j)，且length(i, j)0，求從v到G中其余各頂點(diǎn)的最短路徑。JYP106 觀察圖6.22(a)的有向圖：JYP107 以頂點(diǎn)0為源點(diǎn)，從0到1的最短路徑是0, 5, 6, 1，其長度為19。雖然這一路徑由三條邊構(gòu)成，但它還是比只含一條邊的0, 1路徑短。 從0到3不存在路徑。 圖6.22(b)給出了從0到1，2，4，5和6的最短路徑。 這些路徑按長度不減少順序列出

46、。JYP108 S 最短路徑已找到的終點(diǎn)（包括源點(diǎn)v）的集合。 對于 w S，定義distw為從v出發(fā)，只經(jīng)過S中的頂點(diǎn)，到達(dá)w的最短路徑的長度。 當(dāng)按長度不減少順序生成最短路徑時，可以發(fā)現(xiàn)： （1）若下一條最短路徑是到頂點(diǎn)u的，則該路徑始于v，終于u，并且中間只經(jīng)過S中的頂點(diǎn)。 為此必須證明始于頂點(diǎn)v的最短路徑中的所有中間頂點(diǎn)都在S中。JYP109 假設(shè)該路徑中存在一個頂點(diǎn)w且w S，則從v到u的路徑由從v到w和從w到u兩段路徑構(gòu)成，如下圖所示：JYP110 這一條經(jīng)過w的路徑長度一定比不經(jīng)過w的短，否則就沒必要經(jīng)過w。 由于每條邊的長度都是非負(fù)的，所以從v到w的路徑長度 distu。 而此

47、時從v到w的最短路徑尚未確定，這與按長度不減少順序生成最短路徑的假設(shè)矛盾。 因此，不存在不在S中的中間頂點(diǎn)。JYP111 （2）根據(jù)dist定義和（1），下一條最短路徑的終點(diǎn)u必須滿足： distu = 如果多個不在S中的頂點(diǎn)的dist都具有同樣的最小值，則可任選其中之一。 （3）頂點(diǎn)u按（2）的條件被選中后即成為S的成員，相應(yīng)的從v到u的最短路徑也被確定。JYP112 這時，對于任何不屬于S且鄰接自u的頂點(diǎn)w，distw可能減少。若確實(shí)減少，則一定是由于存在一條從v到u，再從u到w的更短路徑，如下圖所示：JYP113 從v到u的路徑一定是從v到u的最短路徑，而從u到w的路徑就是邊。 因此從v

48、到w的路徑長度為distu + length(u, w)。 假設(shè)從u到w的路徑含有任何屬于S的中間頂點(diǎn)x，如下圖所示：JYP114則該路徑不可能使distw更短。因?yàn)椋?（a）路徑vux的長度 distx （b）路徑vuxw的長度 路徑vxw的長度 distwJYP115 由上觀察可得最短路徑算法。 設(shè)G的n個頂點(diǎn)編號為0, 1, , n 1。 集合S用Boolean數(shù)組s表示。 到終點(diǎn)w（0w n 1）的最短路徑所經(jīng)過的最后一個頂點(diǎn)用pathw記載。 設(shè)圖G本身由長度鄰接矩陣表示，則lengthij是邊的長度。若E且ij，則將lengthij設(shè)置為LARGEINT。lengthii可設(shè)置為任

49、何非負(fù)數(shù)。JYP116 類Graph的定義如下：class Graph private: int lengthnmaxnmax; int distnmax; int pathnmax; Boolean snmax;public: void ShortestPath(const int, const int); int choose(const int); JYP117 函數(shù)ShortestPath給出了算法的實(shí)現(xiàn)：1 void Graph:ShortestPath(const int n, const int v) 2 for (int i = 0; i n; i+) 3 si = FALSE

50、; disti = lengthvi; 4 if ( i != v & disti LARGEINT) pathi = v; else pathi = 1;5 6 sv = TRUE; distv = 0;7 for (i = 0; i n-2; i+) / 確定從v開始的n 1條路徑8 int u = choose(n); / 選擇u，使得對于所有sx = / FALSE，distu = 最小的distx9 su = TRUE;JYP11810 for ( int w = 0; w n; w+)11 if (!sw)12 if (distu + lengthuw distw) distw =

51、 distu + lengthuw; pathw = u; 13 / for (i = 0;) 結(jié)束14 JYP119 分析：第2行的for循環(huán)需要O(n)時間。第7行的for循環(huán)執(zhí)行n 2次，每次需要O(n)時間用于第8行的選擇和第10到12行的更新dist值。因此，該循環(huán)的總時間是O(n2)。 整個算法的時間是O(n2)。 即使采用鄰接表，第10到12行的總時間可減少到O(e)（因?yàn)橹挥朽徑幼評的頂點(diǎn)的dist可能變化），第8行的總時間仍然是O(n2)。 JYP120 例6.4 對于圖6.22(a)，ShortestPath的運(yùn)行情況：JYP121 根據(jù)path，很容易推算出從源點(diǎn)0到終點(diǎn)

52、u的最短路徑。 以終點(diǎn)4為例，path4 = 6，path6 = 5，path5 = 0，反過來排列，可得路徑0, 5, 6, 4，這就是從源點(diǎn)0到終點(diǎn)4的最短路徑，其長度為dist4 = 28。JYP122 應(yīng)用斐波納契堆和鄰接表，可使算法的時間復(fù)雜性減少為O(n log n + e)。 每次迭代，都需要確定頂點(diǎn)u，使得u ，且distu = 。這對應(yīng)于上的刪除最小元素操作。 由于u加入S， 中與u鄰接的頂點(diǎn)的dist值可能減少。這對應(yīng)于上的關(guān)鍵字減少操作。JYP123 初始時， 含n 1個頂點(diǎn)。如果以dist為關(guān)鍵字，將 組織為斐波納契堆，則需要n 1次插入操作。 接著需要執(zhí)行n 2次刪除

53、最小元素操作和最多e次關(guān)鍵字減少操作。 所有這些操作的代價是各操作的分?jǐn)偞鷥r之和，即 O(n log n + e)。 因此，算法的時間復(fù)雜性是O(n log n + e)。 當(dāng)e遠(yuǎn)小于n2時，這種實(shí)現(xiàn)顯然更好。 JYP124 如果圖中存在邊長為負(fù)的情況，則ShortestPath不一定給出正確結(jié)果。 例如，在下圖中設(shè)v = 0是源點(diǎn)，則算法先計(jì)算dist2 = 5，并確定從0到2的最短路徑是0, 2，再計(jì)算dist1 = 7。而實(shí)際上從0到2的最短路徑是0, 1, 2，其長度為2。JYP1256.6.2 所有頂點(diǎn)對之間的最短路徑 問題：找到所有頂點(diǎn)對u和v（u v）之間的最短路徑。 對于邊長非

54、負(fù)的圖，可以每一個頂點(diǎn)作為源點(diǎn)，將問題轉(zhuǎn)化為n個單源點(diǎn)到所有終點(diǎn)的最短路徑問題，求解所需總時間為O(n3)。 如果采用斐波納契堆，則所需總時間為O(n2 log n + n e)。 對于邊長可能為負(fù)，但不存在長度為負(fù)的環(huán)路的圖，可以利用動態(tài)規(guī)劃的方法得到一個概念更加簡單且時間復(fù)雜性也是O(n3)的算法。 JYP126 定義Akij為經(jīng)過的中間頂點(diǎn)標(biāo)號不大于k的從i到j(luò)的最短路徑的長度，則An-1ij是圖G中從i到j(luò)的最短路徑的長度。 A-1ij = lengthij 。 求所有頂點(diǎn)對之間的最短距離算法的基本思想： 從A-1開始，連續(xù)生成矩陣A0，A1，An-1。JYP127 如果已生成Ak-1

55、，那么對于任意頂點(diǎn)對i和j，可以根據(jù)以下兩種情況之一生成Ak： （1）經(jīng)過的中間頂點(diǎn)標(biāo)號不大于k的從i到j(luò)的最短路徑不經(jīng)過頂點(diǎn)k，因此其長度是Ak-1ij。 （2）該最短路徑經(jīng)過頂點(diǎn)k。該路徑由從i到k的子路徑和從k到j(luò)的子路徑構(gòu)成。由于不存在長度為負(fù)的環(huán)路，所以經(jīng)過頂點(diǎn)k不可能使這些子路徑更短。因此，這些子路徑一定是經(jīng)過的中間頂點(diǎn)標(biāo)號不大于k 1的從i到k和從k到j(luò)的最短路徑，它們的長度分別是Ak-1ik 和Ak-1kj。JYP128 因此，對于k0，有 ： Akij = min Ak-1ij，Ak-1ik + Ak-1kj 設(shè)從i到j(luò)的最短路徑中j前面的頂點(diǎn)為pathij，則pathij前

56、面的頂點(diǎn)為pathipathij，整個路徑為：i = pathmij，pathm-1ij，pathij，j（假設(shè)路徑中有m + 1個頂點(diǎn)）。 若從i到j(luò)的最短路徑經(jīng)過頂點(diǎn)k，則該路徑中j前面的頂點(diǎn)一定是從k到j(luò)的子路徑中j前面的頂點(diǎn)，因此pathij = pathkj。當(dāng)從i到j(luò)的最短路徑只是一條邊時，pathij = i。JYP129 算法AllLengths計(jì)算An-1并生成pathij：1 void Graph:AllLengths(const int n) / 在類Graph定義中將 / path修改為pathnmax nmax，并增加數(shù)據(jù)成員a 2 for (int i = 0; i

57、 n; i+)3 for (int j = 0; j n; j+) 4 aij = lengthij; / 初始化a5 if ( i != j & aij LARGEINT) pathij = i; else pathij = 1;6 7 for ( int k = 0; k n; k+) / 經(jīng)過的中間頂點(diǎn)標(biāo)號不大于k8 for ( i = 0; i n; i+) / 所有頂點(diǎn)對9 for ( j = 0; j n; j+)JYP13010 if (aik + akj 0的從i到j(luò)的路徑則A+ij =1，否則A+ij =0。 定義：圖G的自反傳遞閉包矩陣A*是一個矩陣，且滿足：如果存在一條長

58、度0的從i到j(luò)的路徑則A*ij =1，否則A*ij =0。 JYP135 對于下面的有向圖：其A+和A*如下一頁所示。顯然，A+和A*的差別僅在對角線上，A*ii =1總是成立的。JYP136JYP137 簡化函數(shù)AllLengths，將其中的length和a改為Boolean數(shù)組， lengthij = TRUE當(dāng)且僅當(dāng) 是G的邊，可得到算法TransitiveClose：1 void Graph:TransitiveClose(const int n) 2 for (int i = 0; i n; i+)3 for (int j = 0; j n; j+)4 aij = lengthij;

59、 / 初始化a5 for ( int k = 0; k n; k+) / 經(jīng)過的中間頂點(diǎn)標(biāo)號不大于k6 for ( i = 0; i n; i+) / 所有頂點(diǎn)對7 for ( j = 0; j n; j+)8 aij = aij | aik & akj;9 JYP138 算法結(jié)束時，最終的a就是A+。將A+中對角線元素全部設(shè)置為1則可得到A*。 無向圖的傳遞閉包更容易計(jì)算： 處于同一個連通分量中的任何兩個頂點(diǎn)之間存在一條路徑 可以先求出圖的連通分量，再確定A+，總的時間為O(n2)。對于同一個連通分量中的兩個不同頂點(diǎn)i和j，A+ij = 1。A+ii = 1當(dāng)且僅當(dāng)i所在的分量包含至少兩個頂

60、點(diǎn)。 JYP1396.7 活動網(wǎng)絡(luò) 6.7.1 AOV網(wǎng)絡(luò) 一個工程可以分解為若干個子工程，這些子工程稱為活動。 活動之間可能存在先后關(guān)系。用有向圖可以更清楚地表示活動之間的關(guān)系。 定義：一個用頂點(diǎn)表示活動，邊表示活動之間的先后關(guān)系的有向圖稱為AOV（activity-on-vertex）網(wǎng)絡(luò)。JYP140 定義：在一個AOV網(wǎng)絡(luò)G中，如果存在一條從頂點(diǎn)i到頂點(diǎn)j的有向路徑，則頂點(diǎn)i是頂點(diǎn)j的前驅(qū)，相應(yīng)地，頂點(diǎn)j是頂點(diǎn)i的后繼。如果是G的一條邊，則頂點(diǎn)i是頂點(diǎn)j的直接前驅(qū)，相應(yīng)地，頂點(diǎn)j是頂點(diǎn)i的直接后繼。 定義：拓?fù)漤樞蚴菆D中所有頂點(diǎn)組成的一種線性序列，使得對于圖中任意兩個頂點(diǎn)i和 j，如果