圖論#
圖是最通用的非線性資料結構，用於表示物件之間的複雜關係。
本章內容#
- 圖的基礎：頂點、邊、度，以及存儲方式
- BFS 與 DFS：兩種基本的圖搜尋演算法
- 島嶼問題：連通分量的經典應用
- 拓撲排序：有向無環圖的線性排序
- 最短路徑：Dijkstra 演算法
圖的分類#
| 類型 | 特點 | 應用場景 |
|---|---|---|
| 無向圖 | 邊沒有方向 | 微信好友 |
| 有向圖 | 邊有方向 | 微博關注 |
| 帶權圖 | 邊有權重 | 地圖導航 |
| 有向無環圖 (DAG) | 無環的有向圖 | 任務調度 |
核心概念#
- 度 (Degree)：與頂點相連的邊數
- 有向圖分為入分支度（指向該點）和出分支度（從該點出發）
- 連通分量：無向圖中互相可達的頂點集合
- 環 (Cycle)：從某頂點出發可回到自身的路徑
學習路線：先掌握 BFS/DFS，再理解其在島嶼問題、拓撲排序中的應用。