第8章 圖電子課件

第8章圖本章講解圖。要求理解圖的基本概念；掌握圖的存儲結構；掌握圖的遍歷；掌握最小生成樹相關的Prim算法和Kruskal算法；掌握求最短路徑相關的Dijkstra算法和Floyd算法；理解拓撲排序；靈活應用圖。到古鎮(zhèn)游最喜歡點石磨豆花這道菜了，配上調料碟子，以及其他小吃和米飯，一桌子還是挺豐盛的又不浪費。如果把桌子上的碗、盤、碟看作頂點，把吃貨們在用餐時筷子夾菜的軌跡當作畫邊，其實就是在編織圖。提綱8.1圖基本概念8.2圖存儲結構8.3圖遍歷8.4生成樹和最小生成樹8.5最短路徑8.6拓撲排序8.7關鍵路徑8.8圖應用8.9圖學習總結8.1圖基本概念圖在日常生活中常見，如城市軌道交通圖、高德導航地圖、衛(wèi)星軌道圖、工程項目進度圖、校園地理圖，等等。不同于前面介紹的線性表和樹，圖的邏輯結構是多對多的關系。8.1圖基本概念定義圖G（Graph）由兩個集合V（Vertex）和E（Edge）組成，記為G=(V，E)。V是頂點的有限集合，記為V(G)。E是連接V中兩個不同頂點（頂點對）的邊的有限集合，記為E(G)。8.1圖基本概念頂點集V={v0,v1,v2,v3,v4,v5,v6,v7,v8}，邊集E={(v0,v1),(v0,v2),(v1,v2)...(v6,v8),(v7,v8)}，其中邊上的數(shù)字代表該邊的權值。8.1圖基本概念2.分類圖分為無向圖和有向圖2大類。8.1圖基本概念基本術語鄰接點：在一個無向圖中，若存在一條邊(i，j)，則稱頂點i和頂點j為該邊的兩個端點，它們互為鄰接點。出邊：在一個有向圖中，若存在一條邊<i,j>，則稱此邊是頂點i的1條出邊。入邊：在一個有向圖中，若存在一條邊<i,j>，則稱此邊是頂點j的1條入邊。起點：在一個有向圖中，若存在一條邊<i,j>，則稱i為起點。終點：在一個有向圖中，若存在一條邊<i,j>，則稱j為終點。頂點的度：在無向圖中，頂點所連接的邊數(shù)。8.1圖基本概念入度：在有向圖中，以頂點j為終點的入邊的數(shù)目。出度：在有向圖中，以頂點i為起點的出邊的數(shù)目。完全無向圖：圖中每2個頂點之間都存在著1條邊。含有n個頂點的完全無向圖有n(n-1)/2條邊。如圖8.3（1）所示。完全有向圖：圖中每2個頂點之間都存在著方向相反的2條邊。含有n個頂點的完全有向圖包含有n(n-1)條邊。如圖8.3（2）所示。8.1圖基本概念稠密圖：1個圖接近完全圖。稀疏圖：1個圖含有較少的邊數(shù)（即無向圖有e<<n(n-1)/2，有向圖有e<<n(n-1)）。子圖：設有兩個圖G=(V，E)和G'=(V'，E')，若V'是V的子集，且E'是E的子集，則稱G'是G的子圖。如圖8.4所示。8.1圖基本概念路徑：在一個圖G=(V，E)中，從頂點i到頂點j的一條路徑是一個頂點序列(i，i1，i2，…，im，j)，若此圖G是無向圖，則邊(i，i1)，(i1，i2)，…，(im-1，im)，(im，j)屬于E(G)；若此圖是有向圖，則<i，i1>，<i1，i2>，…，<im-1，im>，<im，j>屬于E(G)。路徑長度：是指一條路徑上經過的邊的數(shù)目。簡單路徑：若一條路徑上除開始點和結束點可以相同其余頂點均不相同的路徑。如圖8.5所示。8.1圖基本概念回路或環(huán)：1條路徑上的開始點與結束點為同一個頂點的路徑。簡單回路或簡單環(huán)：開始點與結束點相同的簡單路徑。如圖8.6所示。連通的：在無向或有向圖G中，若從頂點i到頂點j有路徑，則i和j是連通的。連通圖和非連通圖：若圖G中任意兩個頂點都連通，則稱G為連通圖，否則稱為非連通圖。連通分量：無向圖G中的極大連通子圖。顯然，任何連通圖的連通分量只有一個即本身，而非連通圖有多個連通分量。8.1圖基本概念強連通圖：若有向圖G中的任意兩個頂點i和j都連通，即從頂點i到頂點j和從頂點j到頂點i都存在路徑，則稱圖G是強連通圖。強連通分量：有向圖G中的極大強連通子圖。顯然，強連通圖只有1個強連通分量即本身，非強連通圖有多個強連通分量。一般地單個頂點自身就是一個強連通分量。如圖8.6所示。8.1圖基本概念權：圖中每一條邊都可以附有一個對應的數(shù)值。權可以表示從一個頂點到另一個頂點的距離或花費的代價。網(wǎng)或帶權圖：邊上帶有權的圖。如圖8.7所示。8.1圖基本概念

