iT邦幫忙

鐵人檔案

2021 iThome 鐵人賽
回列表
Software Development

圖論與演算法之間的相互應用 系列

圖論的應用層面有兩種,其中一種應用是把一個題目使用圖論的模型來找出其特性,並且根據這些特性設計出演算法解決該問題。另一種應用則是建立圖論模型後,使用已知的工具(比方說線性規劃、矩陣相乘等等)來解決這些已知的圖論問題。在這 30 天之中,我想要介紹一些與圖論相關的演算法問題,並且描述一些範例程式。

鐵人鍊成 | 共 30 篇文章 | 5 人訂閱 訂閱系列文 RSS系列文
DAY 1

圖論與演算法之間的相互應用

Disclaimer: 今年大概撐不到連續 30 天...大概能寫多少就是多少吧 哈哈 1 圖論為什麼重要 1.1 圖論可以幫助你看清問題的本質 圖 (Gr...

2021-09-15 ‧ 由 卡卡恩 分享
DAY 2

圖的資料結構

3 圖的資料結構 今天來介紹我們儲存一張圖的時候,幾種常見的資料結構:相鄰矩陣(Adjacency Matrix)、鄰接鏈結串列(Adjacency Linke...

2021-09-16 ‧ 由 卡卡恩 分享
DAY 3

圖的走訪 - BFS 篇

4 圖的走訪 - BFS 篇 如果要好好地探索一張圖,最經典的方法莫過於深度優先搜索(Depth First Search) 以及廣度優先搜索(Breadth...

2021-09-17 ‧ 由 卡卡恩 分享
DAY 4

圖的走訪 - DFS 篇

5 圖的走訪 - DFS 篇 今天要跟大家分享另一種在圖上面遍歷所有節點的深度優先搜索 (Depth First Search, DFS)。深度優先搜索與廣度優...

2021-09-18 ‧ 由 卡卡恩 分享
DAY 5

拓樸排序問題

6 拓樸排序問題 現在讓我們來考慮另一個可以使用 DFS 來解決的經典範例:拓樸排序問題。想像有 N 件工作要完成,但是這些工作會有一定程度的相依性:我們可以用...

2021-09-19 ‧ 由 卡卡恩 分享
DAY 6

強連通元件

7 強連通元件 對於一個無向圖來說,如果我們把一個極大連通的子圖找出來(極大在這邊的定義是,無論再增加任何一個點,都沒辦法讓現在的子圖連通),那麼這個極大連通的...

2021-09-20 ‧ 由 卡卡恩 分享
DAY 7

圖的連通 (1)

8 割點、橋、雙連通元件 現在讓我們回到無向圖的演算法。給一張圖,要判斷這張圖是否為連通圖相當簡單:只要做一次 BFS 或 DFS 就可以了。但是,如果我們想知...

2021-09-21 ‧ 由 卡卡恩 分享
DAY 8

圖的連通 (2)

8.3 找出雙連通元件 圖 G 上面的雙連通元件 (Biconnected Component) 是指,一個極大的子圖,使得該子圖內不存在關節點。 經過一些有趣...

2021-09-22 ‧ 由 卡卡恩 分享
DAY 9

圖的連通 (3)

8.5 一些 Leetcode 例子 今天來拖點稿子,解幾題跟連通有關的題目吧。 Leetcode 1192. Critical Connections in...

2021-09-23 ‧ 由 卡卡恩 分享
DAY 10

圖的連通 (4)

9 三連通圖 如果一圖 G 有至少 k 個點、並且拿掉任何 k-1 個點以後都還是保持連通的,那麼我們就說這個圖是 k-點連通的。 9.1 判斷 k 連通圖的演...

2021-09-24 ‧ 由 卡卡恩 分享