數(shù)據(jù)結構課件-圖

圖圖的定義圖（graph）是一種網(wǎng)狀數(shù)據(jù)結構，圖是由非空的頂點集合和一個描述頂點之間關系的集合組成。其形式化的定義如下： Graph=(V,E) V={x|x∈某個數(shù)據(jù)對象}

E={<u,v>|P(u,v)∧(u,v∈V)} V是具有相同特性的數(shù)據(jù)元素的集合，V中的數(shù)據(jù)元素通常稱為頂點（Vertex）。

E是兩個頂點之間關系的集合。 P(u,v)表示u和v之間有特定的關聯(lián)屬性。2024/9/292圖的基本術語若<u,v>∈E，則<u,v>表示從頂點u到頂點v的一條弧，并稱u為弧尾或起始點，稱v為弧頭或終止點，此時圖中的頂點之間的連線是有方向的，這樣的圖稱為有向圖（directedgraph）。若<u,v>∈E則必有<v,u>∈E，即關系E是對稱的，此時可以使用一個無序?qū)?u,v)來代替兩個有序?qū)?，它表示頂點u和頂點v之間的一條邊，此時圖中頂點之間的連線是沒有方向的，這種圖稱為無向圖（undirectedgraph）。2024/9/293圖的示例2024/9/294圖的基本術語簡單圖圖中所有的邊自然構成一個集合，并且每條邊的兩個頂點均不相同。2024/9/295圖的基本術語鄰接點對于無向圖G=(V,E)，如果邊(u,v)∈E，則稱頂點u與頂點v互為鄰接點。邊(u,v)依附于頂點u和v，或者說邊(u,v)與頂點u和v相關聯(lián)。對于有向圖G=(V,E)，如果邊<u,v>∈E，則稱頂點u鄰接到頂點v，頂點v鄰接自頂點u，或稱v為u的鄰接點，u為v的逆鄰接點。同樣我們稱邊<u,v>與頂點u和v相關聯(lián)。從頂點u出發(fā)的邊也稱為u的出邊或鄰接邊，而指向頂點u的邊也稱為u的入邊或逆鄰接邊。2024/9/296圖的基本術語頂點的度、入度、出度頂點的度（degree）是指依附于某頂點v的邊數(shù)，通常記為TD(v)。在有向圖中，頂點v的入度（indegree）是指以頂點為終點的邊的數(shù)目，記為ID(v)；頂點v出度（outdegree）是指以頂點v為起始點的邊的數(shù)目，記為OD(v)。對于有向圖有TD(v)=ID(v)＋OD(v)。在無向圖中每條邊都可以看成出邊，也可以看成入邊，此時TD(v)=ID(v)=OD(v)。觀察結論7.1：在任何圖G=(V,E)中，|E|=(ΣTD(vi))/22024/9/297圖的基本術語完全圖、稠密圖、稀疏圖觀察結論7.2假設在圖G=(V,E)中有n個頂點和m條邊。1）若G是無向圖，則有0≤m≤n(n-1)/2。2）若G是有向圖，則有0≤m≤n(n-1)。有n(n-1)/2條邊的無向圖稱為無向完全圖；

有n(n-1)條邊的有向圖稱為有向完全圖。有很少邊（如m<nlogn）的圖稱為稀疏圖；

