【資料結構】圖論（Graph）Part 1

圖（Graph）通常以G 來代表，裡面包含兩個集合… ... Trees）是一個很重要的課題，它指的是在一個包含權重的無相圖中，找到一個生成樹，它的路徑權重加起來是最小的。

GetstartedOpeninappYalaninSigninGetstarted24FollowersAboutGetstartedOpeninapp【資料結構】圖論（Graph）Part1YalaninJul2,2020·11minreadhttps://pixabay.com/illustrations/annular-solar-eclipse-eclipse-2003461/本文為清華大學開放式課程上課心得整理。

TheGraphAbstractDataTypeGraph第一次被使用是在1736年，數學家歐拉用來解決著名的柯尼斯堡七橋問題（KoenigsbergerBrueckenproblem）：在科尼斯堡有四座城市，彼此之間以七座橋連接，是否能每座橋都只走過一次，便經過四座城市回到最原始的出發點？歐拉證明只要符合每個城市（頂點）的連接邊（橋）都是偶數這個條件，上述問題是有機會完成的。

https://zh.wikipedia.org/wiki/%E6%9F%AF%E5%B0%BC%E6%96%AF%E5%A0%A1%E4%B8%83%E6%A1%A5%E9%97%AE%E9%A2%98圖（Graph）通常以G來代表，裡面包含兩個集合V（vertices，端點）和E（edges，連接兩端點的線），表達方法為G=（V,E）；頂點的degree則由與它連結的邊的數量（包含來到該點以及從該點出發的路徑總數）來決定，Graph的degree則是頂點最大的degree。

Graph有幾種類型：・UndirectedGraph（simplygraph）：（u,v）與（v,u）存在相同數量的edges・DirectedGraph（digraph）：!=https://www.youtube.com/watch?v=-_o6JoDUOKo&list=PLS0SUwlYe8cxbiGgUdK24o756wfbG3Xrw&index=35，4分03秒截圖Graph的限制如下：起點和終點不能是同一個頂點（selfedgeorselfloop）2.相同的兩個頂點，edge不能出現多次（multigraph）Graph、Vertex與Edge的特性如下：・一個有n個頂點的圖，最大的邊線數量為：UndirectedGraph：n(n-1)/2DirectedGraph：n(n-1)・兩個頂點u、v，若（u，v）∈E，則此二頂點相鄰，edge（u，v）連結頂點u、v・DirectedGraphedge，由於有方向性，所以會以uisadjacenttovandvisadjacentfromu（難翻原文照抄），edge連接頂點u、vCompleteGraphCompleteGraph指的是一種頂點彼此相連的圖，一樣分成有方向性與沒有方向性兩種，一個有n個頂點的圖，邊線數量的計算方式如下：UndirectedGraph：n(n-1)/2DirectedGraph：n(n-1)Subgraph因為特殊符號很難打決定直接上圖：同上，7分57秒截圖PathandSimplePathPath指的是圖中的端點能夠連接到另一個端點的所有路徑，Path有可能包含loop，把loop狀況去除之後的路徑便稱為SimplePath，SimplePath除了起點與終點可能相同之外，其他的都是不同點。

起點與終點相同的SimplePath又稱為Cycle，如果路徑有方向性，則套用前面的定義分別稱為DirectedPath、DirectedSimplePath與DirectedCycle。

ConnectedGraph假設有一個UndirectedGraphG，裡面的任何兩個端點u、v，都有一個路徑連接，即稱為ConnectedGraph。

ConnectedComponentandTree一個不相通的UndirectedGraph裡面的每個部分都稱為連通份量（ConnectedComponent），樹則可以當成是一個裡面沒有任何Cycle的圖（acyclicgraph）。

這個部分影片聽不太懂，但是網路上找的資料跟影片講的定義不太一樣，顧兩者皆留存：同上，12分11秒截圖StronglyConnected在DirectedGraph中，任兩個端點u、v之間都有一條路徑可以從u到v、從v到u，便稱為StronglyConnected；在DirectedGraph中，所有連通份量都有雙向通道可以連接的，便稱為StronglyConnectedComponent。

GraphRepresentationGraph可以用幾種方式表達：・相鄰矩陣（adjacencyMatrix）：以一個二維矩陣，紀錄端點之間的連結關係。

這種表達方法的缺點就是當端點之間的邊線很少的時候會非常浪費記憶體。

・相鄰列表（adjacencylists）：以Chain連接鄰近的端點。

由於要再紀錄位置，所以在complete的狀況下會比矩陣再多一倍的記憶體空間。

・反轉相鄰列表（inverseadjacencylists）：以Chain的形式紀錄from而非to端點，list的長度取決於端點的in-degree。

SequentialRepresentation以有序陣列方式表達圖，以下為圖解：https://www.youtube.com/watch?v=Mp1xmNxCrRY&list=PLS0SUwlYe8cxbiGgUdK24o756wfbG3Xrw&index=36，4分58秒截圖上方圖中以四個端點、四條邊線為例，畫出一個共13個的陣列（四個端點、邊線可以來回所以算兩次、以及一個紀錄terminal的位置），再分別將對應的連線端點填入。

