建中資訊科校內培訓講義 – 圖論

Size: px

Start display at page:

Download "建中資訊科校內培訓講義 – 圖論"

冈服父仇
5 years ago
Views:

Chapter 1 緒論 1-1 起源大數學家尤拉 Euler (1707~1783) 由於在 1735 年時右眼失明, 所以便到山明水秀的 Königsberg 去度假, 希望能抒解一下工作壓力, 而故事就從這裡開始 Königsburg 市有一條 Pregel 河流經, 河的中心有兩個小島, 小島與河的兩岸有七座橋相連接當地流傳的一則謎題是, 要如何才能從某一塊土地開始

關於圖論的第一本著作正式宣告圖論這門學問誕生圖論是一門探討物件之間如何關連的學問在前面的故事中我們提到的七橋問題, 其本質上就是在討論陸地之間透過橋樑的連結關係我們可以把整個鳥瞰圖抽象成如下面中間圖的型式 ; 而如果我們再進一步地更簡單地單純用一個點來表示一個陸塊, 並且依照它們之間的橋樑連接關係用邊連接起來, 那最後我們會得到如下面的示意圖於是,

1 Chapter 1 緒論 1-1 起源大數學家尤拉 Euler (1707~1783) 由於在 1735 年時右眼失明, 所以便到山明水秀的 Königsberg 去度假, 希望能抒解一下工作壓力, 而故事就從這裡開始 Königsburg 市有一條 Pregel 河流經, 河的中心有兩個小島, 小島與河的兩岸有七座橋相連接當地流傳的一則謎題是, 要如何才能從某一塊土地開始將每一座橋恰好經過一次尤拉不只想要解決七橋問題, 更希望能夠找到所有類似問題的一般性結論於是, 一個不僅解決了七橋問題同時更一般的結論就這樣出現了 1736 年 Euler 的一篇文章奠基了圖論這門學問之後的整整兩百年, 不同領域的人在他們各自的崗位上, 以不同的名稱不同的內容, 探索與 Euler 發現的圖一樣的概念一直到 1936 年,König 關於圖論的第一本著作正式宣告圖論這門學問誕生圖論是一門探討物件之間如何關連的學問在前面的故事中我們提到的七橋問題, 其本質上就是在討論陸地之間透過橋樑的連結關係我們可以把整個鳥瞰圖抽象成如下面中間圖的型式 ; 而如果我們再進一步地更簡單地單純用一個點來表示一個陸塊, 並且依照它們之間的橋樑連接關係用邊連接起來, 那最後我們會得到如下面的示意圖於是, 七橋問題其實就相當於是要求我們從圖中的某一點出發, 不重複亦不遺漏地將每一條邊都走過一次然而, 對於所有類似於上面右圖的這種由點和邊連結而成的圖, 我們都可以問同樣的問題, 這就是一般化之後的河與橋的問題我們接著要討論的對象說穿了就是像這樣的一個東西其他例子如電腦網路的連結道路鋪設人與人之間的互動關係, 都可以透過類似的圖來表示在這些圖當中, 我們以個別的點表示物件, 而以邊連接標示它們之間的關係因此, 簡單而言, 我們所要討的圖就是一些點跟邊的組合在圖當中, 物件的實際長度跟位置其實都不是重要的, 我們關心的重點只有物件之間怎麼連接的問題圖論當中沒有複雜的幾何結構, 只有點跟邊兩種最單純的元素, 所以其討論往往是非常具離散味道的 ; 事實上, 圖論通常也是被歸類在離散數學的分支之中首先, 我們將簡單地介紹圖論的基本要素, 並且來看看以圖論的觀點所產生的演算法如何解決 Königsberg 七橋問題, 以及一些衍生出來的相關議題 1 頁