反之邊較多的圖稱為稠密圖。2024/9/298圖的基本術語子圖設圖G=(V,E)和圖G‘=(V’,E‘)。如果V’?V且E’?E，則稱G’是G的一個子圖（subgraph）。如果V‘=V且E’?E，則稱G‘是G的一個生成子圖（spanningsubgraph）。2024/9/299子圖2024/9/2910圖的基本術語路徑、環(huán)路及可達分量圖中的一條通路或路徑（path），就是由m+1個頂點與m條邊交替構成的一個序列ρ={v0,e1,v1,e2,v2,…,em,vm}，m≥0，且ei=(vi-1,vi)，1≤i≤m。路徑上邊的數(shù)目稱為路徑長度，計作|ρ|。長度|ρ|≥1的路徑，若路徑的第一個頂點與最后一個頂點相同，則稱之為環(huán)路或環(huán)(cycle)。2024/9/2911圖的基本術語路徑、環(huán)路及可達分量如果組成路徑ρ的所有頂點各不相同，則稱之為簡單路徑（simplepath）；如果在組成環(huán)的所有頂點中，除首尾頂點外均各不相同，則稱該環(huán)為簡單環(huán)路（simplecycle）。如果組成路徑ρ的所有邊都是有向邊，且ei均是從vi-1指向vi，1≤i≤m，則稱ρ為有向路徑；同樣可以定義有向環(huán)路。2024/9/2912圖的基本術語路徑、環(huán)路及可達分量在有向圖G中，若從頂點s到頂點v有一條通路，則稱v是從s可達的。對于頂點s，從s可達的所有頂點所組成的集合，稱作s在G中對應的可達分量。2024/9/2913圖的基本術語連通性與連通分量在無向圖中，如果從一個頂點vi到另一個頂點vj(i≠j)有路徑，則稱頂點vi和vj是連通的。如果圖中任意兩頂點vi、vj∈V，vi和vj都是連通的，則稱該圖是連通圖（connectedgraph）。連通分量（connectedcomponent），是指無向圖的極大連通子圖。在有向圖中，若圖中任意一對頂點vi和vj(i≠j)均有一條從頂點vi到另一個頂點vj的路徑，也有從vj到vii的路徑，則稱該有向圖是強連通圖。有向圖的極大強連通子圖稱為強連通分量。2024/9/2914強連通圖和強連通分量2024/9/2915圖的基本術語無向圖的生成樹對于無向圖G=(V,E)。如果G是連通圖，則G的生成樹（spanningtree），是G的一個極小連通生成子圖。2024/9/2916圖的基本術語權與網(wǎng)圖的邊往往與具有一定實際意義的數(shù)有關，即每條邊都有與它相關的實數(shù)，稱為權。邊上具有權值的圖稱為帶權圖（weightedgraph）或網(wǎng)（network）。2024/9/2917抽象數(shù)據(jù)類型2024/9/2918圖的抽象數(shù)據(jù)類型定義2024/9/2919圖的抽象數(shù)據(jù)類型定義2024/9/2920圖的抽象數(shù)據(jù)類型定義2024/9/2921圖的抽象數(shù)據(jù)類型定義2024/9/2922圖的Java接口2024/9/2923圖的Java接口2024/9/2924圖的Java接口2024/9/2925UnsupportedOperation異常2024/9/2926圖的存儲方法2024/9/2927鄰接矩陣圖的鄰接矩陣（adjacentmatrix）表示法是使用數(shù)組來存儲圖結構的方法，也被稱為數(shù)組表示法。假設圖G＝(V,E)有n個頂點，即V＝{v0,v1,…,vn-1}，則表示G中各頂點關聯(lián)關系的為一個n×n的矩陣A，矩陣的元素為：2024/9/2928鄰接矩陣2024/9/2929帶權圖的鄰接矩陣若G是一個有n個頂點的帶權圖，則它的鄰接矩陣是具有如下性質(zhì)的n×n的矩陣A：2024/9/2930帶權圖的鄰接矩陣2024/9/2931鄰接表鄰接表（adjacencylist）是圖的一種鏈式存儲方法，鄰接表表示法類似于樹的孩子鏈表表示法。在鄰接表中對于圖G中的每個頂點vi建立一個單鏈表，將所有鄰接于vi的頂點vj鏈成一個單鏈表，并在表頭附設一個表頭結點，這個單鏈表就稱為頂點vi的鄰接表。2024/9/2932鄰接表結點結構2024/9/2933鄰接表2024/9/2934鄰接表2024/9/2935雙鏈式存儲結構2024/9/2936頂點與邊的結構雙鏈式存儲結構的頂點定義2024/9/29382024/9/29392024/9/29402024/9/29412024/9/29422024/9/2943Vertex類中方法的功能2024/9/2944雙鏈式存儲結構的邊定義2024/9/29452024/9/2946472024/9/2948Edge類中方法的功能49圖ADT實現(xiàn)設計2024/9/2950圖ADT的實現(xiàn)首先，確定無向圖與有向圖都支持的操作中實現(xiàn)算法相同的操作，將這些操作的實現(xiàn)放在一個抽象類AbstractGraph