8.2圖存儲結構圖的存儲結構分為順序存儲結構和鏈式存儲結構，前者為鄰接矩陣，后者為鄰接表。8.2.1鄰接矩陣

8.2.1鄰接矩陣【思考與練習8.2】寫出圖8.9所示的1個帶權有向圖的鄰接矩陣。答：

8.2.1鄰接矩陣圖的鄰接矩陣類MatGraph描述8.2.1鄰接矩陣【算法8.3】1個含有n個頂點e條邊的圖采用鄰接矩陣g存儲，設計以下算法：（1）若圖為無向圖，求每個頂點的度。（2）若圖為有向圖，求每個頂點的出度和入度。思路：（1）對于無向圖，用1個計數(shù)器統(tǒng)計鄰接矩陣某1行的非零元素個數(shù)。（2）對于有向圖，統(tǒng)計鄰接矩陣某1行的非零元素個數(shù)即得出度；統(tǒng)計鄰接矩陣某1列的非零元素個數(shù)即得入度。代碼見算法8.38.2.2鄰接表

8.2.2鄰接表【思考與練習8.3】畫出下圖所示的無向圖的鄰接表，并指出頂點b的度。答：

8.2.2鄰接表圖的鄰接表的表頭節(jié)點類VNode描述圖的鄰接表的邊節(jié)點類ArcNode描述圖的鄰接表類AdjGraph描述8.2.2鄰接表【算法8.6】1個含有n個頂點e條邊的圖采用鄰接表存儲，設計以下算法：（1）若圖為無向圖，求每個頂點的度。（2）若圖為有向圖，求每個頂點的出度和入度。思路：（1）對于無向圖，某個頂點的度就是該頂點為頭節(jié)點的單鏈表的節(jié)點個數(shù)。通過遍歷單鏈表并計數(shù)可以得到。（2）對于有向圖，某個頂點的出度就是該頂點為頭節(jié)點的單鏈表的節(jié)點個數(shù)；某個頂點的入度就是該頂點在單鏈表組（不含頭節(jié)點）中出現(xiàn)的次數(shù)。通過遍歷和比較以及計數(shù)可以得到。代碼見算法8.68.3圖遍歷從給定圖中任意指定的頂點（稱為初始點）出發(fā)，按照某種搜索方法沿著圖的邊訪問圖中的所有頂點，使每個頂點僅被訪問1次，這個過程稱為圖遍歷。圖的遍歷分為深度優(yōu)先搜索/遍歷（DFS，DepthFirstSearch）和廣度優(yōu)先搜索/遍歷(BFS，BreadthFirstSearch)。8.3圖遍歷舉例：上課之前，課代表要將手上的一摞作業(yè)本發(fā)給包含自己在內的每個同學，這個過程實質上課代表在進行遍歷，全班同學構成了圖的頂點，課代表對所有頂點進行了訪問且只訪問了1次。8.3.1深度優(yōu)先遍歷（1）首先訪問初始頂點v。（2）選擇1個與頂點v鄰接且沒被訪問過的頂點w，再從w出發(fā)進行深度優(yōu)先搜索。（3）遞歸上述過程，直到所有頂點遍歷完。8.3.1深度優(yōu)先遍歷

