圖(Graph)

用來表示有限集合中物件之間的關係,物件在圖中以「節點/頂點(node / vertex)」呈現、關係以「邊(edge / arc)」呈現。


一、圖/簡單圖/無向圖(simple graph / undirected graph)

節點之間的邊都沒有方向性,以「直線」呈現。

一張有 3 個節點、3 條邊的無向圖


二、有向圖(directed graph / digraph)

節點之間的邊有方向性,可能為單向或雙向,各自以單箭頭及雙箭頭表示。

一張有 3 個節點、3 條邊的有向圖


三、混合圖(mixed graph)

同時包含有向邊與無向邊的圖。

一張有 3 個節點、2 條有向邊、1 條無向邊的無向圖


四、加權圖/賦權圖/網路(weighted graph / network)

每條邊各自對應一數字,代表其權重(weight),可代表兩相鄰節點關係連結的強弱。

左為「無向加權圖」、右為「有向加權圖」


五、同構(isomorphism)

若兩圖中各自節點形成的集合互為「對射」關係,稱此兩圖為「同構」。

用更簡單的方式理解,「同構」就是「相同構造」,兩張圖的節點個數相同、邊數相同、每個節點各自跟哪個節點連接也相同,唯一不同的是「長的模樣」,但既然是相同構造,兩者會被當成同一種圖研究。

左右兩組圖各自為「同構」關係


特殊的圖

一、正則圖(regular graph)

每個節點的鄰居數量皆相同,即每個節點的「度(degree)」皆相同。若每個節點的度數均為 k,稱為「k-正則圖」。


二、完全圖(complete graph)

每對節點跟節點之間皆僅有一邊連接的無向圖;若為有向圖且每對節點之間皆是雙向關係,稱為「完全有向圖(complete directed graph)」。


三、連通圖(connected graph)

節點與其他節點間至少有一個邊連接的無向圖。

若扣除節點 D,其他 3 個節點與 3 條邊所組成的即為一「連通圖」

對於有限圖來說,若將其所有的邊都改為無向後可形成(簡單)連通圖,稱為「弱連通圖(weakly connected graph)」;若當中任兩節點可透過任一方向連通,稱為「單連通圖(unilaterally connected graph)」;若當中任兩節雙向皆可透過圖中路徑抵達,稱為「強連通圖(strongly connected graph)」。

三者可以各自用更簡單的方式理解:

  1. 弱連通圖:把箭頭去掉方向後,沒有節點落單。
  2. 單連通圖:每兩個節點間必有至少一個方向可走。
  3. 強連通圖:從任一節點出發必能抵達其他所有節點。

四、二分圖/偶圖/雙分圖/二部圖(bipartite graph)

將節點分為兩個互斥的獨立集,每條邊都連接兩個集合內的節點,若其中一集合有 k 個節點、另一個集合有 r 個節點,最多可以形成 k×r 條邊,具有 k×r 條邊的二分圖稱為「完全二分圖(complete bipartite graph)」。

「完全二分圖」示意圖


五、循環圖/環形圖(cycle graph / circular graph)

可形成一單環的簡單圖,邊與節點個數相同,每個節點的度數皆為 2。若要形成循環圖,至少要有三個節點、三條邊。

若一有向圖的邊可形成單環且所有的邊的方向皆相同,稱為「有向循環圖(directed cycle graph)」。


六、樹(tree)

每兩個節點間只有一條邊的無向圖,只要是無單環的連通圖皆可稱之為「樹」。

有根樹(rooted tree)