2 1-2 名詞與定義圖論的相關專有名詞十分繁多, 在此僅列出部分較重要的名詞與其簡要定義 A. 基本定義頂點 (Vertex): 在圖形中的點邊 (Edge): 圖形中連接兩個頂點的連線, 常常寫成 e(u,v) 代表有一條從 u 連到 v 的邊, 而 u 和 v 是其端點邊是無向的 ( 沒有特定規定的方向 ), 因此 e(u,v) = e(v,u) 弧 (Arc) : 弧可以視為有向的邊, 常常寫成 arc(u,v) 代表有一條從 u 連到 v 的弧由於弧是有向的, 因此 arc(u,v) arc(v,u) 相鄰 (Adjacent): 無向圖中, 兩個點 v 和 u 相鄰當且僅當 v 和 u 之間存在一條邊有向圖中, 一般若存在一條弧 (u,v), 則稱 v 和 u 相鄰圖 (Graph): 一個圖可以用 G = (V,E) 來表示, 其中 V 是頂點集合,E 是邊集合 B. 圖的種類及其他定義簡單圖 (Simple graph): 沒有環且沒有多重弧的圖稱作簡單圖連通圖 (Connected graph): 對於所有點對之間都至少有一條路徑可以相通有向圖 (Directed graph): 若圖中的邊皆為有向邊 ( 弧 ) 則此圖稱作有向圖無向圖 (Undirected graph): 若圖中的邊皆為無向邊則此圖稱作有向圖路徑 (Path): 圖 G 中一個點邊交替出現的序列 p v e v e e v, 滿足 v V, e E, i j i j 1 i j i0 i1 i1 i2 ik ik e ( v, v ) ( 亦有人稱之為途徑 (walk), 而把簡單路徑才稱為路徑 ) 簡單路徑 (Simple Path): 頂點與邊皆不重複的路徑分支度 (Degree): 一個頂點的度是指與該邊相關聯的邊的條數無向圖 : deg( v) 2 E ; 有向圖 : deg ( v) deg ( v) v V ( 握手定理 ) 入分支度 (In-degree): 在有向圖中, 一個頂點 v 的入度是指與該邊相關聯的入邊 ( 即邊的目標是 v) 條數, 記作 deg ( v) 出分支度 (Out-degree): 在有向圖中, 一個頂點的出度是指與該邊相關聯的出邊 ( 即邊的起始端是 v) 條數, 記作 deg ( v) 迴路 ( 或稱圈,Cycle): 若有一條路徑可以使一個頂點由自己出發並回到自己, 則稱此路徑為迴路子圖 (Sub-graph):G' 稱作圖 G 的子圖如果 V( G') V( G) 以及 E( G') E( G) 生成子圖 (Spanning Sub-graph): 即包含 G 的所有頂點的連通子圖, 即滿足條件 V( G') V( G) 的 G 的子圖 G 生成樹 (Spanning Tree): 設 T 是圖 G 的一個子圖, 如果 T 是一棵樹, 且 V( T) V( G), 則稱 v V v V T 是 G 的一個生成樹即 G 的生成子圖, 且子圖為樹有向無環圖 DAG (Directed Acyclic Graph): 顧名思義, 是有向圖且為無環圖 ij ij 2 頁

(dense graph), 優點是可以迅速的修改任意點對的狀態, 但有空間複雜度過大的缺點, 在 V 過大時恐有記憶體使用量 ( 內存溢出 ) 上的顧慮對應的鄰接矩陣 B.

如果有多個節點鄰接, 就以不斷往後串的方式表示之 ( 如下圖 ) 此種表示法常用於稀疏圖 (Sparse Graph), 原因是稀疏圖的邊數相對較少, 因此使用鄰接矩陣的話將會浪費掉大半的記憶體, 此時則可以考慮使用鄰接串列

3 Chapter 2 基本知識 2-1 圖的表示法 A. 鄰接矩陣 (Adjacency Matrix) Space Complexity: O(V 2 ) 利用一個二維矩陣 ( 陣列 ) 如 adj[u][v] 來記錄頂點 u 與頂點 v 的相鄰狀況, 這種表示法多用於稠密圖 (dense graph), 優點是可以迅速的修改任意點對的狀態, 但有空間複雜度過大的缺點, 在 V 過大時恐有記憶體使用量 ( 內存溢出 ) 上的顧慮對應的鄰接矩陣 B. 鄰接串列 (Adjacency List) Space Complexity: O(E) 藉由鏈結串列 (Linked-list) 來實作的一種表示法對於每個節點, 用鏈結串列的方式以指標指向其所鄰接的節點, 如果有多個節點鄰接, 就以不斷往後串的方式表示之 ( 如下圖 ) 此種表示法常用於稀疏圖 (Sparse Graph), 原因是稀疏圖的邊數相對較少, 因此使用鄰接矩陣的話將會浪費掉大半的記憶體, 此時則可以考慮使用鄰接串列起點終點指標對應的鄰接串列 NULL 3 NULL 2-2 圖的遍歷及走訪所謂圖的遍歷, 或者是稱作是走訪, 意思就是依照著某個順序來一個個訪問圖中的各個節點, 常見的演算法有深度優先搜尋及廣度優先搜尋, 之所以稱作搜尋是因為這些走訪方式亦可以視為是搜索特定節點的方式然而, 雖然演算法的名字是搜尋 (Search), 但實質上卻是一一走訪各個節點, 因此也有人稱作是深度 ( 廣度 ) 優先走訪 (Traversal) 3 頁