中；其次，將兩類圖都支持但是實現(xiàn)算法不同的操作放在兩個不同的類DirectGraph

和UndirectedGraph

中分別實現(xiàn)，當然DirectGraph

和UndirectedGraph

類都繼承自AbstractGraph

抽象類；最后，在DirectGraph類中實現(xiàn)只有有向圖才支持的操作，在UndirectedGraph

類中實現(xiàn)只有無向圖才支持的操作。2024/9/2951圖ADT實現(xiàn)結構2024/9/2952AbstractGraph抽象類實現(xiàn)的方法2024/9/2953DirectGraph和UndirectedGraph分別實現(xiàn)的方法2024/9/2954圖的遍歷2024/9/2955圖的遍歷圖的遍歷就是從圖中某個頂點出發(fā)，按某種方法對圖中所有頂點訪問且僅訪問一次。兩種方法：深度優(yōu)先搜索廣度優(yōu)先搜索2024/9/2956深度優(yōu)先搜索深度優(yōu)先搜索（depthfirstsearch）從圖中某個頂點發(fā)v出發(fā)，訪問此頂點，然后依次從v的未被訪問的鄰接點出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。2024/9/2957深度優(yōu)先搜索2024/9/2958DFSTraverse2024/9/29592024/9/2960非遞歸實現(xiàn)DFS首先將初始頂點v入棧；當堆棧不為空時，重復以下處理棧頂元素出棧，若未訪問，則訪問之并設置訪問標志，將其未曾訪問的鄰接點入棧；如果圖中還有未曾訪問的鄰接點，選擇一個重復以上過程。2024/9/2961DFS62廣度優(yōu)先搜索廣度優(yōu)先搜索（breadthfirstsearch）假設從圖中某頂點v出發(fā)，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，然后分別從這些鄰接點出發(fā)依次訪問它們的鄰接點，并使“先被訪問的頂點的鄰接點”先于“后被訪問的頂點的鄰接點”先被訪問，直至圖中所有已被訪問的頂點的鄰接點都被訪問到。若此時圖中尚有頂點未被訪問，則另選圖中一個未曾被訪問的頂點作起始點，重復上述過程，直至圖中所有頂點都被訪問到為止。2024/9/29632024/9/2964算法思想首先訪問初始頂點v并入隊；當隊列不為空時，重復以下處理隊首元素出隊，訪問其所有未曾訪問的鄰接點，并它們?nèi)腙?；如果圖中還有未曾訪問的鄰接點，選擇一個重復以上過程。2024/9/2965BFSTraverse2024/9/29662024/9/2967圖的連通性2024/9/2968無向圖的連通分量2024/9/2969無向圖的生成樹設E是連通圖G中所有邊的集合，則從圖中任意一個頂點出發(fā)遍歷圖時，必定將E分成兩個子集：Et和Eb，其中Et是遍歷圖過程中經(jīng)歷的邊的集合；Eb是剩余邊的集合。顯然Et和圖中所有頂點一起構成連通圖G的極小連通子圖，即圖G的生成樹。并且由深度優(yōu)先搜索得到的為深度優(yōu)先搜索生成樹；由廣度優(yōu)先搜索得到的為廣度優(yōu)先搜索生成樹。2024/9/2970無向圖的生成樹2024/9/2971非連通圖的生成森林2024/9/2972有向圖的強連通分量從有向圖中某個頂點s出發(fā)進行深度優(yōu)先搜索或廣度優(yōu)先搜索，只能得到頂點s的可達分量，不一定能夠得到包含s在內(nèi)的強連通分量。2024/9/2973有向圖的強連通分量對于任何有向邊e=<u,v>，稱R(e)=<v,u>為e的鏡像邊，即R(e)的起點（終點）就是e的終點（起點）。對于任何有向圖G=(V,E)，我們稱R(E)={R(e)|e∈E}為E的鏡像邊集。此時，也稱R(G)=(V,R(E))為G的鏡像圖。構造有向圖的強連通分量的方法：求出頂點s在圖G中的可達分量與頂點s在R(G)中的可達分量的交集；在有向圖中求頂點s的可達分量，只需要從s出發(fā)進行深度優(yōu)先搜索或廣度優(yōu)先搜索即可。2024/9/2974有向圖的強連通分量2024/9/2975最小生成樹一個連通網(wǎng)的代價最小的生成樹稱為圖的最小生成樹（minimumspanningtree）。盡管最小生成樹必然存在，但不一定唯一。2024/9/2976構造最小生成樹每步形成最小生成樹的一條邊；算法設置了邊集合A，初始時為空，該集合一直是某最小生成樹的子集。在每步?jīng)Q定是否把邊(u,v)添加到集合A中，其添加條件是A∪{(u,v)}仍然是最小生成樹的子集。稱這樣的邊為A的安全邊。通過上述過程找到|V|-1條邊最后返回集合A時，A就必然是一棵最小生成樹。2024/9/2977基本概念無向圖G=(V,E)的一個割(S,V-S)是對頂點集的一個劃分。當邊(u,v)∈E的一個頂點在S中，而另外一個頂點在V-S中，我們說邊(u,v)橫切割(S,V-S)。在橫切割的所有邊中，權最小的邊稱為輕邊。若集合A中沒有邊橫切割，則我們說割不妨害邊的集合A。2024/9/2978割及輕邊的概念2024/9/2979確認安全邊定理7.1設圖G=(V,E)是一個無向連通圖，且在E上定義了相應的加權函數(shù)w，設A是E的一個子集且包含于G的某個最小生成樹中，割(S,V-S)是G的不妨害A的任意割且邊(u,v)是橫切割(S,V-S)的一條輕邊，則邊(u,v)對集合A是安全的。2024/9/2980Prim算法假設G=(V,E)是連通網(wǎng)，A是G上最小生成樹的邊的集合。算法從S={u0}（u0∈V），A={}開始，重復執(zhí)行下述操作：找到橫切割(S,V-S)的輕邊(u0,v0)并入集合A，同時v0并入S，直到S=V為止。此時A中必定有|V|-1條邊，則T=(V,A)為G的最小生成樹。2024/9/2981Prim算法示例2024/9/29822024/9/2983算法實現(xiàn)策略首先，以頂點的成員變量visited來表示該頂點是否屬于S，visited=true表示屬于S，否則不屬于S。其次，到達V-S中各個頂點的最短橫切邊通過該頂點的成員變量application來表示，此時application指向的是Edge類的對象，它是從S到達本頂點橫切邊中權值最小的一條。最后，最小生成樹的表示采用設置圖中邊的類型來完成，即如果是最小生成樹的邊，將邊的類型設置為Edge.MST。2024/9/2984求MST時，對v.application的操作2024/9/2985generateMST2024/9/29862024/9/29872024/9/2988Kruskal算法假設G=(V,E)是連通網(wǎng)，則令最小生成樹的初始狀態(tài)為只有|V|個頂點而無邊的非連通圖，圖中每個頂點自成一個連通分量。在E中選擇權值最小的邊，若該邊依附的頂點落在T中的不同連通分量上，則將此邊加入T，否則舍去此邊選擇下一條代價最小的邊。以此類推，直到所有頂點都在同一連通分量上為止。2024/9/2989Kruskal算法示例2024/9/29902024/9/2991最短距離