在「樹」中,可有一節點被指定為「根(root)」,位在整棵樹的頂端。一棵有根樹除了「根」之外,還會有下列構造:

  1. 雙親節點/父節點(parent node):任兩層相連的節點中,較靠近「根」者。
  2. 子節點(child node / children):任兩層相連的節點中,較遠離「根」者,可再依其所在雙親節點的相對位置分為「左子節點(left child)」及「右子節點(right child)」。
  3. 手足節點/兄弟節點(sibling node):所有共享同一雙親節點的同層節點。
  4. 堂表手足節點(cousin node):所有同層但不共享雙親節點的節點。
  5. 葉(leaf / leaves):沒有任何子節點的節點,又稱為「外部節點(external node)」。
  6. 內部節點(internal node):至少有一個子節點的節點。
  7. 祖先(ancestor):指某一節點到根的路徑上所有節點,「根」為所有其他節點的共同祖先。
  8. 子嗣/後裔(descendant):指某一節點往遠離根方向可達的所有節點,至最底層為順著該方向抵達的「葉」。
  9. 路徑(path):連接任兩節點之間所有的邊與節點。
  10. 子樹(subtree):以根以外的節點為新節點形成的小樹,可再依其所在新的根的相對位置分為「左子樹(left subtree)」及「右子樹(right subtree)」。


「樹」構造圖,中&右圖皆以「6號節點」為基準

除上述構造外,「樹」亦包含下列性質:

  1. 層(level):定義根為第 1 層,其餘節點層數為其與根之間連接的邊數 +1。
  2. 高度(height):一節點與最遠的葉間路徑長度,對於「樹」來說,計算基準為其根,故數值與其深度相同。
  3. 深度(depth):一節點與根間路徑長度,對於「樹」來說,計算基準為其距離根最遠的葉,故數值與高度相同。
  4. 寬度(width):指該層節點個數,節點最多那一層的寬度即為「樹」寬度。
  5. 寬度(breadth):葉的個數。
  6. 直徑(diameter):距離最遠的兩葉間路徑長度。


「樹」相關性質示意圖

二元樹(binary tree)

任一雙親節點都只能有不超過 2 個子節點的有根樹。

二元滿樹(full binary tree)

每個節點都有 0 或 2 個節點的二元樹,其葉的數量必為內部節點數量 +1。

完整二元樹(complete binary tree)

最底層節點皆由左而右排列,其他層的節點皆無空缺。

完美二元樹(perfect binary tree)

所有內部節點都有 2 個子節點,且所有葉都在同一層,若高度為 n 層,則所有節點數為 2ⁿ–1。

二元搜尋樹(binary search tree)

對於任一節點而言,其左子節點最小、自己次之、右子節點最大的二元樹。

森林(forest)

指無單環的圖,跟「樹」相比,可能有不連通處,也可理解為多棵互斥的樹形成的集合。


遍歷(traversal)

指在圖中拜訪每個節點。當我們以「圖」的方式儲存資料時,「遍歷」就是在眾多資料內容中找到目標的方法。


一、節點關係呈現方式

在表示圖中節點與節點間的關係時,可以使用「鄰接表」或「鄰接矩陣」方式呈現。

鄰接表(adjacency list)

使用無序列表(unordered list)列出與每個節點相鄰的節點,範例如下:

鄰接矩陣(adjacency matrix)

以矩陣方式呈現兩節點間的關係,若有邊連接記為「1」、無邊連接記為「0」。

在上述範例中,僅為呈現「一步是否可抵達」的狀況,若要檢視「是否可以兩步抵達」,則可將鄰接矩陣乘以鄰接矩陣自己,得走兩步的「可達性矩陣(reachability matrix)」:

等號右方為走兩步的「可達性矩陣」

等號右方矩陣不僅告訴我們走兩步「能不能抵達」,還告訴我們從某節點走兩步可抵達另一對應節點的「總方法數」,舉例如下:

從 A 走兩步到 A,矩陣元素值為 2,代表用兩步從 A 走到 A 的方法共 2 種:
  1. A→B→A
  2. A→E→A
從 A 走兩步到 B,矩陣元素值為 0,代表用兩步從 A 走到 B 的方法共 0 種:
  1. 無法達成
從 B 走兩步到 B,矩陣元素值為 3,代表用兩步從 B 走到 B 的方法共3種:
  1. B→A→B
  2. B→C→B
  3. B→D→B