4 A. 深度優先搜尋 (Depth-First Search, DFS) I. 基本概念所謂的深度優先搜尋, 顧名思義, 我們對於走訪各節點順序採取的是一種先深的策略, 意即若考慮一個圖中的點, 對於訪問過這個點之後, 我們應該首先接著走訪其兒子節點而非兄弟節點 II. 特性 DFS 的特性非常顯而易見, 由於每次搜尋都是先深入到最底端才回溯到上一層找尋其他可能的路徑, 因此不難聯想到堆疊 (Stack) 先進後出 (FILO) 的特性, 因此, 對於 DFS 我們通常使用堆疊實踐, 對於層數較少的狀況, 亦可以直接寫成遞迴呼叫, 利用系統堆疊實踐 III. DFS 生成樹以及邊的分類藉由 DFS 遍歷整張圖後, 若此圖為連通圖, 我們將會得到一棵 DFS-Tree 也就是這張圖的一棵生成樹, 而若非連通圖, 則會得到兩棵以上的 DFS-Tree, 而若考慮這些 DFS-Tree, 我們可以將 DFS 過程中碰到的邊分作四大類 : 1. Tree Edge : 屬於 DFS-Tree 上的邊 2. Forward Edge: 連向 DFS-Tree 中相對子孫的邊 3. Back Edge: 連向 DFS-Tree 中相對祖先的邊, 加入此邊會造成環 4. Cross Edge: 非屬以上三種的邊即為 Cross Edge IV. 虛擬碼 Function DFS ( bool[ ] Visited, int Start, stack Stack ) 1 Set Visited[ ] all False. 3 push Start into Stack. // 將起點放入堆疊 4 While Stack is not empty 5 Do Curr top element of Stack. 6 Pop the top element of Stack. 7 If Visited[Curr]=False // 若堆疊頂端的點尚未遍歷 8 Then Visited[Curr] True. 9 For Next, all vertices adjacent to Curr 10 Do Push Next into Stack. 11 End If. 12 End While. 使用的資料結構為鄰接矩陣的話, 可以以 O(V 2 ) 的時間遍歷整張圖 ; 使用鄰接串列的話, 則可以用 O(V+E) 的時間遍歷整張圖 4 頁

5 B. 廣度優先搜尋 (Breadth-First Search, BFS) I. 基本概念相對於深度優先搜尋, 如其名, 走訪順序相對於 DFS 的深度優先,BFS 改採廣度優先的策略, 意思是對於圖中的某一節點, 拜訪過後是先接著拜訪同一層的兄弟節點, 之後才拜訪子孫節點 ( 所謂的層數是指在 BFS Tree 中和起始點的距離 ) II. 特性 BFS 最重要的特性其實也十分顯著, 由於其先廣的策略, 簡單來說就是一種自原點擴散的概念觀察一下就會發現, 由於對於每一個節點都是先拜訪同層節點之後再拜訪下一層的節點, 因此, 我們將可以保證, 每個節點被拜訪到後在 BFS-Tree 中的位置其與起始點 ( 即 BFS-Tree 中的根結點, Root) 的距離必定為最短由於 BFS 永遠是先拜訪同層的點, 換句話說, 對於每個點接下來下一層將被考慮的點一定是比較晚被拜訪的, 這讓我們聯想到佇列 (Queue) 先進先出 (FIFO) 的特性, 因此, 我們可以以維護一個佇列來實作 BFS III. 虛擬碼 \ Function BFS ( bool[ ] Visited, int Start, queue Queue ) 1 Set Visited[ ] all False. 2 Visited[Start] True. 3 push Start into Queue. // 將起點放入佇列 4 While Queue is not empty 5 Do Curr front element of Queue. 6 pop the Queue. 7 For Next, all vertices adjacent to Curr // 找出相鄰且尚未遍歷的點 8 If Visited[Next]=False 9 Then Visited[Next] True. 10 push Next into Queue. // 將他們放入佇列 11 End if. 12 End While. 虛擬碼整體而言跟 DFS 大同小異, 唯獨將 Stack 換成 Queue 使用的資料結構為鄰接矩陣的話, 可以以 O(V 2 ) 的時間遍歷整張圖 ; 使用鄰接串列的話, 則可以用 O(V+E) 的時間遍歷整張圖 ~ Note ~ 5 頁