AdjacencyMultilists這是一種比較複雜的list，當中記錄的nodes可以和很多list共用。

同上，6分04秒截圖陣列會紀錄三個資料：頂點、outgoing（link1）、incoming（link2）。

首先先列出節點與邊的關係如下：vivjeiej-----------011012其中ei對應vi，ej對應vj，順向搜尋是否有符合紀錄的節點，結果如下：vivjeiej-----------01NN10Ne212NN在NULL的地方記0，其他則以pointer連結下個位置。

WeightedEdgesweight指的是edge上的權重，通常用來表示端點到端點間的距離，因此需要另一個位置來儲存權重的資訊。

一個邊上面有權重的圖便稱為網路（network）。

ElementaryGraphOperations圖有三種基本的操作：遍歷、連通份量計算、生成樹（spanningtree），其中遍歷又分為深度優先搜尋（Depth-firstsearch，DFS）以及寬度優先搜尋（Breadth-firstsearch，BFS）兩種。

深度優先搜尋的順序是，當到達一個端點時，忽略兩邊的端點先往下找，直到端點未遍歷的鄰近端點為零時再回頭，結束的契機就是所有端點的相鄰端點都已經遍歷過。

https://www.youtube.com/watch?v=sPCAYbqYj5I&list=PLS0SUwlYe8cxbiGgUdK24o756wfbG3Xrw&index=37，3分20秒截圖寬度優先搜尋與深度優先搜尋相反，是優先遍歷端點的相鄰端點，再檢查被遍歷的端點是否有未遍歷的鄰近端點，循環進行直到所有端點都遍歷過一次為止。

同上，8分55秒截圖在討論連通份量計算之前，有兩個問題必須解決：這個圖是不是一個連通圖（connectedgraph）？這時候可以使用上述的遍歷方法驗證，檢查遍歷之後圖是否有未遍歷到的端點即可。

是否能辨識所有的連通份量？一樣可以使用上述的遍歷方法，在停止之後從尚未遍歷的端點重複遍歷即可。

圖最後一個重要的操作便是生成樹，顧名思義，就是一棵樹上面的點與連線就是圖的端點與邊。

生成樹邊的數量為n−1，如果再加入沒有使用到的邊（non-treeedge），就會形成一個循環（Cycle）。

spanningtree可以用DFS或BFS產生，只要將遍歷時走過的路線當成樹的連接路徑即可。

MinimumCostSpanningTrees權重最小生成樹（MinimumCostSpanningTrees）是一個很重要的課題，它指的是在一個包含權重的無相圖中，找到一個生成樹，它的路徑權重加起來是最小的。

通用的三個計算方法（greedyalgorithm）如下：・Kruskal’salgorithm：將樹裡面權重最小的邊相加，執行步驟如下：1.找到最小權重的邊2.檢查是否會形成Cycle，如果會就捨棄3.重複上述兩步驟，直到所有邊都檢查完為止・Prims’salgorithm：該演算法有幾個要點1.用minheap來儲存邊的權重2.用setrepresentation儲存端點，並檢查端點是否在同一個連通份量裡面，避免造成Cycle3.當兩個邊在同一個連通份量裡時捨棄，不同時合併Prims’salgorithm的構思為：從一個小的樹出發，找出樹周邊權重最小的邊，把邊加到樹裡面（near-to-treedatastructure），並隨時都保持樹的構造，直到樹包含圖裡的所有端點。

執行步驟如下：1.隨機選取任意端點2.檢查端點周邊，找出權重最小的邊，把邊和連接的端點加入樹中3.重複上述兩步驟，直到檢查完所有的邊為止・Sollin’salgorithm：每次都選取複數個邊，執行步驟如下：1.先產生一個forset，裡面包含若干個生成樹（每個生成樹皆含有一個端點）2.尋找每個樹最小權重的邊3.刪除出現重複選取狀況的邊，如果有兩條有相同權重的邊連接到兩棵樹，就刪除其中一條參考資料：柯尼斯堡七桥问题柯尼斯堡七桥问题（SevenBridgesofKönigsberg）是图论中的著名问题。

这个问题是基於一個現實生活中的事例：當時東普魯士柯尼斯堡（今日俄羅斯加里寧格勒）市区跨普列戈利亚河…zh.wikipedia.org演算法筆記-ComponentArticulationVertex（ArticulationPoint）（Cut-vertex）Articulation乃「關節」之意，骨骼與骨骼銜接的地方就是關節。

關節一旦被拆開，肢體之間的連繫就被切斷了。

…www.csie.ntnu.edu.tw演算法筆記-GraphAdjacencyLists「相鄰列表」。

把一張圖上的點依序標示編號。

每一個點，後方列出所有相鄰的點。

例如第4列是第4點所有相鄰的點。

另外，相鄰的點也可以想成是相鄰的邊。

第一種，直覺的實作方式，採用陣列：…www.csie.ntnu.edu.twGraph請先讀:表達人事物之間的關係(為什麼要學BinaryRelation與Graph)被vertexv指到的vertex(vertices),稱為v的successor(s);指向v的vertex…www.cyut.edu.twYalaninFollow11 1DataStructuresComputerScienceMorefromYalaninFollow