設「走一步」可到的可達性矩陣為 M,則走兩步的可達性矩陣為 M²、走三步的可達性矩陣為 M³...,依此類推,走 n 步的可達性矩陣為 Mⁿ。

若節點非常多,根據「小世界網路(small-world network)」,任兩節點若要抵達彼此,走的步數大約都只要十步以內就能辦到,遠比想像中來得快。


二、遍歷問題分類

根據邊或節點是否可重複拜訪,以及是否探討最短路徑,主要可分為歐拉路徑問題、哈密頓路徑問題、中國郵遞員問題、旅行推銷員問題四種。


歐拉路徑問題/一筆畫問題(Eulerian graph)

所有的邊都只拜訪過一次,節點可重複拜訪。

現在我們來比較以下三張圖,哪些圖可以透過一筆畫走完所有的邊呢?

依序比較三張圖,可發現:

  1. 左圖:C、F、G 三節點都只跟一條邊相連,只能取任兩節點為起、終點,與剩下那一個節點相連的邊必會走過兩次;其他節點皆不能做為起、終點,否則與其相連的邊必無法都只走過一次。
  2. 中間圖:可取 A、C 為起、終點,用一筆畫走完所有節點。
  3. 右圖:不管取哪兩個節點為起、終點,都可以用一筆畫走完所有節點。

總結來說,若要使用一筆畫走完一圖中所有的邊、每條邊都只經過一次,必須符合下列任一種條件:

  1. 起點與終點度數必為奇數、中間節點度數必為偶數:起點僅供離開、終點僅供抵達,中間節點有進必有出。
  2. 所有節點度數均為偶數:所有節點都有進必有出。

哈密頓路徑問題(Hamiltonian path problem)

所有的節點都只拜訪一次,邊可重複拜訪。

以下圖而言,左圖可沿箭頭方向完成「哈密頓路徑」,右圖因E節點為「十字路口」,若要抵達 D 節點與 D 節點,E 節點必定要經過兩次,故不可能找到「哈密頓路徑」。

左圖可找到哈密頓路徑,右圖不可

哈密頓路徑問題是一個「NP 完全問題(NP-Complete problem)」,意即該問題的困難度極高,目前僅能以「回溯法(backtracking)」暴力解開,時間複雜度呈指數變化,除此之外,尚無其他更有效率的演算法可解決此問題。


中國郵遞員問題(Chinese postman problem)

所有的邊都至少經過一次且可重複經過。

可以想像有一位郵差要走遍所有的街道送信,每條街道可以重複走過,要如何使送信路徑為最短。

如果是無向圖,這個問題相對容易解決,屬於「P 問題(P problem)」,但若為有向圖,則該問題亦為「NP 完全問題(NP-Complete problem)」,目前僅能以時間複雜度極高的暴力法解開。


旅行推銷員問題(travelling salesman problem, TSP)

已知所有節點與邊的權重,求在每個節點都只經過一次的情況下,可能的最短距離,也就是要找出最短的哈密頓路徑。

可假想有一名推銷員正在多個城市間出差,已經知道所有要拜訪的地點,也知道任兩地點間的距離,要如何在每座城市都只拜訪一次的情況下,使旅行距離為最短。

這個問題同樣是「NP 完全問題(NP-Complete problem)」,目前除了使用「分支定界法(branch and bound)」暴力解開外,尚無其他更有效率的演算法可解決。


三、最短路徑問題(shortest path problem)

探討在加權圖中的任兩節點間移動時,如何能有最小的權重,也就是要如何用最短的距離從某節點移動到某節點。


佛洛依德演算法(Floyd–Warshall algorithm)

從圖中任一節點出發,找出從該節點到其他節點的最短路徑;因使用三層迴圈讓任兩節點配對比較,時間複雜度為 O(n³)。

我們可以透過下列範例,認識「Floyd–Warshall 演算法」的運作方式:

「Floyd–Warshall 演算法」的第一步驟共包含三個部分:

  1. 將所有節點自己到自己的路徑長設為 0。
  2. 兩節點間路徑存在者,其路徑長設為連結兩節點邊的權重。
  3. 其他所有不相連節點間的路徑長設為 ∞。

完成後可得下圖右表,表中數字代表從 i 到 j 的路徑長。

「Floyd–Warshall 演算法」的第二步驟要找出兩節點間距離較短的路徑。

從 i 節點走到 j 節點時,可以直接從 i 走到 j,也可以從 i 經過 k 再到 j,兩者取距離較短者。將所有節點配對、一一比較後可得下圖結果,圖中上半部為第一步驟所得結果,供進行第二步驟時參考;下列三表標黃底處代表路徑較短的走法:

因發現從 A 節點經 B 節點到 C 節點的路徑長,會比 A 節點直接走到 C 節點短,因此將表中 i=A、j=C 中的數字從 4 改為 3,其餘表格內的數字因未找到更短路徑,故維持不變。

經「Floyd–Warshall 演算法」透過上述流程讓任兩節點互相配對進行判斷,最終可得任兩節點間最短路徑如下:

經「Floyd–Warshall 演算法」計算得從 i 到 j 最短路徑表

戴克斯特拉演算法(Dijkstra’s algorithm)

一般用於尋找從某一節點出發,走到其他所有節點的最短路徑,即「單源最短路徑(single source shortest path)」,類似下個段落中「寬度優先搜尋(breadth-first search, BFS)」概念。

可透過「優先隊列(priority queue)」輔助,隊列以路徑長較小者為優先,稱為「最小優先隊列(minimum priority queue)」。

在最糟的情況下,每條邊跟每個節點都要放進並取出「priority queue」中,時間複雜度為 O(|V|+|E|);而在「priority queue」中,若用「最小堆積(min-heap)」實現「最小優先隊列」,時間複雜度為 O(log|V|),因此「Dijkstra 演算法」的時間複雜度為 O((|V|+|E|)·log|V|),其中 |V| 代表圖中節點個數、|E| 代表邊數。

需要特別留意的是,使用本方法求最短路徑時,每條邊的權重不得為負,否則可能會漏找路徑更短的方法,或在帶負邊的環中不斷繞圈,詳細說明可參考 Stack Overflow

「Dijkstra 演算法」的步驟如下:

  1. 挑定一節點為始發節點 A,A 到所有節點的距離皆預設為 ∞。
  2. A 到 A 的路徑長為 0,比原本的 ∞ 短,因此將 A 到 A 的距離改為 0,並將 A 節點與 A 到 A 的路徑長資訊放進「priority queue」中。
  3. 依路徑長的數值小至大順序依序拜訪「priority queue」中的節點,檢查從 A 到該節點原有的距離,是否比從 A 節點沿本次路徑經過的距離還短。
  4. 若原有距離較短,則不變;若沿本次路徑經過的距離較短,則將 A 到該節點的路徑長與前一個節點資訊更新,並將該節點名稱與路徑長資訊放進「priority queue」中,「priority queue」中的節點順序固定依照路徑長由小到大排列。
  5. 重複 3.~4.,直到「priority queue」為空、每個節點都被拜訪過為止。

圖解「Dijkstra 演算法」過程範例如下,黃底節點代表目前所在節點、深棕底節點代表已經拜訪過的節點、黃邊為從目前所在節點離開可抵達的鄰居節點:

  1. 原圖,挑定始發節點為 A,A 至各節點路徑長皆預設為 ∞,「priority queue」為空。

  2. A 到 A 節點的路徑長為 0,比原預設的 ∞ 短,因此將 A 到 A 路徑長改為 0,並將 A 節點放進「priority queue」中。

  3. 拜訪「priority queue」路徑長最短的 A 節點,從 A 出發可抵達 B、C 兩節點。