6 C. 拓樸排序 (Topological Sort) I. 基本概念拓樸排序的名字中雖有排序二字, 但他與我們所熟知的一些序列排序演算法如 Quick- Sort Merge Sort 等不同, 拓樸排序所排序的對象是圖, 對於一張有向圖, 我們可以藉由拓樸排序來得到一個拜訪順序使得當一個節點被拜訪時, 其入分支的所有來源節點都已經被拜訪, 可以參考下面的附圖此外, 拓樸排序顯然不一定都只有唯一解 II. 條件限制知道了拓樸排序的用意後, 我們不難發現到, 對於一個有 Cycle 的圖, 我們是無法利用拓樸排序對其得到一個符合條件的拜訪順序的, 理由是因為形成 Cycle 的那些節點彼此是彼此的前序節點, 意思就是 Cycle 中沒有一個節點可以符合拜訪條件因此, 我們只能對一張有向無環圖 (DAG) 作拓樸排序的作業 III. 時間戳記 (Time Stamp) 現在, 我們要引進一種叫做時間戳記的標號 (Label) 概念, 所謂的一個節點的時間戳記, 意思就是在走訪這張圖時進出該節點的時間點, 時間戳記的概念可以幫助我們解決一些問題 IV. 演算法對於拓樸排序這個問題, 我們便可以利用剛剛所提到的時間戳記的概念解決首先, 以 DFS 遍歷一次整張圖, 並在過程中記錄下各個節點訪問結束的時間點, 而最後我們可以很容易的得到拓樸排序的結果, 只要將時間戳記的標號順序反過來就可以了 V. 實際應用拓樸排序有很多的應用, 可以參考相關書籍, 其中一個很直覺的用途就是可以拿來排定事務處理的順序等等有先決條件 ( 意即在做某些事前須先完成某些事 ) 的事情 6 頁

7 VI. 虛擬碼建中資訊科校內培訓講義圖論 Function Topological_Sort ( bool[ ] Visited, stack Stack, int[ ] Stamp ) 1 Time 0. // 初始化時間為 0 2 Set Visited[ ] all False. 3 For All the vertex V in the DAG // 對 DAG 作一遍 DFS 4 Do If Visited[V]=False 5 Then Visited[V] True. 6 push V into Stack. 7 While Stack is not empty 8 Do Curr top element of Stack 9 pop the Stack. 10 Time Time+1 // 時間戳記, 11 Stamp[Time] Curr. // 記錄該時間被拜訪的節點 12 For Next, all vertices adjacent to Curr 13 If Visited[Next]=False 14 Then Visited[Next] True. 15 push Next into Stack. 16 End if. 17 End While. 18 End if. 使用的資料結構為鄰接矩陣的話, 可以以 O(V 2 ) 的時間對頂點進行拓樸排序 ; 使用鄰接串列的話, 則可以用 O(V+E) 的時間對頂點進行拓樸排序想一想? 請比較遍歷圖的 D/BFS 與狀態搜索的 D/BFS 之異同為什麼 BFS 有各節點在 BFS-Tree 中層數必為可能的最小值但 DFS 卻沒有此特性? 為何將 DFS 時所記錄的時間戳記順序顛倒過來就必定是一種合法的拓樸排序順序呢? Do Exercise! UVa : 336, 10305, 10926, TIOJ : 頁

2-3 圖的連通性與元件建中資訊科校內培訓講義圖論我們如果要檢驗一個圖的連通性, 可以使用前面提到的深度優先走訪 (DFS), 但在 DFS 的過程中, 我們除了可以查詢此圖的連通塊以外, 其實只要加一些記錄, 就可以得到很多有用的相關訊息因此, 這節我們將從基本的 DFS 延伸下去, 說明這些能夠利用 DFS 得到的資訊 A.