8.3.1深度優(yōu)先遍歷【算法8.8】圖G采用鄰接表存儲，設計1個深度優(yōu)先遍歷算法。思路：同算法8.7。只是將鄰接矩陣換成了鄰接表。代碼見算法8.88.3.2廣度優(yōu)先遍歷（1）訪問起始點v。（2）訪問頂點v的所有未被訪問過的鄰接點v1、v2、…、vt。（3）再按照v1、v2、…、vt的次序，訪問每1個頂點的所有未被訪問過的鄰接點。（4）依次類推，直到圖中所有頂點都被訪問過為止。8.3.2廣度優(yōu)先遍歷【算法8.9】圖G采用鄰接矩陣存儲，設計1個廣度優(yōu)先遍歷算法。思路：與二叉樹層次遍歷類同，圖的廣度優(yōu)先遍歷也可以借助1個隊列用非遞歸算法實現(xiàn)。（1）訪問起始頂點v，置visited[v]=1，將v入隊列qu。（2）若隊列非空，則出隊列。（3）訪問以出隊列元素所在行的所有非0非∞且visited標志為0的元素，置它們的visited標志為1，將它們入隊列qu。（4）重復（2）、（3），直到隊列為空。代碼見算法8.98.3.2廣度優(yōu)先遍歷【算法8.10】圖G采用鄰接表存儲，設計1個廣度優(yōu)先遍歷算法。思路：（1）訪問起始頂?shù)譾，置visited[v]=1，將v入隊列qu。（2）若隊列非空，則出隊列。（3）訪問以出隊列為頭節(jié)點的單鏈表中visited標志為0的所有節(jié)點，置它們的visited標志為1，將它們入隊列qu。（4）重復（2）、（3），直到隊列為空。代碼見算法8.108.4生成樹和最小生成樹通常生成樹是針對無向圖的，最小生成樹是針對帶權無向圖的。8.4.1生成樹和最小生成樹基本概念1.定義1個有n個頂點的連通圖的生成樹是1個極小連通子圖。1個帶權連通圖G可能有多棵生成樹,其中邊上的權值之和最小的生成樹稱為圖的最小生成樹。8.4.1生成樹和最小生成樹基本概念2.特點生成樹含有圖中全部頂點，但只包含構成1棵樹的n-1條邊。如果在1棵生成樹上添加1條邊，必定構成一個環(huán)：因為這條邊使得它依附的那兩個頂點之間有了第2條路徑。1個圖的最小生成樹不一定是唯一的。8.4.1生成樹和最小生成樹基本概念留意：n個頂點的無向圖，含有n-1條邊，不一定是生成樹；少于n-1條邊為非連通圖；多于n-1條邊則有回路。8.4.1生成樹和最小生成樹基本概念3.生成樹生成算法1個圖的生成樹可以采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷來產生。8.4.1生成樹和最小生成樹基本概念【思考與練習8.4】如右圖的無向圖G的頂點集合按{A,B,C,D,E,F}次序存儲，分別畫出從所有頂點出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷生成樹，并寫出相應的遍歷序列。答：8.4.2Prim算法Prim算法是選頂點法。每次在U和V-U兩個集合之間產生的割集中選最小邊，再將該邊在V-U中的頂點加入U,直到U=V或者V-U為空。8.4.2Prim算法【思考與練習8.5】如圖8.18所示的帶權無向圖及其最小生成樹，請簡明給出Prim算法求解的過程。答：Prim算法不斷擴充U，擴充次序為AGBCDEF。8.4.2Prim算法【算法8.11】從起點v出發(fā)求圖的最小生成樹的Prim算法。思路：（1）頂點v加入U。（2）在U和V-U頂點集之間的割集中，找出最小邊（v,k）并修改lowcost數(shù)組和closest數(shù)組。（3）將頂點k加入U。（4）重復（2）、（3），直到全部頂點到U或者V-U為空。代碼見算法8.118.4.3Kruskal算法Kruskal算法是選邊法。每次從所有沒被選的邊中選擇權值最小的邊，在不構成環(huán)的情況下連接頂點，直到所有頂點相連或n-1條邊選完。8.4.3Kruskal算法【思考與練習8.6】如圖8.18所示的帶權無向圖及其最小生成樹，請簡明給出Kruskal算法求解的過程。答：Kruskal算法不斷合并樹，依次選擇邊（B,G），（C,D），（A,G），（E,F），（D,E），（B,C）。8.4.3Kruskal算法【算法8.12】求圖的最小生成樹Kruskal算法。思路：（1）置U的初值等于V（即包含有G中的全部頂點），TE的初值為空集。（2）將圖G中的邊按權值從小到大的順序依次選?。喝暨x取的邊未使生成樹T形成回路，則加入TE；否則舍棄，直到TE中包含n-1條邊為止。（3）為了不形成回路，可以用vset頂點編號集來區(qū)別，不同時才能加邊。代碼見算法8.128.5最短路徑在圖中從某個始點出發(fā)到終點，可能存在多條路徑，其中最短的路徑就是最短路徑。8.5最短路徑舉例：將軍飲馬，如右圖所示，將軍從A點出發(fā)，要到前面的一條河流飲馬，再折返到B點?？梢杂脭?shù)學證明將軍在圖中C點飲馬再折返到B點，是最短的路徑。在其它點飲馬都不是最短路徑，這樣給將軍節(jié)省了很多寶貴軍事時間。8.5.1最短路徑基本概念無向不帶權圖最短路：分支數(shù)最少的路徑。如圖8.22，A-E-B有向帶權圖最短路徑：權值之和最小的路徑。如圖8.23，v0->v4->v38.5.2Dijkstra算法Dijkstra算法是求單源最短路徑算法，即求圖中某個頂點到另一個頂點的最短路徑算法。思路：8.5.2Dijkstra算法舉例：如圖8.25所示，求頂點0到頂點6的最短路徑和最短路徑長度。由最后一輪的path[]:求前驅頂點：path[6]=4，path[4]=5，path[5]=2，path[2]=1，path[1]=0。逆序路徑得：0->1->2->5->4->6即為所求最短路徑，長度為4+1+4+1+6=16。8.5.2Dijkstra算法【算法8.13】圖g中從源點v出發(fā)到其它各頂點的最短路徑的Dijkstra算法。思路：（1）初始化dist[]、path[]和S[]。（2）在dist[]中找最小值和對應的索引號（頂點號）。（3）加入u后新舊路徑比較（如圖8.24（2）），更新dist[]和path[]。（4）求最短路徑長度：遍歷最后的dist[]。（5）求最短路徑：1）反復path[]找前驅并加入到apath[]，直到源點v；2）逆向輸出apath[]。代碼見算法8.138.5.3Floyd算法Floyd算法是求多源最短路徑算法，即求圖中某個頂點到所有頂點的最短路徑算法。思路：8.5.3Floyd算法舉例：如圖8.27所示1個帶權有向圖及其鄰接矩陣，求任意2個頂點的最短距離。8.5.3Floyd算法求解過程如下面的表格：求A-1和path-18.5.3Floyd算法求A0和path0（加入頂點0）8.5.3Floyd算法求A1和path1（加入頂點1）8.5.3Floyd算法求A2和path2（加入頂點2）8.5.3Floyd算法求A3和path3（加入頂點3）由最后所求的A和path分別求最短路徑長度和最短路徑。例如，求頂點1到頂點0的最短路徑長度和最短路徑：由A3得，A3[1][0]=6。有path3得，path[1][0]=2，path[1][2]=3，path[1][3]=1（找到起點），故最短路徑為1→3→2→0。8.5.3Floyd算法【算法8.14】圖g中任意2個頂點的最短路徑的Floyd算法。思路：（1）初始化A[][]和path[][]。（2）加入頂點k之后，比較新舊路徑長度（如圖8.26（1）），更新A[][]和path[][]。（3）求最短路徑長度：遍歷最后的A[][]。（4）求最短路徑：1）反復path[][]求前驅并加到apath[]；2）逆向輸出apath[]。代碼見算法8.148.6拓撲排序概念設G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列v1、v2、…、vn稱為一個拓撲序列，當且僅當該頂點序列滿足下列條件：若<vi，vj>是圖中的有向邊或者從頂點vi到頂點vj有一條路徑，則在序列中頂點vi必須排在頂點vj之前。在一個有向圖G中找一個拓撲序列的過程稱為拓撲排序。8.6拓撲排序對有向圖的拓撲排序基本思想為：（1）從有向圖中選擇一個沒有前驅（即入度為0）的頂點并且輸出它。（2）從圖中刪去該頂點，并且刪去從該頂點發(fā)出的全部有向邊。（3）重（1）、（2），直到剩余的圖中不再存在沒有前驅的頂點為止。8.6拓撲排序2.舉例學生修學分課程的先后順序如表8.7所示。8.6拓撲排序用一個有向圖表示，可得排課方案。拓撲排序序列不一定唯一！8.6拓撲排序【思考與練習8.7】給出圖8.27有向圖的全部拓撲排序序列。答：從入度為0的頂點入手，得到所有的拓撲排序序列有：041253、041523、045123、450123、401253、405123、401523。8.6拓撲排序3.算法【算法8.15】對鄰接表存儲的有向圖G進行拓撲排序，輸出拓撲排序序列。思路：（1）將入度為0的頂點入棧st。（2）出棧并輸出該頂點i，同時刪除頂點i的所有邊（將頂點i的所有出邊鄰接點的入度減1）。（3）重復（1）、（2），直到棧為空。代碼見算法8.158.7關鍵路徑基本術語AOE網(wǎng)：若用一個帶權有向圖描述工程的預計進度，以頂點表示事件，有向邊表示活動，邊e的權c(e)表示完成活動e所需的時間（比如天數(shù)），或者說活動e持續(xù)時間。源點：AOE網(wǎng)中入度為0的頂點。匯點：AOE網(wǎng)中出度為0的頂點。關鍵路徑：在AOE網(wǎng)中，從源點到匯點的所有路徑中，具有最大路徑長度的路徑。關鍵活動：關鍵路徑上的活動，或者說關鍵路徑是由關鍵活動構成的。8.7關鍵路徑留意：完成整個工程的最短時間就是網(wǎng)中關鍵路徑的長度。只要找出AOE網(wǎng)中的全部關鍵活動，也就找到了全部關鍵路徑了。源點：A匯點：I關鍵路徑：A→B→E→F→I，A→B→E→G→I關鍵事件：ABEFGI8.7關鍵路徑2.公式事件v的最早開始時間（ee）：