分別判斷 A 到 B、C 兩節點的路徑長:

B 節點:預設從 A 到此的路徑長為 ∞,實際從 A 到此的路徑長為 2,實際路徑較短,故將 B 的前一個節點改為 A,路徑長改為 2,並將 B 節點放進「priority queue」中。

C 節點:預設從 A 到此的路徑長為 ∞,實際從 A 到此的路徑長為 5,實際路徑較短,故將 C 的前一個節點改為 A,路徑長改為 5,並將 C 節點放進「priority queue」中。

目前 A 到 B 的路徑長較 A 到 C 短,故在「priority queue」中,以 B 節點為優先。

  1. 拜訪「priority queue」路徑長最短的 B 節點,從 B 出發可抵達 C、D 兩節點。

分別判斷 A 到 C、D 兩節點的路徑長:

C 節點:在步驟 3. 得從 A 到此的路徑長為 5,但從 A 經過 B 到此的路徑長為 2+2=4,經過 B 節點路徑較短,故將 C 的前一個節點改為 B,路徑長改為 4,並將「priority queue」中 C 節點的路徑長資訊改為 4。

D 節點:預設從 A 到此的路徑長為 ∞,實際從 A 經 B 到此的路徑長為 2+3=5,實際路徑較短,故將 D 的前一個節點改為 B,路徑長改為 5,並將 D 節點放進「priority queue」中。

目前 A 到 C 的路徑長較 A 到 D 短,故在「priority queue」中,以 C 節點為優先。

  1. 拜訪「priority queue」路徑長最短的 C 節點,從 C 出發可抵達 E 節點。

判斷 A 到 E 兩節點的路徑長:

原預設 A 到 E 節點路徑長為 ∞,實際從 A 經 B、C 到此的路徑長為 2+2+2=6,實際路徑較短,故將 E 的前一個節點改為 C,路徑長改為 6,並將 E 節點放進「priority queue」中。

目前 A 到 D 的路徑長較 A 到 E 短,故在「priority queue」中,以 D 節點為優先。

  1. 拜訪「priority queue」路徑長最短的 D 節點,從 D 出發可抵達 E 節點。

判斷 A 到 E 節點的路徑長:

因步驟 5. 所求從 A 到 E 節點路徑長為 6,實際從 A 經 B、D 到此的路徑長為 2+3+4=9,既有路徑較短,故 E 的前一個節點維持為 C、路徑長保持為 6,E 在「priority queue」中的路徑長也維持不變。

  1. 拜訪「priority queue」路徑長最短的 E 節點,至此所有節點皆拜訪完畢,不需再判斷 E 到其他節點的路徑長。

抵達最後的 E 節點時,我們即可以知道從 A 出發到每個節點的最短路徑,包含「路徑長」與「經過節點」兩項資訊。例如要從 A 節點走到 E 節點,應遵循「A→B→C→E」方式,方能使路徑最短,路徑長為 6,若走「A→B→D→E」或「A→C→B→D→E」都會讓路徑變長。


四、遍歷方式

圖的遍歷方式可分為「寬度優先搜尋(breadth-first search, BFS)」與「深度優先搜尋(depth-first search, DFS)」兩種,前者以「隊列/佇列(queue)這種資料型別輔助、後者以「堆疊(stack)」輔助。

「queue」表示先進到其中的資料將先被處理,即「先進先出(First-In-First-Out, FIFO)」,就如同排隊時,先加入隊伍的人可以比後加入隊伍人的先享受到服務。

「stack」表示後進到其中的資料將先被處理,即「後進先出(Last In First Out, LIFO)」,就如同拿取堆疊的物品時,要先將上層物品取出,才能取得下層物品。


寬度優先搜尋(breadth-first search, BFS)

從某一節點開始,依序找到與各節點連接的所有節點,直到所有節點都被拜訪過為止;在每個節點中確認其相鄰的節點是否被拜訪過時,使用「queue」輔助實現。