2024/9/2992最短距離在圖中兩點之間的最短路徑問題包括兩個方面：一是求圖中一個頂點到其他頂點的最短路徑；二是求圖中每對頂點之間的最短路徑。2024/9/2993單源最短路徑在帶權圖G=(V,E)中，已知源點為s∈V，求s到其余各頂點的最短路徑。在圖中若頂點v是從源點s可達的，那么從s到頂點v的最短路徑必然存在，其長度稱為“從s到v的最短距離”，記作δ(s,v)。如果頂點v從s不可達，則可以認為從s到v的距離為∞。兩點之間的最短路徑可能不是唯一的。2024/9/2994最短路徑的基本性質(zhì)定理7.2若π=(u0=s,u1,u2,…,uk=v)是從頂點s到頂點v的最短路徑，則對于任何0≤i<j≤k，τ=(ui,ui+1,…,uj)是從頂點ui到uj的最短路徑。2024/9/2995Dijkstra算法將帶權圖G=(V,E)的頂點分為兩個集合：S、V-S，其中頂點集S是已求出的最短路徑的終點集合（初始時S={s}）。頂點集V-S是尚未求出最短路徑的終點的集合。算法將按最短路徑長度遞增的順序逐個將V-S中的頂點加入到S中，直到所有頂點都被加入到S中為止。2024/9/2996為每個頂點v定義了一個變量distance，該變量記錄了從s出發(fā)，經(jīng)由S中的頂點到達v的當前最短距離。長度最短的一條最短路徑必為π=(s,uk)，其中uk滿足： distance(uk)=min{distance(ui)|ui∈V-S}將uk并入S，即S=S∪{uk}。每當一個新的頂點uk加入S之后，要以uk為“中轉(zhuǎn)”頂點對V-S中各個頂點的當前最短路徑distance進行修正。2024/9/2997修正當前最短路徑依次對頂點uk的鄰接點ui（ui∈V-S）執(zhí)行如下操作：