ee(v)=0 當v為源點時

ee(v)=MAX{ee(x)+a，ee(y)+b，ee(z)+c} 否則事件v的最遲開始時間（le）： le(v)=ee(v) 當v為匯點時 le(v)=MIN{le(x)-a，le(y)-b，le(z)-c} 否則活動a的最早開始時間e(a)：e(a)=ee(x)活動a的最遲開始時間l(a)：l(a)=le(y)-c8.7關鍵路徑3.舉例求圖8.28的關鍵路徑。求解步驟如下：（1）求出1個拓撲排序序列：ABCDEFGHI。（2）計算各事件的ee(v)：ee(A)=0ee(B)=ee(A)+c(a1)=6ee(C)=ee(A)+c(a2)=4ee(D)=ee(A)+c(a3)=5ee(E)=MAX(ee(B)+c(a4)，ee(C)+c(a5)}=MAX{7，5}=7ee(F)=ee(E)+c(a7)=16ee(G)=ee(E)+c(a8)=14ee(H)=ee(D)+c(a6)=7ee(I)=MAX{ee(F)+c(a10)，ee(G)+c(a11)，ee(H)+c(a9)}=MAX(18，18，11}=18（3）按拓撲逆序IHGFEDCBA計算各事件的le(v)：le(I)=ee(I)=18le(H)=le(I)-c(a9)=14le(G)=le(I)-c(a11)=14le(F)=le(I)-c(a10)=16le(E)=MIN(le(F)-c(a7)，le(G)-c(a8)}={7，7}=7le(D)=le(H)-c(a6)=12le(C)=le(E)-c(a5)=6le(B)=le(E)-c(a4)=6le(A)=MIN(le(B)-c(a1)，le(C)-c(a2)，le(D)-c(a3)}={0，2，7}=0（4）計算各活動的e(a)、l(a)和d(a)：活動a1：e(a1)=ee(A)=0， l(a1)=le(B)-6=0，d(a1)=0 活動a2：e(a2)=ee(A)=0， l(a2)=le(C)-4=2，d(a2)=2 活動a3：e(a3)=ee(A)=0， l(a3)=le(D)-5=7，d(a3)=7活動a4：e(a4)=ee(B)=6， l(a4)=le(E)-1=6，d(a4)=0 活動a5：e(a5)=ee(C)=4， l(a5)=le(E)-1=6，d(a5)=2 活動a6：e(a6)=ee(D)=5， l(a6)=le(H)-2=12，d(a6)=7活動a7：e(a7)=ee(E)=7， l(a7)=le(F)-9=7，d(a7)=0 活動a8：e(a8)=ee(E)=7， l(a8)=le(G)-7=7，d(a8)=0 活動a9：e(a9)=ee(H)=7， l(a9)=le(I)-4=14，d(a9)=7活動a10：e(a10)=ee(F)=16，l(a10)=le(I)-2=16，d(a10)=0 活動a11：e(a11)=ee(G)=14， l(a11)=le(I)-4=14，d(a11)=0（4）求出關鍵路徑：關鍵活動有a11、a10、a8、a7、a4、a1，因此關鍵路徑有兩條：A－B－E－F－I和A－B－E－G－I。8.7關鍵路徑4.算法【算法8.16】求鄰接表存儲的AOE網(wǎng)中關鍵路徑的算法。思路：（1）將AOE網(wǎng)拓撲排序，產生拓撲排序序列。（2）按照該序列正序求出頂點的最早開始時間，存入數(shù)組ve；按照該序列逆序求出頂點的最遲開始時間，存入數(shù)組vl。（3）若ve[i]與vl[p.adjvex]-p.weight相等，則該邊為關鍵活動。（4）求出所有關鍵活動構造所有關鍵路徑。代碼見算法8.168.8圖應用【例8.1】圖G