轉自：https://segmentfault.com/a/1190000010794621
摘 要 ： 圖 論 問 題(Graph Theory)
·節(jié)點(Vertex)?與?邊（Edge）
·圖的表示：?鄰接表?和?鄰接矩陣
·這里可以分為?有向圖?和無向圖
·無向圖是一種特殊的有向圖
·有權圖?和?無權圖
·圖的遍歷：?DFS?BFS?常見可以解決的問題有：?聯通分量?Flood Fill?尋路?走迷宮?迷宮生成?無權圖的最短路徑環(huán)的判斷
·最小生成樹問題（Minimum Spanning Tree）?Prim?Kruskal
·最短路徑問題(Shortest Path)?Dijkstra?Bellman-Ford
·拓撲排序(Topological sorting)
·這里可演示〔佟－>?https://mrpandey.github.io/d3...
圖
什么是圖笛粘？
圖是一種復雜的非線性結構租悄。
在線性結構中，數據元素之間滿足唯一的線性關系曲聂，每個數據元素(除第一個和最后一個外)只有一個直接前趨和一個直接后繼屏轰；
在樹形結構中瓤球，數據元素之間有著明顯的層次關系休涤，并且每個數據元素只與上一層中的一個元素(parent node)及下一層的多個元素(孩子節(jié)點)相關；
而在圖形結構中诫舅，節(jié)點之間的關系是任意的羽利，圖中任意兩個數據元素之間都有可能相關。
圖G由兩個集合V(頂點Vertex)和E(邊Edge)組成刊懈，定義為G=(V这弧，E)
無向圖 和 有向圖
相關基礎戳這里
有權圖 和 無權圖
頂點的度
對于無向圖，頂點的度表示以該頂點作為一個端點的邊的數目虚汛。比如匾浪，圖(a)無向圖中頂點V3的度D(V3)=3
對于有向圖，頂點的度分為入度和出度卷哩。入度表示以該頂點為終點的入邊數目蛋辈，出度是以該頂點為起點的出邊數目，該頂點的度等于其入度和出度之和将谊。比如冷溶，頂點V1的入度ID(V1)=1，出度OD(V1)=2瓢娜，所以D(V1)=ID(V1)+OD(V1)=1+2=3
記住挂洛，不管是無向圖還是有向圖礼预，頂點數n眠砾，邊數e和頂點的度數有如下關系：
因此，就拿有向圖(b)來舉例，由公式可以得到圖G的邊數e=(D(V1)+D(V2)+D(V3))/2=(3+2+3)/2=4
路徑褒颈、路徑長度和回路
路徑柒巫，比如在無向圖G中，存在一個頂點序列Vp,Vi1,Vi2,Vi3…谷丸，Vim堡掏，Vq，使得(Vp,Vi1)刨疼，(Vi1,Vi2)泉唁，…,(Vim,Vq)均屬于邊集E(G)，則稱頂點Vp到Vq存在一條路徑揩慕。
一系列頂點構成路徑亭畜，路徑中所有頂點都由邊連接。
路徑長度迎卤，是指一條路徑上經過的邊的數量拴鸵。
回路，指一條路徑的起點和終點為同一個頂點蜗搔。
用圖對現實中的系統(tǒng)建模
可以用圖對現實中許多系統(tǒng)建模劲藐。
比如對交通流量建模，頂點可以表示街道的十字路口樟凄，邊表示街道聘芜。加權的邊可以表示限速或者車道的數量。建模人員可以用這個系統(tǒng)來判斷最佳路線及最有可能堵車的街道缝龄。
任何運輸系統(tǒng)都可以用圖來建模厉膀。比如，航空公司可以用圖來為其飛行系統(tǒng)建模二拐。將每個機場看成頂點服鹅，將經過兩個頂點的每條航線看作一條邊。加權的邊可以看作從一個機場到另一個機場的航班成本百新，或兩個機場之間的距離企软，這取決與建模的對象是什么。
包含局域網和廣域網（如互聯網）在內的計算機網絡饭望，同樣經常用圖來建模仗哨。
另一個可以用圖來建模的實現系統(tǒng)是消費市場，頂點可以用來表示供應商和消費者铅辞。
圖的創(chuàng)建和遍歷
圖的兩種存儲結構（表示圖）
乍看起來厌漂，圖和樹或者二叉樹很像，我們可能會嘗試用樹的方式來創(chuàng)建一個圖類斟珊，用節(jié)點來表示每個頂點苇倡。但這種情況下，如果用基于對象的方式去處理就會有問題，因為圖可能增長到非常大旨椒。 用對象來表示圖很快會變得效率低下晓褪，所以我們要考慮表示頂點或邊的其他方案。
表示頂點
創(chuàng)建圖類的第一步是要創(chuàng)建一個Vertex類保存頂點和邊综慎。這個類的作用與鏈表和二叉搜索樹的Node類一樣睛约。Vertex類有兩個數據成員： 一個用于標識頂點兔簇，另一個是表示這個頂點是否被訪問過的布爾值曙搬。分別命名為label 和 wasVisited.這個類只需要一個函數辞色，那就是為頂點的數據成員設定值的構造函數。
我們將所有頂點保存到數組中米罚，在圖類里媚狰，可以通過它們在數組中位置引用它們。
表示邊
圖的實際信息都保存在邊上阔拳，因為它們描述了圖的結構崭孤。我們容易像之前提到的那樣用二叉樹的方式去表示圖，這是不對的糊肠。二叉樹的表現形式相當固定辨宠，一個父節(jié)點只能有兩個子節(jié)點，而圖結構卻要靈活的多货裹，一個頂點既可以有一條邊嗤形，也可以有多條邊與它相連。
我們將表示圖的邊的方法稱為鄰接表?或者鄰接表數組弧圆。
這種方法將邊儲存為由頂點的相鄰頂點列表構成的數組赋兵，并以此頂點作為索引。
當我們在程序中引用一個頂點時搔预，可以高效地訪問與這個頂點相連的所有頂點的列表霹期。
構建圖
確定了如何在代碼中表圖之后，構建一個表示圖的類就容易了拯田，下面是一個Graph類的定義：
這個類會記錄一個圖表示了多少條邊历造，并使用一個長度與圖的頂點數相同的數組來記錄頂點數量。
通過for循環(huán)為數組中的每個元素添加一個子數組來儲存所有的相鄰頂點船庇，并將所有元素初始化為空字符串吭产。
當調用這個函數并傳入頂點A 和 B 時，函數會先查找頂點A 鸭轮，函數會先查找A的鄰接表臣淤，將頂點B添加到列表中，然后再查找頂點B的鄰接表窃爷，將頂點A加入列表邑蒋。最后姓蜂，這個函數會將邊數加 1.
showGraph()?函數會通過打印所有頂點及其相鄰頂點列表的方式來顯示圖：
一個完整的?Graph?類
圖的兩種遍歷方法
確定從一個指定的頂點可以到達其他哪些頂點。這是經常對圖執(zhí)行的操作寺董。我們可能想通過地圖了解到從一個城鎮(zhèn)到另一個城鎮(zhèn)有哪些路覆糟，或者從一個機場到其他機場有哪些航班刻剥。
而圖上這些操作是用算法執(zhí)行的遮咖。在圖上可以執(zhí)行以下兩種遍歷算法用于搜索：
深度優(yōu)先搜索遍歷
深度優(yōu)先搜索DFS遍歷類似于樹的前序遍歷。其基本思路是：
a) 假設初始狀態(tài)是圖中所有頂點都未曾訪問過造虏，則可從圖G中任意一頂點v為初始出發(fā)點御吞，首先訪問出發(fā)點v，并將其標記為已訪問過漓藕。
b)然后依次從v出發(fā)搜索v的每個鄰接點w陶珠，若w未曾訪問過，則以w作為新的出發(fā)點出發(fā)享钞，繼續(xù)進行深度優(yōu)先遍歷揍诽，直到圖中所有和v有路徑相通的頂點都被訪問到。
c) 若此時圖中仍有頂點未被訪問栗竖，則另選一個未曾訪問的頂點作為起點暑脆，重復上述步驟，直到圖中所有頂點都被訪問到為止狐肢。
簡單的來說添吗，深度優(yōu)先搜索包括從一條路徑的起始點開始追溯，直到到達最后一個頂點份名，然后回溯碟联，繼續(xù)追溯下一條路徑，直到到達最后的頂點僵腺，如此往復鲤孵，直到沒有路徑為止
這不是在搜索特定的路徑，而是通過搜索來查看在圖中有哪些路徑可以選擇辰如。
圖示如下：
注：紅色數字代表遍歷的先后順序裤纹，所以圖(e)無向圖的深度優(yōu)先遍歷的頂點訪問序列為：V0，V1丧没，V2鹰椒，V5，V4呕童，V6漆际，V3，V7夺饲，V8
如果采用鄰接矩陣存儲奸汇，則時間復雜度為O(n2)施符；當采用鄰接表時時間復雜度為O(n+e)。
深度優(yōu)先搜索的算法比較簡單： 訪問一個沒有訪問過的頂點擂找，將它標記為已訪問戳吝，再遞歸地去訪問在起始點的鄰接表中其他沒有訪問過的頂點。
要讓該算法運行贯涎，需要為Graph類添加一個數組听哭，用來儲存已訪問過的頂點，將它所有元素的值全部初始化為false塘雳。Graph類的代碼片段演示了這個新數組及其初始化過程：
現在我們可以開始編寫深度優(yōu)先搜索函數：
代碼中用到了print()函數陆盘，這樣我們可以查看當前正在訪問的頂點。當然败明，dfs()不想要print()也能運行隘马。
注意?深度優(yōu)先算法屬于盲目搜索，無法保證搜索到的路徑為最短路徑妻顶。
執(zhí)行深度優(yōu)先搜索
完整示例
戳這里
廣度優(yōu)先搜索遍歷
廣度優(yōu)先搜索遍歷BFS類似于樹的按層次遍歷酸员。其基本思路是：
a) 首先訪問出發(fā)點Vi
b) 接著依次訪問Vi的所有未被訪問過的鄰接點Vi1，Vi2讳嘱，Vi3幔嗦，…，Vit并均標記為已訪問過呢燥。
c) 然后再按照Vi1崭添，Vi2，… 叛氨，Vit的次序呼渣，訪問每一個頂點的所有未曾訪問過的頂點并均標記為已訪問過，依此類推寞埠，直到圖中所有和初始出發(fā)點Vi有路徑相通的頂點都被訪問過為止屁置。
圖示如下：
因此，圖(f)采用廣義優(yōu)先搜索遍歷以V0為出發(fā)點的頂點序列為：V0仁连，V1蓝角，V3，V4饭冬，V2使鹅，V6，V8昌抠，V5患朱，V7
如果采用鄰接矩陣存儲，則時間復雜度為O(n2)炊苫，若采用鄰接表裁厅，則時間復雜度為O(n+e)冰沙。
簡單的來說，廣度優(yōu)先搜索從一個頂點開始执虹，嘗試訪問盡可能靠近它的頂點拓挥。本質上這種搜索在圖上是逐層移動的，首先檢查最靠近第一個頂點的層袋励，再逐漸向下移動到離起始頂點最遠的層
廣度優(yōu)先搜索算法使用了抽象的隊列而不是數組來對已經訪問過的頂點進行排序侥啤。算法工作原理如下：
查找與當前頂點相鄰的未訪問頂點，將其添加到已訪問頂點列表及隊列中;
從圖中取下一個頂點v插龄，添加到已訪問的頂點列表
將所有與v相鄰的未訪問頂點添加到隊列愿棋。
執(zhí)行廣度優(yōu)先搜索
以上程序的輸出結果：
關于廣度優(yōu)先遍歷的應用
-> d3中的each()api?node.each(function)
查找最短路徑
圖最常見的操作之一就是尋找從一個頂點到另一個頂點的最短路徑.
考慮下面的例子：
假期中科展，你將在兩個星期的時間里游歷10個旅游城市均牢，去那里最富盛名的景點（1 個），你希望通過最短路徑算法才睹，找出開車游歷10個城市行駛的最小歷程數徘跪。
另一個最短路徑問題涉及創(chuàng)建一個計算機網絡時的開銷，其中包括兩臺電腦之間傳遞數據的時間琅攘，或者兩臺電腦建立和維護連接的成本垮庐。?
最短路徑算法可以幫助確定構建此網絡的最有效方法。
廣度優(yōu)先搜索對應的最短路徑
在執(zhí)行廣度優(yōu)先搜索時坞琴，會自動查找從一個頂點到另一個相鄰頂點的最短路徑哨查。
例如：要查找從頂點A到頂點D的最短路徑，我們首先會查找從A到D是否有任何一條單邊路徑剧辐，接著查找兩條邊的路徑寒亥，以此類推。這正是廣度優(yōu)先搜索的搜索過程荧关，因此我們可以輕松地修改廣度優(yōu)先搜索算法溉奕，找出最短路徑。
確定路徑
要查找最短路徑忍啤，需要修改廣度優(yōu)先搜索算法來記錄從一個頂點到另一個頂點的路徑加勤，這需要對Gragh類做一些修改。
首先同波，需要一個數組來保存從一個頂點到下一個頂點的所有邊鳄梅。我們將這個數組命名為edgeTo。 因為從始至終使用的都是廣度優(yōu)先搜索函數未檩，所以每次都會遇到一個沒有標記的頂點戴尸，除了對它進行標記外，還會從鄰接列表中我們正在搜索的那個頂點添加一條邊到這個頂點讹挎。
下面是新的bfs()函數 和需要添加到Gragh類的代碼：
現在我們需要一個函數校赤，用于展示圖中連接到不同頂點的路徑吆玖。函數pathTo() 創(chuàng)建了一個棧，用來儲存與指定頂點有共同邊的所有頂點马篮。
以下是pathTo()函數的代碼沾乘，以及一個簡單的輔助函數：
需要確保將以下聲明添加到 Graph()構造函數中：
有了這個函數，我們要做的就是編寫一些客戶端代碼來顯示從源頂點到某個特定頂點的最短路徑浑测。
查找一個頂點的最短路徑
以上程序輸出結果為：
0-2-4
也就是從頂點 0 到頂點4 的最短路徑
拓撲排序
在圖論中翅阵，拓撲排序（Topological Sorting）是一個有向無環(huán)圖（DAG, Directed Acyclic Graph）的所有頂點的線性序列。
該序列必須滿足下面兩個條件：
每個頂點出現且只出現一次
若存在一條從頂點 A 到頂點 B 的路徑迁央，那么在序列中頂點 A 出現在頂點 B 的前面
有向無環(huán)圖（DAG）才有拓撲排序掷匠，非DAG圖沒有拓撲排序一說。
它是一個 DAG 圖岖圈，那么如何寫出它的拓撲排序呢讹语？這里說一種比較常用的方法：
從 DAG 圖中選擇一個 沒有前驅（即入度為0）的頂點并輸出。
從圖中刪除該頂點和所有以它為起點的有向邊蜂科。
重復 1 和 2 直到當前的 DAG 圖為空或當前圖中不存在無前驅的頂點為止顽决。后一種情況說明有向圖中必然存在環(huán)。
于是导匣，得到拓撲排序后的結果是 { 1, 2, 4, 3, 5 }才菠。
通常，一個有向無環(huán)圖可以有一個或多個拓撲排序序列贡定。
拓撲排序的應用
拓撲排序通常用來“排序”具有依賴關系的任務赋访。它與深度優(yōu)先搜索BFS類似。不同的是缓待，拓撲排序算法不會立即輸出已訪問的頂點蚓耽，而是訪問當前頂點鄰接表中的所有相鄰頂點，直到這個列表窮盡時命斧，才將當前頂點壓入棧中田晚。
舉一個例子如下圖：
其拓撲排序可以是：
1,2,3,4,5,7,9,10,11,6,12,8
也可以是：
? ? 9,10,11,6,1,12,4,2,3,5,7,8
再比如，如果用一個DAG圖來表示一個工程国葬，其中每個頂點表示工程中的一個任務贤徒，用有向邊<A,B>表示在做任務 B 之前必須先完成任務 A。故在這個工程中汇四，任意兩個任務要么具有確定的先后關系接奈，要么是沒有關系，絕對不存在互相矛盾的關系（即環(huán)路）通孽。
其他經典問題
有向圖周期檢測：
強連通組件圖
以上不少內容來自《數據結構與算法 javascript》這本書
,感覺講的很糟糕 ,也有可能是譯者的問題序宦。 回頭翻一翻其他資料 重新整理下 并且補上相關算法的應用代碼
常見問題
分別用廣度優(yōu)先遍歷和深度優(yōu)先遍歷展開下面節(jié)點
我們用筆者畫的d3 tree 看看是怎樣的tree結構
https://codepen.io/AlexZ33/pe...點擊預覽
廣度優(yōu)先遍歷：
深度優(yōu)先遍歷：
關系型數組轉換成樹形結構對象
期望輸出:
[{"id":1,"value":"1","children":[{"id":4,"value":"4","children":[]},{"id":5,"value":"5","children":[]}]},{"id":3,"value":"3","children":[{"id":2,"value":"2","children":[]}]}]