在下圖範例中,遍歷從 A 點出發,「visited nodes」代表已經遍歷過的節點、「queue」代表每個與正被拜訪的節點相鄰的節點中,未被拜訪過者。隨著遍歷過程演進,「queue」當中的值會依照「先進先出」規則,依序被放進「visited nodes」。

由 A 節點出發的 BFS 示意圖,已拜訪的節點底色以深棕色表示

直觀上來說,BFS 的遍歷方式有如從某一節點一層一層往外擴。以上圖來說,可把 A 想為第一層,與 A 相連的 B、C 想為第二層,與 B、C 相連的 D、F 想為第三層,與 D 相連的 E 想為第四層;比較到同一層時,該層中任一節點先被放進「queue」中皆可。


深度優先搜尋(depth-first search, DFS)

從某一節點出發,依序拜訪兩相鄰節點,若遇重複拜訪的節點則沿原路返回,直到退回至出發節點為止;在每個節點中確認其相鄰的節點是否被拜訪過時,使用「stack」輔助實現。

在下圖範例中,遍歷從 A 點出發,「visited nodes」代表已經拜訪過的節點、「stack」代表每個與正被拜訪的節點相鄰的節點中,尚未被提出判斷是否放進「visited nodes」者。隨著遍歷過程演進,「stack」當中的值會依照「後進先出」規則,依序被放進「visited nodes」。

由 A 節點出發的 DFS 示意圖,已拜訪的節點底色以深棕色表示

直觀上來說,DFS 的遍歷方式有如從某一節點開始出發開始到處探索,走到死胡同或找不到還沒走過的節點就原路折返,直到退回原出發點為止。


五、樹遍歷(tree traversal)

「樹」是一種常見的資料結構,因此樹的遍歷常被詳加探討。

跟「圖」的遍歷一樣,樹遍歷的方式共可分「寬度優先搜尋(BFS)」與「深度優先搜尋(DFS)」兩大類。


寬度優先搜尋(breadth-first search, BFS)

由根開始,每層皆由最左至右,走到每層最右邊節點後,接下層最左邊節點。跟「圖」相比,樹的 BFS 更有一層一層依序往下的感覺。

節點中的數字代表「寬度優先搜尋(BFS)」遍歷順序


深度優先搜尋-前序遍歷(preorder traversal)

從根出發後一路往左下走,抵達最左下角的節點後,在每一層中都走到最右邊的節點再往上層走。

簡單來說,對於每個子樹而言,遍歷順序為「根、左子節點、右子節點」。

節點中的數字代表「前序(preorder)」遍歷順序


深度優先搜尋-中序遍歷(inorder traversal)

從最左下角的節點出發,先把最靠近左下角的節點都走過再往根走,最後走右邊。

簡單來說,對於每個子樹而言,遍歷順序為「左子節點、根、右子節點」。

節點中的數字代表「中序(inorder)」遍歷順序


深度優先搜尋-後序遍歷(postorder traversal)

從最左下角的節點出發,由左至右把下層節點走完,再往上一層走。

簡單來說,對於每個子樹而言,遍歷順序為「左子節點、右子節點、根」。

節點中的數字代表「後序(postorder)」遍歷順序


樹遍歷「深度優先搜尋(DFS)」小結

  1. 左子節點必定先於右子節點。
  2. 根在左子節點之前先走過,稱為「preorder」。
  3. 根在兩子節點之間走過,稱為「inorder」。
  4. 根在走完兩子節點後才走過,稱為「postorder」。