8 2-3 圖的連通性與元件建中資訊科校內培訓講義圖論我們如果要檢驗一個圖的連通性, 可以使用前面提到的深度優先走訪 (DFS), 但在 DFS 的過程中, 我們除了可以查詢此圖的連通塊以外, 其實只要加一些記錄, 就可以得到很多有用的相關訊息因此, 這節我們將從基本的 DFS 延伸下去, 說明這些能夠利用 DFS 得到的資訊 A. 無向圖的關鍵點 ( 或稱割頂, Articulation Point) I. 基本概念無向圖的關鍵點的集合是該無向圖頂點集合中的一個特殊子集合, 一個頂點被我們稱為關鍵點若且為若該無向圖只要拔掉該頂點則該無向圖不連通, 而這個性質使得關鍵點有它的重要性存在 II. 性質 1. 考慮 DFS-Tree 中的根節點 (Root): 如果有兩個節點 A B 在 DFS-Tree 中皆為根節點 (Root) 的兒子, 則 A 必無法經由其他的邊與 B 相連, 因此, 此時根節點 (Root) 顯然為一關鍵點 2. 考慮 DFS-Tree 中的非根節點 v: 設 v 的某個兒子節點為 u, 則可以發現, 如果 u 與 u 的子孫節點都不存在指向 v 的 Back Edge, 則刪除 v 之後,u 必然無法跟 v 的祖先或是兄弟節點連通, 因此, 此時 v 即為一關鍵點 III. 演算法我們可以對於每個節點, 多維護兩個值, 一個是該節點在 DFS-Tree 中的深度, 我們先稱之為該節點的 dep 值 ; 另一個則是該節點在 DFS-Tree 中的所有 Back Edge 之中, 最小可以連接到深度多小的節點, 我們先稱之為該節點的 low 值有了 dep 值和 low 值之後, 我們就可以很容易的得到一個求無向圖中關鍵點的演算法 : 對於根節點, 只要在 DFS-Tree 中的兒子節點超過兩個, 則根節點為關鍵點 ; 對於其他節點 v, 只要兒子節點 u 的 low 值大於等於該節點 v 的 dep 值, 則節點 v 為關鍵點 8 頁

9 VI. 虛擬碼 Function Find_AP ( bool[ ] Visited, int Start, int[ ] Dep, int[ ] Low, List AP ) 1 Set Visited[ ] all False. 2 Visited[Start] True. 3 Clear List AP. 4 DFS( Visited, Start, NIL, 0, Dep, Low, AP ). Function DFS ( bool[ ] Visited, int Curr, int Prev, int Depth, int[ ] Dep, int[ ] Low, List AP ) 1 Visited[Curr] True. 2 Dep[Curr] Depth. 3 Count 0. // 計算當前節點 Curr 的兒子數 4 For Next, all vertices adjacent to Curr 5 If Visited[Next]=True And Next is not Prev 6 Then Low[Curr] Min{ Low[Curr], Dep[Next] }. 7 End if. 8 If Visited[Next]=False 9 Then DFS( Visited, Next, Curr, Depth+1, Dep, Low, AP ). 10 Count Count If (Depth=0 And Count>1) Or (Depth>0 And Low[Next] Dep[Curr]) 12 Then If Curr is not in the List AP, Add Curr to The List AP. 13 End if. 14 End if. 15 End For. 由於僅僅是在 DFS 上做額外的標記動作, 故時間複雜度與普通的 DFS 相同使用的資料結構為鄰接矩陣的話, 可以以 O(V 2 ) 的時間求出圖的所有關鍵點 ; 使用鄰接串列的話, 則可以用 O(V+E) 的時間求出圖的所有關鍵點 More Extend Ext. 無向圖的橋 (Bridge) 無向圖的橋的集合是該無向圖邊集合中的一個特殊子集合, 一條邊被我們之稱為橋若且為若該無向圖只要拔掉該條邊則該無向圖不連通不覺得橋的概念和剛剛提到的關鍵點 (Articulation Point) 很像嗎? 只是一個是頂點一個是邊, 其實, 求出無向圖中的橋的方法與求關鍵點的大小是大同小異的, 你能夠自己想出如何求出那些邊是橋嗎? 9 頁

所謂的連通元件 (Connected Component) 是一個有向圖或無向圖的子圖, 且該子圖滿足任兩個節點皆互相連通, 而且無法在維持該性質下加入任何其他的頂點或邊換句話說, 就是一個極大的連通子圖 (Maximal Connected Subgraph) B. 有向圖的強連通元件 (Strongly-Connected Component, SCC) I.

