目錄圖的基本概念圖的存儲和遍歷鄰接矩陣鄰接表圖的遍歷構造最小生成樹Kruskal算法Prim算法最短路徑問題單源最短路徑Dijkstra算法Bellman-Ford算法多源最短路徑Floyd-Warshall算法參考代碼圖的基本概念圖是由頂點集合及頂點間的關系邊組成的一種數(shù)據(jù)結構用G (V E)表示。其中V是頂點的集合頂點的個數(shù)不能為0E是頂點間關系的集合也就是邊的集合它的個數(shù)可以為0。簡單來說圖就是由有限個頂點和有限條邊組成的。圖中第i個頂點記作vii是下標編號沒有要求可以自行給頂點和邊編號。圖中第k條邊記作ekk是下標。邊有雙向和單向之分ekvi,vj表示ek是頂點vi到頂點vj的一條有向邊類似單行道在這條邊上只能從vi走到vj如果是ekvi,vj則表示ek是頂點vi和頂點vj的一條無向邊沒有特定的方向其實就是雙向的邊。其中vi,vj和vi,vj也叫頂點對分為有序和無序vi,vj是有序的也就是有向的所以vi,vj和vj,vi不同無序的頂點對vivj則和vj,vi相同。一個圖中只能有一種邊要么都是無向邊要么都是有向邊。如下左邊的圖只有有向邊叫做有向圖右邊的圖則是只有無向邊的無向圖。如果圖中所有能存在的邊都已經(jīng)存在再畫一條邊就必定會跟其中一條邊重復的圖就是完全圖。有向的叫有向完全圖下圖左邊如果有n個頂點就有有n*(n-1)條邊無向的叫無向完全圖(下圖右邊)n個頂點有 n*(n-1)/2條邊。在無向圖中GVE中若(vi, vj)是E中的一條邊則稱 vi 和 vj 互為鄰接頂點并稱邊(vi,vj)依附于頂點 vi 和 vj在有向圖G中若vi, vj是E中的一條邊則稱頂點vi鄰接到vj頂點vj鄰接自頂點vi并稱邊vi, vj與頂點vi和頂點vj相關聯(lián)。頂點v的度是指與它相關聯(lián)的邊的條數(shù)。在有向圖中頂點的度等于該頂點的入度與出度之和其中頂點v的入度是以v為終點的有向邊的條數(shù)頂點v的出度是以v為起始點的有向邊的條數(shù)。對于無向圖頂點的度與該頂點的入度和出度都相等這是因為無向圖的邊可以看作雙向的邊每有一條無向邊依附于v就會同時增加一個入度和一個出度。若從頂點vi出發(fā)有一組邊使其可到達頂點vj則稱頂點 vi 到頂點 vj 的頂點序列為從頂點 vi 到頂點 vj 的路徑雙向的路徑記作vi,vj,單向的記作 Path(vi,vj)。權值W是邊附帶的數(shù)據(jù)信息對于不帶權的圖一條路徑的路徑長度是指該路徑上的邊的條數(shù)對于帶權的圖如下一條路徑的路徑長度是指該路徑上各個邊權值的總和。若路徑上各頂點v1v2v3…vm均不重復則稱這樣的路徑為簡單路徑。若路徑上第一個頂點v1和最后一個頂點vm重合則稱這樣的路徑為回路或環(huán)。若圖G1由圖G中的部分頂點和邊構成則稱G1是G的子圖。在無向圖中若從頂點v1到頂點v2有路徑則稱頂點v1與頂點v2是連通的。如果圖中任意一對頂點都是連通的則稱此圖為連通圖。在有向圖中若在每一對頂點 vi 和 vj 之間都存在一條從 vi 到 vj 的路徑也存在一條從 vj 到 vi 的路徑則稱此有向圖是強連通圖。一個無向連通圖的最小連通子圖稱作該無向圖的生成樹也就是用圖中最少的邊將所有的頂點連接起來有n個頂點的連通圖的生成樹有n個頂點和n- 1條邊如果還能滿足邊的權值之和也是最小的那就是最小生成樹。最小生成樹有可能是不唯一的。圖的存儲和遍歷存儲的核心就是留下圖的所有信息。圖只有頂點和邊二叉樹也是圖的一種但圖的結構不一定像二叉樹那樣規(guī)則所以要將頂點和邊分開存儲。頂點沒什么好說的一個數(shù)組就行主要是邊怎么表示和存儲。這里有兩種辦法一種是鄰接矩陣一種是鄰接表。鄰接矩陣用一個二維數(shù)組edge存儲edge[ i ][ j ] 表示連接頂點 i 和 j 的邊的權值在有向圖中特指從頂點 i 出發(fā)到 j 的邊的權值如果權值為無窮大就表示沒有這條邊。其次將頂點到頂點自身看作權值為0的邊即edge[ i ][ i ]0。我們可以發(fā)現(xiàn)在有向圖的鄰接矩陣中第 i 行元素之和就是頂點 i 的出度第 i 列元素之和是頂點 i 的入度。而在無向圖中第 i 行元素之和與第 i 列元素之和都等于頂點 i 的度。其次用鄰接矩陣存儲圖的優(yōu)點是能夠快速知道兩個頂點是否連通缺陷是如果頂點比較多邊比較少時矩陣中存儲了大量的0成為系數(shù)矩陣比較浪費空間并且兩個頂點之間的路徑不是很好求。鄰接表用一個數(shù)組link存儲鏈表只存指向鏈表的第一個節(jié)點的指針將無向邊視為一條雙向的邊如果鏈表link[ i ]中存儲的是所有從頂點 i 出發(fā)的邊就叫出邊表鏈表節(jié)點中除了指針和邊的權值之外還會存儲邊指向的頂點的編號鏈表中所含結點的個數(shù)就是該頂點的出度也稱出度表。如果存儲的是所有到達頂點 i 的邊則是入邊表鏈表節(jié)點中存儲邊出發(fā)的頂點的編號。兩種表都會存儲圖中全部的邊一般只需實現(xiàn)出邊表。也可以用二維數(shù)組存儲邊用鏈表是為了方便刪除邊。無向圖中同一條邊在鄰接表中出現(xiàn)了兩次。頂點vi的度等于頂點vi邊鏈表集合中結點的數(shù)目。有向圖中每條邊在鄰接表中只出現(xiàn)一次如果要在出邊表中得到頂點 i 的入度必須檢測其他所有頂點對應的邊鏈表看有多少邊的終點是 i 入邊表也是類似。圖的遍歷圖的遍歷一樣是廣度優(yōu)先BFS和深度優(yōu)先DFS兩種核心都是從一個頂點出發(fā)通過鄰接矩陣或鄰接表找到頂點進行遍歷并在一個bool數(shù)組中標記已經(jīng)遍歷過的頂點防止重復遍歷。都比較簡單不詳細展開不過要注意有些圖并不能從一個頂點出發(fā)就遍歷整個圖如不連通的無向圖或者弱連通的有向圖等可以通過bool數(shù)組找到?jīng)]有遍歷的頂點然后繼續(xù)遍歷。具體可以參考文末的代碼中的BFS函數(shù)和DFS函數(shù)。構造最小生成樹構造最小生成樹有兩種常見的算法一個是Kruskal算法另一個是Prim算法。在文末的代碼中也有實現(xiàn)分別是Kruskal函數(shù)和Prim函數(shù)。Kruskal算法Kruskal算法的核心是在圖的全部邊中不斷選出權值最小的邊同時要檢查是否構成環(huán)直到選出n-1條邊將n個頂點連接起來。在實現(xiàn)時先將頂點全部復制一份給生成樹因為頂點肯定都一樣再將所有邊都放入小根堆中依次選出最小的邊用并查集算法檢查邊連接的兩個頂點是否構成環(huán)如果連接的兩個頂點在并查集中屬于同一組團體就會構成環(huán)。不了解并查集的話可以看我之前發(fā)布的博客進階數(shù)據(jù)結構并查集_并查集進階-CSDN博客 或網(wǎng)上搜索這個算法并不復雜。Prim算法Prim算法的核心是從一個頂點出發(fā)在與頂點連接的所有邊中選權值最小的那個邊這樣就連接了兩個頂點然后在這兩個頂點連接的所有邊中選權值最小的邊接著是在三個頂點連接的邊中選再接著就是四個、五個、六個以此類推。以下是示意圖只畫了關鍵部分。為了方便講述我將這些在圖結構中與子圖相連但不屬于子圖的邊統(tǒng)稱為子圖附近的邊。Prim的實現(xiàn)同樣先把頂點都復制一份接著先把第一個頂點連接的所有邊加入小根堆然后不斷從小根堆中取出權值最小的邊添加到生成樹中同時把其連接的新頂點的所有邊加入小根堆。由于頂點是一個一個連起來的只需要用bool數(shù)組記錄哪個頂點在最小生成樹中沒有連接從小根堆中取邊的時候判斷一下如果這條邊連接的另一個頂點在生成樹中沒有被連接就不會出現(xiàn)環(huán)不需要使用并查集。其次是將重復的邊加入到小根堆中的問題重復的邊雖然在判斷環(huán)的時候會被篩掉不會對結果產生影響但也會影響一點效率處理也比較簡單小根堆中以及已經(jīng)添加到生成樹中的邊都是舊頂點子圖中的頂點連接的邊我們向小根堆加入的邊都是新頂點子圖以外的頂點連接的邊如果出現(xiàn)邊重復那就說明新頂點連接到了舊頂點而前面提到的bool數(shù)組就記錄了頂點是否被連接也就是頂點是否為子圖中的舊頂點將邊添加到小根堆之前用bool數(shù)組判斷新頂點連接的是否為舊頂點即可。最短路徑問題顧名思義在帶權有向圖中從某一頂點出發(fā)找到通往另一頂點的路徑如果滿足路徑上的權值之和最小就是最短路徑。無向圖也可以找最短路徑把邊看成雙向的即可。如何通過給定的一個頂點出發(fā)找出到其它所有頂點的最短路徑的問題就是單源最短路徑問題。如果要找的是任意兩個頂點之間的最短路徑就是多源最短路徑問題。單源最短路徑Dijkstra算法Dijkstra算法的前提條件是不能有權值為負數(shù)的邊否則找的可能不是最短路徑其核心是從一個頂點出發(fā)將圖分為兩部分一個是每個點都已經(jīng)找到最短路徑的子圖S也就是說S是由各個最短路徑組成的子圖另一個則是頂點還未找到最短路徑的部分Q。如果Q中的頂點u存在最短路徑肯定是由S中的某個頂點出發(fā)得到的這是因為權值不為負在一條最短路徑上起點到沿途每個頂點的路徑一定是最短路徑。由此可以得出兩點第一我們只需在S附近的邊中找到滿足最短路徑的邊也就是這條邊是其到達的頂點的最短路徑的一部分將其連接的Q組的頂點加入S不斷擴展S的范圍直到延伸至整張圖就確定了所有頂點的最短路徑。第二我們可以通過數(shù)組dist記錄每一個頂點在各自最短路徑中的前一個頂點下面簡稱前一個頂點是誰dist[ i ]是 i 頂點的前一個頂點通過不斷回溯就能找到起點由此可以確定最短路徑比如起點a到d的最短路徑是a-b-c-dd的前一個頂點就是c。我們要看d的最短路徑就通過數(shù)組找到了c現(xiàn)在只需要知道c的最短路徑所以又通過數(shù)組找到了b于是又變成了要看b的最短路徑一直找到起點a就得到了最短路徑。那么如何在S附近找到這條滿足最短路徑的邊呢和prim算法有些相似。首先一開始S中只有一個作為起點的頂點從它出發(fā)的邊中最短的那條肯定滿足最短路徑我們將其出發(fā)的邊都放入小根堆找到那條最短的邊將其連接的頂點暫時命名為u加入S。接著將從u出發(fā)的邊都放入小根堆。但這時堆中最短的邊就不一定滿足最短路徑了如下S附近最短的邊為60但藍色頂點的最短路徑應該是從頂點出發(fā)的100。為此在開始找最短路徑前我們先將起點到所有頂點的路徑權值之和下稱路程值都看作無窮大起點到自身的則看作0或者權值W的缺省值每次向S中加入頂點時對從其出發(fā)的所有的邊不包括指向S中頂點的邊進行松弛操作比如我們要松弛邊uv就比較u的路程值邊的權值和v的路程的大小前者更小就將v的路程值改成u的路程值與邊權的和。如下圖將起點a加入s后c和b的路程值分別為100和65均小于原來的無窮大所以都進行更新。同時將從a出發(fā)的邊放入小根堆選出最小的邊也就是從a連接到b的權值65的邊。此時比較b原來的路程值 和 a的路程值加上這條邊的權值發(fā)現(xiàn)一樣大故可以將b加入S記錄b的前一個頂點是a接著繼續(xù)更新路程、選邊循環(huán)往復。具體實現(xiàn)可以參考文末的代碼。Dijkstra算法只能處理邊權不為負的圖如果有負權值的邊就需要使用Bellman-Ford算法。Bellman-Ford算法Bellman-Ford算法是一種暴力算法不過不是遍歷所有可能的路徑而是遍歷所有的邊最短路徑的記錄方式和Dijkstra一樣需要記錄各個頂點的路程值以及各個頂點的前一個頂點初始化也是將起點自身的路程值設為0其它頂點的路程值為無窮大。在遍歷所有邊的過程中不用管選到的是哪條邊能松弛就松弛不停遍歷所有邊進行松弛直到不能再松弛就得到了所有最短路徑。具體來說比如我們遍歷到一條從頂點u到頂點v的邊首先看起點到u的路程是不是無窮大也就是u有沒有更新過路程值如果有就進行松弛操作反之則跳過。有幾點說明一下。第一比如有一條路徑是a-c-b-e如果在遍歷過程中經(jīng)過松弛操作改成了a-u-b-e這種情況按理來說是要更新e的路程值但我們不需要額外處理因為這個算法會不停的遍歷等遍歷到邊be的時候就會通過松弛操作更新路程值這一輪沒遍歷到那就下一輪。第二如果圖中存在由權值為負的邊組成的負權環(huán)Bellman-Ford算法也會失效所以是需要判斷圖中有沒有負權環(huán)的。第三在沒有負權環(huán)的情況下。如果頂點數(shù)為n那么Bellman-Ford算法最多只會遍歷n輪也就是把所有的邊遍歷n-1次最后一次判斷有沒有負權環(huán)。每輪遍歷可以保證至少選出一條邊滿足最短路徑。原因比較抽象感興趣的可以自行了解。第四Bellman-Ford算法雖然一開始也和Dijkstra算法一樣是從起點開始松弛附近的邊不斷擴展但是由于遍歷沒有限制很快就能把每個頂點都更新一遍然后再不斷縮短路徑。它能夠處理負權值的原因也在這里。如果后面有負權值的邊可能會導致前面的路徑連接這條邊后反而變短但是Dijkstra算法只看附近的邊沒法預知哪里會有負權邊也不會去處理已經(jīng)選中的邊和頂點所以碰到負權邊會失效。而Bellman-Ford算法由于本身比較“吃苦耐勞”不停地遍歷所有邊所以能應對負權邊當然代價就是效率比較低下。最后Bellman-Ford算法也有經(jīng)過優(yōu)化的版本SPFA。由于Bellman-Ford算法每輪遍歷其實只需松弛那些被修改過路程值的頂點出發(fā)的邊所以可以用一個隊列存儲這些頂點出隊列時對從該頂點出發(fā)的邊進行松弛并把修改過路程值的頂點入隊列直到隊列為空。具體可以看文末的代碼里面的BellmanFord函數(shù)就是Bellman-Ford算法優(yōu)化后的SPFA。多源最短路徑Floyd-Warshall算法Floyd-Warshall算法也可以處理帶有負權邊的圖其核心是動態(tài)規(guī)劃。對于一個三維數(shù)組DD[ i ][ j ][ k ]表示從第 i 個頂點出發(fā)只經(jīng)過前k個頂點中的若干個頂點到達第 j 個頂點的最短路徑長度也就是前面說的路程值默認都為無窮大。D[ i ][ j ][ 0 ]則表示從頂點 i 直接連接到頂點 j 的邊的權值。 將所有邊的權值輸入DD[ i ][ i ][ 0 ]設為0D[ 0 ][ j ][ k ]和D[ i ][ 0 ][ k ]沒有意義前兩個維度中的 i 和 j 的取值都是從1開始只有第三維的k才能取0但在動態(tài)規(guī)劃的過程中k也是從1開始但是會用到k-1。為方便講述下面將第 t 個頂點稱作頂點 t 或者 t。狀態(tài)轉移方程的關鍵在于怎么從D[ i ][ j ][k-1]得到D[ i ][ j ][ k ]。假設頂點 i 到頂點 j 的最短路徑經(jīng)過頂點k那么 i 到 j 的最短路徑長度是 i 到 k 的長度加 k 到 j 的長度即D[ i ][ j ][ k ]D[ i ][ k ][k-1]D[ k ][ j ][k-1]再假設沒經(jīng)過頂點k的情況那就和只經(jīng)過前k-1個頂點中的若干個頂點沒有區(qū)別D[ i ][ j ][ k ]D[ i ][ k ][ k-1 ]取二者中的較小者就是最終的狀態(tài)轉移方程D[ i ][ j ][ k ]min{D[ i ][ k ][ k-1 ]D[ k ][ j ][k-1]D[ i ][ k ][k-1]}對于任意的頂點 i 、jD[ i ][ j ][ 0 ]是 i 到 j 的邊的權值。k雖然是數(shù)組D的第三維但是在循環(huán)中是最外層的循環(huán)因子。即循環(huán)的最外層為while(kn)所以在計算D[ i ][ j ][ k ]時對于任意的 s 、t, D[ s ][ t ][k-1]都是已經(jīng)處理完成的最優(yōu)路程值。故可以保證在動態(tài)規(guī)劃的過程中上式右邊的各項都是有意義的。其次我們還需要記錄各頂點在最短路徑中的前一個頂點由于起點是任意的所以需要用二維數(shù)組來記錄。如我用的是parentparent[ s ][ d ]表示在起點為 s 的最短路徑中頂點d的前一個頂點。在前面的轉態(tài)轉移方程中如果 i 到 j 有經(jīng)過頂點k那么頂點 j 在以 i 為起點的最短路徑中的前一個頂點應該是頂點 j 在以k為起點的最短路徑中的前一個節(jié)點 也就是parent[ i ][ j ]parent[ k ][ j ]這是因為頂點k也不一定是直接連接到 j 的。如果沒有經(jīng)過第k個頂點那前一個頂點就沒有變化。降維優(yōu)化實際上為了節(jié)約空間Floyd-Warshall算法會通過在原來的空間上迭代可以將D降為二維。D[ i ][ j ]表示頂點 i 到頂點 j 的最短路徑長度。與前面不同的是這里的頂點 i 就是指下標為 i 的頂點頂點 j 同理。初始化時D[ i ][ j ]是頂點 i 到頂點 j 的邊的權值D[ i ][ i ]取0其它的取無窮大。不難發(fā)現(xiàn)在開始動態(tài)規(guī)劃之前D就是鄰接矩陣。接下來我們將在多輪動態(tài)規(guī)劃中不斷迭代讓D[ i ][ j ]從邊的權值變?yōu)樽疃搪窂介L度。首先假設頂點 i 到 j 的最短路徑要么經(jīng)過頂點0要么直連由此進行動態(tài)規(guī)劃。如果有頂點 i 到頂點 j 的最短路徑有經(jīng)過頂點0那么D[ i ][ j ]D[ i ][ 0 ]D[ 0 ][ j ]如果沒有則D[ i ][ j ]沒有變化所以狀態(tài)轉移方程為D[ i ][ j ]min{D[ i ][ j ] , D[ i ][ 0 ]D[ 0 ][ j ] }此時D中的路徑就是有經(jīng)過頂點集合{ 0 }中若干個頂點的最短路徑也就是要么經(jīng)過0要么沒有。接下來假設D[ i ][ j ]是經(jīng)過頂點集合 {012……k-1}中若干個頂點的最短路徑長度k可以等于1我們要由此推廣到包含頂點k的情況。不難得到狀態(tài)轉移方程D[ i ][ j ]min{D[ i ][ j ]D[ i ][ k ]D[ k ][ j ]}令k從0增加到編號最大的頂點n-1使用上面這個狀態(tài)轉移方程進行多輪動態(tài)規(guī)劃就可以得到真正的最短路徑。前一個頂點的記錄和前面一樣若有經(jīng)過頂點k則parent[ i ][ j ]parent[ k ][ j ]如果沒有就不變。我們可以發(fā)現(xiàn)其實整體的思路沒有變化只是不再記錄由k的值帶來的變化而是通過不斷的迭代節(jié)省空間。具體可以參考文末的代碼。參考代碼注意代碼只經(jīng)過了粗略的驗證不能保證完全正確只提供大致的思路。頭文件和Kruskal算法需要用到的并查集#includeiostream #includemap #includevector #includequeue using namespace std; class Unionfindset { public: Unionfindset(size_t n) : _ufs(n, -1) { } int Findroot(int x) {//找老大返回老大的編號 if (_ufs[x] 0) return x; else return _ufs[x] Findroot(_ufs[x]);//直接讓下屬連接老大提高找老大的效率 } void Union(int a, int b) {//交友、聯(lián)合將a看作上司 int ar Findroot(a); int br Findroot(b); if (ar ! br) { _ufs[ar] _ufs[br];//算人數(shù) _ufs[br] ar;//認老大 } } size_t Setsize(int x) {//返回x所在團體的大小 return -_ufs[Findroot(x)]; } size_t count() {//返回團體個數(shù) size_t ans 0; for (auto e : _ufs) { if (e 0) ans; } return ans; } private: vectorint _ufs; };使用鄰接矩陣實現(xiàn)的圖//用鄰接矩陣實現(xiàn)的圖 namespace Matrix { templateclass V, class W, W MAX_W INT_MAX, bool Direction false//頂點類型權值類型無窮大是否為有向圖 class Graph { typedef GraphV, W, MAX_W, Direction Self; public: Graph() default; Graph(const V* vertexs, size_t n) {//先存頂點邊后面再加上 _vertexs vectorV(n, V()); for (int i 0; i n; i) { _vertexs[i] vertexs[i]; _vIndexMap[vertexs[i]] i; } _matrix vectorvectorW (n, vectorW(n, MAX_W)); for (int i 0; i n; i) { _matrix[i][i] 0; } } int GetVertexIndex(const V v) {//返回頂點對應下標 auto it _vIndexMap.find(v); if (it ! _vIndexMap.end()) { return it-second; } else { cout 該頂點不存在 endl; return -1; } } void _AddEdge(size_t srci, size_t dsti, const W w) {//用頂點下標添加邊 _matrix[srci][dsti] w; if (!Direction) _matrix[dsti][srci] w; } void AddEdge(const V v1, const V v2, const W w) {//用頂點添加 int sr GetVertexIndex(v1); int ds GetVertexIndex(v2); if (sr -1 || ds -1) return; _AddEdge(sr, ds, w); } void BFS() { if (_vertexs.size() 0) return; queueint que; vectorbool hash(_vertexs.size(), false);//是否被訪問過 int count 0;//遍歷過的頂點數(shù) while (count ! _vertexs.size()) { for (int i 0; i hash.size(); i) {//找一個沒遍歷過的入隊 if (!hash[i]) { que.push(i); hash[i] true; count; break; } } while (!que.empty()) { cout _vertexs[que.front()] ; for (int j 0; j _matrix.size(); j) { if (_matrix[que.front()][j] ! MAX_W !hash[j]) { hash[j] true; que.push(j); count; } } que.pop(); } cout endl; } } void _DFS_Func(vectorbool hash, int set) {//DFS核心遞歸函數(shù) if (hash[set]) return; cout _vertexs[set] ; hash[set] true; for (int j 0; j _matrix.size(); j) { if (_matrix[set][j] ! MAX_W) _DFS_Func(hash,j); } } void DFS() {//封裝 vectorbool hash(_vertexs.size(), false);//是否被訪問過 while (1) { int i; for (i 0; i hash.size(); i) {//檢查遍歷完了沒 if (!hash[i]) break; } if (i ! hash.size()) _DFS_Func(hash, i); else break; cout endl; } } struct Edge {//用于方便構造最小生成樹 W _w;//權值 int _src;//該邊出發(fā)的頂點的值 int _dst;//該邊指向的頂點的值 Edge(W w) :_dst(-1), _src(-1), _w(w) {} bool operator(const Edge b) const {//用于堆中的比較 return _w b._w; } }; W Kruskal(Self mintree) {//返回權值總和mintree用于存儲最小生成樹 if (Direction) { cout 該圖為有向圖 endl; return W(); } mintree._vertexs _vertexs;//頂點都一樣邊后面加 //由于沒有調用構造函數(shù)鄰接矩陣要手動初始化 mintree._matrix.resize(_vertexs.size(), vectorW(_vertexs.size(), MAX_W)); priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存儲所有邊 for (int i 0; i _matrix.size(); i) { for (int j 0; j i; j) { if (_matrix[i][j] ! MAX_W){ Edge temp(_matrix[i][j]); temp._src i; temp._dst j; edgeque.push(temp); } } } Unionfindset ufs(_vertexs.size());//并查集 int count 1;//用于判斷是不是生成樹 W sumW();//計算權值之和 while (count!_vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (ufs.Findroot(temp._src) ! ufs.Findroot(temp._dst)) {//用并查集判斷是否構成環(huán) ufs.Union(temp._src, temp._dst); mintree._AddEdge(temp._src, temp._dst, temp._w); sum temp._w; count; } } if (count _vertexs.size()) return sum;//判斷是不是生成樹 else return W(); } W Prim(Self mintree, V src) {//st是起點 if (Direction) { cout 該圖為有向圖 endl; return W(); } mintree._vertexs _vertexs;//頂點都一樣邊后面加 //由于沒有調用構造函數(shù)鄰接矩陣要手動初始化 mintree._matrix.resize(_vertexs.size(), vectorW(_vertexs.size(), MAX_W)); size_t st _vIndexMap[src]; vectorbool hash(_vertexs.size(), true);//記錄未連接的頂點 hash[st] false; priority_queueEdge,vectorEdge,greaterEdge edgeque;//小根堆存儲附近的所有邊 for (int i st; i _matrix[st].size(); i) { if (_matrix[st][i] ! MAX_W i!st) { Edge temp(_matrix[st][i]); temp._src st; temp._dst i; edgeque.push(temp); } } int count 1; W sum W(); while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (hash[temp._dst]) { hash[temp._dst] false; mintree._AddEdge(temp._src, temp._dst, temp._w); count; sum temp._w; for (int j 0; j _matrix[temp._dst].size(); j) {//連接的頂點的所有邊加入堆 if (_matrix[temp._dst][j] ! MAX_W hash[j]) {//hash[j]防止連到舊頂點和同一個頂點優(yōu)化一點效率 Edge t(_matrix[temp._dst][j]); t._src temp._dst; t._dst j; edgeque.push(t); } } } } if (count _vertexs.size()) return sum;//判斷是不是生成樹 else return W(); } //包含從起點出發(fā)到所有頂點的最短路徑的信息 void Dijkstra(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各個頂點的最短路徑的長度 parent.resize(N, -1);//各個頂點的在各自最短路徑中的上一個節(jié)點下面簡稱父節(jié)點不斷回溯即可確定其最短路徑值為-1表示父節(jié)點是自己 vectorbool hash(N, false);//true表示該頂點屬于找到最短路徑的S反之則屬于未處理的Q priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存儲附近的所有邊 path[sr] W(); Edge t(0); t._dst sr; t._src sr; edgeque.push(t); while (!edgeque.empty()) { int cur edgeque.top()._dst;//取的是頂點而不是邊 //判斷一下從這條邊到達是不是最短路徑是的話要更新路徑長度和父節(jié)點 if (path[edgeque.top()._src] edgeque.top()._w path[edgeque.top()._dst]) { path[edgeque.top()._dst] path[edgeque.top()._src] edgeque.top()._w; parent[edgeque.top()._dst] edgeque.top()._src; } edgeque.pop(); if (hash[cur]) continue; hash[cur] true; for (int j 0; j N; j) { if (hash[j] || _matrix[cur][j] MAX_W) continue; Edge temp(_matrix[cur][j]); temp._src cur; temp._dst j; edgeque.push(temp); if (path[cur] _matrix[cur][j] path[j]) {//松弛父節(jié)點會在取出邊時更新 path[j] path[cur] _matrix[cur][j]; } } } } bool BellmanFord(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各個頂點的最短路徑的長度 parent.resize(N, -1);//各個頂點的在各自最短路徑中的上一個節(jié)點下面簡稱父節(jié)點不斷回溯即可確定其最短路徑值為-1表示父節(jié)點是自己 vectorint count(N, 0);//記錄每個頂點遍歷次數(shù)防止負權環(huán)帶來的死循環(huán) queueint verque;//頂點隊列 vectorboolhash(N, false);//記錄頂點是否在隊列里防重復 path[sr] 0; verque.push(sr); hash[sr] true; while (!verque.empty()) { int temp verque.front(); verque.pop(); hash[temp] false; count[temp]; if (count[temp] N) return false; for (int j 0; j N; j) { if (_matrix[temp][j]!MAX_W path[j] _matrix[temp][j] path[temp]) { path[j] _matrix[temp][j] path[temp]; parent[j] temp; if (!hash[j]) { verque.push(j);; hash[j] true; } } } } return true; } void FloydWarShall(vectorvectorW path, vectorvectorint parent) {//path就是D size_t N _vertexs.size(); path _matrix;//初始時就是鄰接矩陣 parent.resize(N, vectorint(N, -1)); for (int i 0; i N; i) { for (int j 0; j N; j) { if (_matrix[i][j] ! MAX_W i ! j) parent[i][j] i;//父節(jié)點也要初始化 } } for (int k 0; k N; k) { for (int i 0; i N; i) { for (int j 0; j N; j) { if (path[i][k] ! MAX_W path[k][j] ! MAX_W i ! j path[i][j] path[i][k] path[k][j]) {//有經(jīng)過頂點k path[i][j] path[i][k] path[k][j]; parent[i][j] parent[k][j]; } } } } } void Print() {//輸出圖的內容 for (auto i : _vertexs) {//打印頂點與下標關系 cout i ; } cout endl; for (int i 0; i _vertexs.size(); i) cout i ; cout endl endl; for (auto i : _matrix) {//打印鄰接矩陣 for (auto j : i) { if (j ! MAX_W) cout j ; else cout # ; } cout endl; } cout endl; int sup; for (int i 0; i _matrix.size(); i) {//打印所有的邊 if (Direction) sup _matrix[i].size(); else sup i; for (int j 0; j sup; j) { if (_matrix[i][j] ! MAX_W Direction) cout _vertexs[i] -- _matrix[i][j] -- _vertexs[j] endl; else if (_matrix[i][j] ! MAX_W) cout _vertexs[i] -- _matrix[i][j] -- _vertexs[j] endl; } } } void PrinrtShotPath(V srci, vectorW dist, vectorint parent) {//打印以srci為起點的所有最短路徑 int sr _vIndexMap[srci]; for (int i 0; i parent.size(); i) { if (i sr) continue; vectorint path; int cur i; while (cur ! -1) { path.push_back(cur); cur parent[cur]; } cout 最短路徑: endl; for (int i path.size() - 1; i 0; i--) { cout _vertexs[path[i]] -; } cout endl; cout 長度 dist[i] endl endl; } } private: vectorV _vertexs;//頂點 mapV, int _vIndexMap;//映射頂點-編號 vectorvectorW _matrix;//鄰接矩陣 }; }使用鄰接表實現(xiàn)的圖//用鄰接表實現(xiàn)的圖 namespace Link_Table { templateclass W struct Edge { W _w;//權值 int _src;//該邊出發(fā)的頂點的值 int _dst;//該邊指向的頂點的值 EdgeW* _next; Edge(W w) :_dst(-1), _src(-1), _w(w), _next(nullptr) { } bool operator(const Edge b) const {//用于堆中的比較 return _w b._w; } }; templateclass V, class W, W MAX_W INT_MAX, bool Direction false//頂點類型權值類型無窮大是否為有向圖 class Graph { typedef EdgeW Edge; typedef GraphV, W, MAX_W, Direction Self; public: Graph() default; Graph(const V* vertexs, size_t n) {//先存頂點邊后面再加上 _vertexs vectorV(n, V()); for (int i 0; i n; i) { _vertexs[i] vertexs[i]; _vIndexMap[vertexs[i]] i; } _LinkTable.resize(n, nullptr); } int GetVertexIndex(const V v) {//返回頂點對應下標 auto it _vIndexMap.find(v); if (it ! _vIndexMap.end()) { return it-second; } else { cout 該頂點不存在 endl; return -1; } } void _AddEdge(size_t sr, size_t ds, const W w) {//用頂點下標添加邊 if (sr _vertexs.size() || ds _vertexs.size() || _LinkTable[sr] _LinkTable[sr]-_dst ds)//頂點不存在或者邊已經(jīng)有了 return; Edge* temp new Edge(w); temp-_src sr; temp-_dst ds; //頭插也只能頭插 temp-_next _LinkTable[sr]; _LinkTable[sr] temp; if (!Direction) {//無向圖要再加一條反過來的 _AddEdge(ds, sr, w); } } void AddEdge(const V v1, const V v2, const W w) {//用頂點添加邊 int sr GetVertexIndex(v1); int ds GetVertexIndex(v2); if (sr -1 || ds -1) return; _AddEdge(sr, ds, w); } void BFS() { if (_vertexs.size() 0) return; queueint que; vectorbool hash(_vertexs.size(), false);//是否被訪問過 int count 0;//遍歷過的頂點數(shù) while (count ! _vertexs.size()) { for (int i 0; i hash.size(); i) {//找一個沒遍歷過的入隊 if (!hash[i]) { que.push(i); hash[i] true; count; break; } } while (!que.empty()) { cout _vertexs[que.front()] ; Edge* cur _LinkTable[que.front()]; while (cur) { hash[cur-_dst] true; count; que.push(cur-dst); cur cur-_next; } que.pop(); } cout endl; } } void _DFS_Func(vectorbool hash, int set) {//DFS核心遞歸函數(shù) if (hash[set]) return; cout _vertexs[set] ;//遍歷當前頂點 hash[set] true; Edge* cur _LinkTable[set];//尋找下一個頂點 while (cur) { _DFS_Func(hash, cur-_dst); cur cur-_next; } } void DFS() {//封裝 vectorbool hash(_vertexs.size(), false);//是否被訪問過 while (1) { int i; for (i 0; i hash.size(); i) {//檢查遍歷完了沒 if (!hash[i]) break; } if (i ! hash.size()) _DFS_Func(hash, i);//開始遞歸 else break; cout endl; } } W Kruskal(Self mintree) {//返回權值總和mintree用于存儲最小生成樹 if (Direction) { cout 該圖為有向圖 endl; return W(); } mintree._vertexs _vertexs;//頂點都一樣邊后面加 //由于沒有調用構造函數(shù)鄰接表要手動初始化 mintree._LinkTable.resize(_vertexs.size(), nullptr); priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存儲所有邊 for (int i 0; i _LinkTable.size(); i) { Edge* cur _LinkTable[i]; while (cur) { edgeque.push(*cur); cur cur-_next; } } Unionfindset ufs(_vertexs.size());//并查集 int count 1;//用于判斷是不是生成樹 W sum W();//計算權值之和 while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (ufs.Findroot(temp._src) ! ufs.Findroot(temp._dst)) {//用并查集判斷是否構成環(huán) ufs.Union(temp._src, temp._dst); mintree._AddEdge(temp._src, temp._dst, temp._w); sum temp._w; count; } } if (count _vertexs.size()) return sum;//判斷是不是生成樹 else return W(); } W Prim(Self mintree, V src) {//src是起點 if (Direction) { cout 該圖為有向圖 endl; return W(); } mintree._vertexs _vertexs;//頂點都一樣邊后面加 //由于沒有調用構造函數(shù)鄰接表要手動初始化 mintree._LinkTable.resize(_vertexs.size(), nullptr); size_t st _vIndexMap[src]; vectorbool hash(_vertexs.size(), true);//記錄未連接的頂點 hash[st] false; priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存儲附近的所有邊 Edge* cur _LinkTable[st]; while (cur) { edgeque.push(*cur); cur cur-_next; } int count 1; W sum W(); while (count ! _vertexs.size() !edgeque.empty()) { Edge temp edgeque.top(); edgeque.pop(); if (hash[temp._dst]) { hash[temp._dst] false; mintree._AddEdge(temp._src, temp._dst, temp._w); count; sum temp._w; Edge* cur _LinkTable[temp._dst]; while (cur) { if (hash[cur-_dst]) edgeque.push(*cur); cur cur-_next; } } } if (count _vertexs.size()) return sum;//判斷是不是生成樹 else return W(); } //包含從起點出發(fā)到所有頂點的最短路徑的信息 void Dijkstra(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各個頂點的最短路徑的長度 parent.resize(N, -1);//各個頂點的在各自最短路徑中的上一個節(jié)點下面簡稱父節(jié)點不斷回溯即可確定其最短路徑值為-1表示父節(jié)點是自己 vectorbool hash(N, false);//true表示該頂點屬于找到最短路徑的S反之則屬于未處理的Q priority_queueEdge, vectorEdge, greaterEdge edgeque;//小根堆存儲附近的所有邊 path[sr] W(); Edge t(0); t._dst sr; t._src sr; edgeque.push(t); while (!edgeque.empty()) { int cur edgeque.top()._dst;//取的是頂點而不是邊 //判斷一下從這條邊到達是不是最短路徑是的話要更新路徑長度和父節(jié)點 if (path[edgeque.top()._src] edgeque.top()._w path[edgeque.top()._dst]) { path[edgeque.top()._dst] path[edgeque.top()._src] edgeque.top()._w; parent[edgeque.top()._dst] edgeque.top()._src; } edgeque.pop(); if (hash[cur]) continue; hash[cur] true; Edge* ep _LinkTable[cur];//附近的邊加入堆中 while (ep) { if (!hash[ep-_dst]) { edgeque.push(*ep); if (path[cur] ep-_w path[ep-_dst]) {//松弛父節(jié)點會在取出邊時更新 path[ep-_dst] path[cur] ep-_w; } } ep ep-_next; } } } bool BellmanFord(V srci, vectorW path, vectorint parent) { size_t N _vertexs.size(); int sr _vIndexMap[srci]; path.resize(N, MAX_W);//到各個頂點的最短路徑的長度 parent.resize(N, -1);//各個頂點的在各自最短路徑中的上一個節(jié)點下面簡稱父節(jié)點不斷回溯即可確定其最短路徑值為-1表示父節(jié)點是自己 vectorint count(N, 0);//記錄每個頂點遍歷次數(shù)防止負權環(huán)帶來的死循環(huán) queueint verque;//頂點隊列 vectorboolhash(N, false);//記錄頂點是否在隊列里防重復 path[sr] 0; verque.push(sr); hash[sr] true; while (!verque.empty()) { int temp verque.front(); verque.pop(); hash[temp] false; count[temp]; if (count[temp] N) return false; Edge* cur _LinkTable[temp]; while (cur) { if (path[cur-_dst] cur-_w path[cur-_src]) {//松弛 path[cur-_dst] cur-_w path[cur-_src]; parent[cur-_dst] cur-_src; if (!hash[cur-_dst]) { verque.push(cur-_dst); hash[cur-_dst] true; } } cur cur-_next; } } return true; } void FloydWarShall(vectorvectorW path, vectorvectorint parent) {//path就是D size_t N _vertexs.size(); path.resize(N, vectorW(N, MAX_W));//初始化 parent.resize(N, vectorint(N, -1)); for (int i 0; i N; i) { Edge* cur _LinkTable[i]; while (cur) { path[cur-_src][cur-_dst] cur-_w; parent[cur-_src][cur-_dst] cur-_src;//父節(jié)點也要初始化 cur cur-_next; } path[i][i] W(); } for (int k 0; k N; k) { for (int i 0; i N; i) { for (int j 0; j N; j) { if (path[i][k] ! MAX_W path[k][j] ! MAX_W i ! j path[i][j] path[i][k] path[k][j]) {//有經(jīng)過頂點k path[i][j] path[i][k] path[k][j]; parent[i][j] parent[k][j]; } } } } } void Print() {//輸出圖的內容 for (auto i : _vertexs) {//打印頂點與下標關系 cout i ; } cout endl; for (int i 0; i _vertexs.size(); i) cout i ; cout endl endl; for (int i 0; i _LinkTable.size(); i) {//打印鄰接表 if (_LinkTable[i]) { cout _vertexs[i] ( i ): ; Edge* cur _LinkTable[i]; while (cur) { cout _vertexs[cur-_dst] ( cur-_dst ) --cur-_w-- ; cur cur-_next; } cout nullptr endl; } else cout _vertexs[i] ( i ): nullptrendl; } } void PrinrtShotPath(V srci, vectorW dist, vectorint parent) {//打印以srci為起點的所有最短路徑 int sr _vIndexMap[srci]; for(int i0;iparent.size();i) { if (i sr) continue; vectorint path; int cur i; while (cur ! -1) { path.push_back(cur); cur parent[cur]; } cout 最短路徑: endl; for (int i path.size() - 1; i 0; i--) { cout _vertexs[path[i]] -; } cout endl; cout 長度 dist[i] endlendl; } } private: vectorV _vertexs;//頂點 mapV, int _vIndexMap;//映射頂點-編號 vectorEdge* _LinkTable;//鄰接表出邊表 }; }