小結

  1. 圖:表示物件之間關係,以「節點」表示物件、「邊」表示節點間關係。
  2. 簡單圖:邊無方向的圖。
  3. 有向圖:邊有方向的圖,可能為單向或雙向。
  4. 混合圖:包含有向邊與無向邊的圖。
  5. 加權圖:邊有「權重」的圖。
  6. 同構:圖的架構相同,僅外觀不同。
  7. 正則圖:每個節點同度。
  8. 完全圖:任兩節點間皆有一邊連結,若為有向圖,則所有的邊皆為雙向。
  9. 連通圖:沒有節點落單,若為有向圖,可再分為「弱連通圖」、「單連通圖」與「強連通圖」。
  10. 二分圖:節點可分為兩部分。
  11. 循環圖:可形成單環,若為有向圖,則所有邊的方向相同。
  12. 樹:無環的連通圖。
  13. 有根樹:可有一節點為「根」,除此之外另可有雙親節點、左右子節點、手足節點、堂表手足節點、葉、內部節點、祖先、子嗣、路徑、左右子樹構造,以及層、高度、深度、寬度、直徑等性質。
  14. 二元樹:任一雙親節點的子節點數量不超過 2 個。
  15. 二元滿樹:任一節點的子節點數量皆為 0 或 2。
  16. 完整二元樹:非最底層節點無空缺,最底層節點由左到右排列。
  17. 完美二元樹:所有內部節點都有 2 個子節點,且葉都在同層。
  18. 二元搜尋樹:任一子樹數值大小順序為「左子節點≥根≥右子節點」。
  19. 森林:無環、但可不連通的圖。
  20. 遍歷:拜訪圖中節點。
  21. 鄰接表:用無序列表表示節點間是否可互達。
  22. 鄰接矩陣:用矩陣表示節點間是否可互達,其乘冪代表走幾步可從某節點走到其他節點或回到原節點,稱為「可達性矩陣」。
  23. 歐拉路徑問題:節點可重複拜訪,邊都只走過一次,條件為起點跟終點都必接奇數條邊、中間節點都必接偶數條邊,或者全部節點都連接偶數條邊。
  24. 哈密頓路徑問題:節點只拜訪一次,邊可重複拜訪,屬於 NP 完全問題,目前只能用回溯法暴力解開。
  25. 中國郵遞員問題:所有邊都至少經過一次且可重複經過,無向圖是 P 問題、有向圖是 NP 完全問題。
  26. 旅行推銷員問題(TSP):節點只拜訪一次,邊可重複拜訪,求最短路徑,屬於 NP 完全問題,目前只能用分支定界法暴力解開。
  27. 最短路徑問題:在加權圖中用總權重最小的方式從一節點移動到另一節點。
  28. Floyd–Warshall 演算法:求任兩節點間最短路徑,時間複雜度為 O(n³)。
  29. Dijkstra 演算法:求單緣最短路徑,以優先隊列輔助,不可用於有負邊的圖,時間複雜度為 O((|V|+|E|)·log|V|)。
  30. 隊列(queue):類似排隊,先進先出。
  31. 堆疊(stack):類似堆東西,後進先出。
  32. 寬度優先搜尋(BFS):一層一層往外拜訪所有節點;用「queue」輔助實現。
  33. 深度優先搜尋(DFS):逐一拜訪所有節點,遇到死胡同或拜訪過的節點時折返,最終回到原節點;用「stack」輔助實現。
  34. 樹的「寬度優先搜尋(BFS)」:從根開始一層一層往下走,每層內從左往右走。
  35. 前序遍歷(preorder):對於樹中任一節點而言,遍歷順序為「根→左子節點→右子節點」。
  36. 中序遍歷(inorder):對於樹中任一節點而言,遍歷順序為「左子節點→根→右子節點」。
  37. 後序遍歷(postorder):對於樹中任一節點而言,遍歷順序為「左子節點→右子節點→根」。
#離散數學 #圖論 #樹







你可能感興趣的文章

COSCUP 2022 信箱爆炸了

COSCUP 2022 信箱爆炸了

ASP.NET Core Web API 入門教學 - 開發環境基本介紹

ASP.NET Core Web API 入門教學 - 開發環境基本介紹

Navigating Rhode Island's Window Tint Laws: A Comprehensive Overview

Navigating Rhode Island's Window Tint Laws: A Comprehensive Overview






留言討論