distance(ui)=min{distance(ui),distance(uk)+w(uk,ui)}，ui∈V-S

其中distance(ui)是ui當前最短距離，distance(uk)+w(uk,ui)是經(jīng)過uk

“中轉(zhuǎn)”的路徑長度，修正之后ui的當前最短路徑長度是兩者中小的。2024/9/2998Dijkstra算法①初始化： S={s}；distance(s)=0； distance(ui)=w(s,ui)或∞，（ui∈V-S）；②選擇distance(uk)=min{distance(ui)|ui∈V-S}，uk為下一條最短路徑的終點；③S=S∪{uk}④以uk為“中轉(zhuǎn)”，修正V-S中各個頂點distance：

distance(ui)=min{distance(ui),distance(uk)+w(uk,ui)}，ui∈V-S⑤重復②—④步|V|-1次。2024/9/29992024/9/29100對v.application的操作2024/9/29101Path類定義2024/9/291021032024/9/29104Dijkstra算法的具體實現(xiàn)shortestPath2024/9/291052024/9/291062024/9/291072024/9/29108任意頂點間的最短路徑定義：D(k)（0≤k≤|V|）是一個|V|階方陣，其中D(k)[i][j]是在考慮帶權圖中前k個頂點，將它們作為中間頂點時從頂點vi到頂點vj的當前最短距離（1≤i≤|V|，1≤j≤|V|）。2024/9/29109Floyd算法基本思想：(1)用鄰接矩陣初始化D(0)，對角線元素為0；(2)在頂點vi、vj之間考慮頂點vl比較在引入vl之后vi到vjj的當前最短距離是否可以通過vl變得更小。把vl放在vi到vj的路徑上，vi到vj之間可能會產(chǎn)生新的路徑，其距離為D(0)[i][1]+D(0)[1][j]，當然vl的引入可能反而會加大vi到vj的距離，因此需要比較D(0)[i][1]+D(0)[1][j]與D(0)[i][j]的大小。最終，在考慮vl之后vi到vj的當前最短距離為兩者中小的。即 D(1)[i][j]=min{D(0)[i][1]+D(0)[1][j],D(0)[i][j]}2024/9/29110Floyd算法基本思想：(3)一般情況下，如果在考慮了前k-1個頂點{v1,v2,…,vk-1}之后，從頂點vi到vj的當前最短距離是D(k-1)[i][j]。那么在頂點vi、vj之間考慮前k個頂點時，頂點vi到vj的當前最短距離為以下兩個距離中小的：在考慮前k-1個頂點基礎上將vk放在vi到vj的路徑上，此時產(chǎn)生新的路徑長度為D(k-1)[i][k]+D(k-1)[k][j]；以及不將vk放在vi到vj的路徑上的距離D(k-1)[i][j]。最終，在考慮前k個頂點{v1,v2,…,vk}之后，vi到vj的當前最短距離D(k)[i][j]=min{D(k-1)[i][k]+D(k-1)[k][j],D(k-1)[i][j]}1≤k≤|V|(4)依次進行下去，直到k=|V|。此時D(|V|)[i][j]即為帶權圖中任意兩個頂點vi到vj的最短距離。2024/9/29111Floyd算法執(zhí)行過程2024/9/29112有向無環(huán)圖及其應用2024/9/29113有向無環(huán)圖有向無環(huán)圖（directedacyclicgraph）是指一個無環(huán)的有向圖，簡稱DAG。2024/9/29114拓撲排序如果在一個有向圖G=<V,E>中用頂點表示活動，用有向邊<vi,vj>表示活動vi必須先于活動vj進行。這種有向圖叫做頂點表示活動的AOV網(wǎng)絡（activityonverticesnetworks）。2024/9/29115AOV網(wǎng)及拓撲序列a.購買原材料；b.生產(chǎn)零件1；c.用零件1加工零件2；d.生產(chǎn)零件3；e.組裝零件2、3得到成品。2024/9/29116拓撲排序由某個集合上的一個偏序得到該集合上的一個全序，此操作稱之為拓撲排序（topologicalsort）。⑴在AOV網(wǎng)絡中選一個沒有直接前驅(qū)的頂點，并輸出之；⑵從圖中刪去該頂點，同時刪去所有它發(fā)出的有向邊；⑶重復以上⑴、⑵步,直到全部頂點均已輸出，或圖中不存在無前驅(qū)的頂點。2024/9/29117拓撲排序的過程2024/9/29118拓撲排序的實現(xiàn)首先，為每個頂點v設置一個變量，記錄其在拓撲排序過程中的入度，入度為0的頂點就是沒有直接前驅(qū)的頂點。其次，刪除一條有向邊可以用有向邊終止點的入度減1來實現(xiàn)。2024/9/29119構造AOV網(wǎng)絡的拓撲序列⑴建立入度為零的頂點棧；⑵當入度為零的頂點棧不空時，重復執(zhí)行從頂點棧中退出一個頂點，并輸出之；搜索以這個頂點發(fā)出的邊，將邊的終頂點入度減1；