10 所謂的連通元件 (Connected Component) 是一個有向圖或無向圖的子圖, 且該子圖滿足任兩個節點皆互相連通, 而且無法在維持該性質下加入任何其他的頂點或邊換句話說, 就是一個極大的連通子圖 (Maximal Connected Subgraph) B. 有向圖的強連通元件 (Strongly-Connected Component, SCC) I. 基本概念如果一個有向圖中的每一個頂點對於其他的每個節點都存在著一條路徑 (Path) 能夠到達, 則我們稱該有向圖強連通 (Strongly Connected) 因此, 一個有向圖的強連通元件即為該有向圖的一個極大強連通子圖 II. 性質有向圖的強連通元件有一個很重要的性質當我們求出一個有向圖的強連通元件之後, 我們可以把整個強連通元件視作一個點, 該點對於不在所處強連通元件的節點的邊即為該強連通元件中所有點對外的邊, 這個動作我們稱之為縮點而在縮完一個有向圖中所有的強連通元件之後, 該有向圖便會成為一個有向無環圖 (DAG) 這個縮點的概念與技巧很重要, 不僅僅在 SCC 的部分會用到相關概念, 之後在其他地方也有可以能會用到 III. 演算法求 SCC 有許多經典的演算法, 在此我們介紹其中一種稱為 Kosaraju s Algorithm 的演算法首先, 先對原本的有向圖 G 0 作一次 DFS 走訪, 而在遍歷節點的過程使用之前曾經使用過的時間戳記 (Time Stamp), 對每個節點結束遍歷的時間建立時間戳記在第一次 DFS 走訪之後, 我們會得到一座森林 (Forest) F 0, 之後對於 F 0 中的每一棵樹 T i,t i 中的節點與連結那些節點的邊形成一個圖 G i, 對於這些 G i, 我們將其中的邊全部反向, 得到一個新的圖 G T i, 之 T 後再按照剛剛做的時間戳記由大到小的順序對 G i 進行 DFS 走訪, 然後又會得到一座新的森林 F i, 而對於 F i 中的每一棵樹, 樹中的節點連接那些節點的邊 ( 不一定在樹中 ) 即成一個強連通元件 (SCC) 10 頁

11 VI. 虛擬碼 Function Kosaraju s_algorithm ( Graph G, bool[ ] Visited, int[ ] Stamp, List SCC ) 1 Clear List SCC. 2 Set Visited[ ] all False. 3 For v, all vertices in G 4 If Visited[v]=False 5 Then start DFS G from v and make Time Stamp. 6 End If. 7 Let G T be G with reversed arcs. 8 Set Visited[ ] all False. 9 For u, with the reverse order of Time Stamp 10 If Visited[u]=False 11 Then Clear Current SCC. 12 start DFS G T from u and add the vertices into Current SCC which were visited Ext. 無向圖的雙連通元件 (Bi-Connected Component, BCC) 對於一個無向圖, 若在該無向圖中的每個點皆不為關鍵點 (Articulation Point), 則我們稱該無向圖雙連通 (Bi-Connected) 想一想? during the DFS. 13 add Current SCC to List SCC. 14 End If. More Extend 因此, 一個無向圖中的雙連通元件即為該無向圖中的一個極大雙連通子圖雙連通元件也具有一些獨特的性質, 對於一個雙連通元件中的兩個任意頂點, 都至少有兩條相異的路徑連接它們此外, 如果我們將一個無向圖的所有 BCC 全部收縮成點, 我們可以得到一棵樹, 而這棵樹的邊就是橋! 想一想, 要如何求出一個無向圖的 BCC? 這些性質又該怎麼應用呢? 為什麼求 SCC 的 Kosaraju s Algorithm 會是對的? 試著分析看看 Kosaraju s Algorithm 的時間複雜度為什麼將一個有向圖中的所有 SCC 縮成單一個點之後該圖就會成為一個 DAG? Do Exercise! UVa : TIOJ : 頁

Foreword: Graph Theory by CK63rd poao899 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from

Foreword: Graph Theory by CK63rd poao899 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from Foreword: Graph Theory 圖論, 算是演算法中比較獨立的一個支派, 起源為科科堡的七橋問題 (Seven Bridges of Königsberg) 數學中也有圖論, 在數學中它屬於離散數學它也可以說是研究一維的拓樸學的一門學派 (from Wiki) Definition: Graph 圖, 和一般我們看到的圖不一樣, 這裡的圖只有一堆點以及點與點的連接關係一張圖常用一個點集合跟一個邊或弧的集合表示