如果邊的終頂點入度減至0，則該頂點進入棧；⑶如果輸出頂點個數(shù)少于AOV網(wǎng)絡的頂點個數(shù)，說明網(wǎng)絡中存在有向環(huán)。2024/9/29120對v.application的操作2024/9/29121toplogicalSort2024/9/291222024/9/29123關鍵路徑如果在有向無環(huán)的帶權圖中：用有向邊表示一個工程中的各項活動(activity)；用邊上的權值表示活動的持續(xù)時間(duration)；用頂點表示事件(event)；

則這樣的有向圖叫做用邊表示活動的網(wǎng)絡，簡稱AOE(activityonedges)網(wǎng)絡。2024/9/29124AOE網(wǎng)假設活動a需時3天、活動b需時1天、活動c需時2天、活動d需時5天、活動e需時2天。 a.購買原材料； b.生產(chǎn)零件1； c.用零件1加工零件2； d.生產(chǎn)零件3； e.組裝零件2、3得到成品。2024/9/29125AOE網(wǎng)在正常情況下，AOE網(wǎng)絡中只有一個入度為0的頂點，也只有一個出度為0的頂點，它們分別稱之為源點和匯點。完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關鍵路徑（criticalpath）。2024/9/29126變量定義在圖G={V,E}中，假設V={v0,v1,…,vn-1}，其中n=|V|，v0是源點，vn-1是匯點。為求關鍵活動，定義以下變量：事件vi的最早可能開始時間Ve[i]：是從源點v0到頂點vi的最長路徑長度?；顒觓k的最早可能開始時間e[k]：設活動ak在邊<vi,vj>上，則e[k]是從源點v0到頂點vi的最長路徑