圖（Graph） 是一種非線性數據結構，用于表示對象之間的關系。圖由 頂點（Vertex） 和 邊（Edge） 組成，其中頂點表示對象，邊表示對象之間的關系。圖廣泛應用于計算機科學、數學、物理、生物、社交網絡等領域。

1. 圖的基本概念

• 頂點（Vertex）：也稱為節點（Node），表示圖中的對象。例如，在社交網絡中，頂點可以表示人。
• 邊（Edge）：表示頂點之間的關系。例如，在社交網絡中，邊可以表示兩個人是朋友。
• 有向圖（Directed Graph）：邊有方向，表示從一個頂點指向另一個頂點。例如，A → B 表示從 A 到 B 的關系。
• 無向圖（Undirected Graph）：邊沒有方向，表示兩個頂點之間的雙向關系。例如，A — B 表示 A 和 B 是相互關聯的。
• 權重（Weight）：邊可以帶有權重，表示關系的強度或成本。例如，在地圖中，邊的權重可以表示兩個城市之間的距離。

2. 圖的分類

按邊是否有方向

• 有向圖（Directed Graph）：
  • 邊有方向，表示為 $(u,v)$，表示從頂點 $u$ 指向頂點 $v$。
  • 示例：網頁鏈接（A 頁面鏈接到 B 頁面）。
• 無向圖（Undirected Graph）：
  • 邊沒有方向，表示為 $u,v$，表示頂點 $u$ 和頂點 $v$ 之間的雙向關系。
  • 示例：社交網絡（A 和 B 是朋友）。

按邊是否有權重

• 帶權圖（Weighted Graph）：
  • 邊帶有權重，表示關系的強度或成本。
  • 示例：地圖（邊的權重表示兩個城市之間的距離）。
• 無權圖（Unweighted Graph）：
  • 邊沒有權重，只表示頂點之間是否存在關系。
  • 示例：社交網絡（只表示兩個人是否是朋友）。

按圖中是否有環

• 有環圖（Cyclic Graph）：
  • 圖中存在至少一個環（從一個頂點出發，經過若干邊后回到自身）。
  • 示例：$A\to B\to C\to A$。
• 無環圖（Acyclic Graph）：
  • 圖中不存在任何環。
  • 示例：樹（Tree） 是一種特殊的無環圖。

按圖的連通性

• 連通圖（Connected Graph）：
  • 無向圖中，任意兩個頂點之間都存在路徑。
  • 示例：完全連通的社交網絡。
• 非連通圖（Disconnected Graph）：
  • 無向圖中，存在至少兩個頂點之間沒有路徑。
  • 示例：孤立的社交網絡群體。
• 強連通圖（Strongly Connected Graph）：
  • 有向圖中，任意兩個頂點之間都存在雙向路徑。
  • 示例：完全連通的網頁鏈接圖。

3. 圖的表示方法

圖可以通過多種方式表示，常見的有：

• 鄰接矩陣（Adjacency Matrix）：
  • 使用二維數組表示頂點之間的連接關系。
  • 適合稠密圖。
• 鄰接表（Adjacency List）：
  • 使用數組或鏈表存儲每個頂點的鄰接頂點。
  • 適合稀疏圖。
• 邊列表（Edge List）：
  • 直接存儲所有邊的列表。
  • 適合某些特定算法（如 Kruskal 算法）。

4. 圖的算法

圖論中有許多經典算法，例如：

• 遍歷算法：
  • 深度優先搜索（DFS）：用于遍歷或搜索圖。
  • 廣度優先搜索（BFS）：用于最短路徑問題。
• 最短路徑算法：
  • Dijkstra 算法：用于帶權圖的最短路徑。
  • Floyd-Warshall 算法：用于所有頂點對之間的最短路徑。
• 最小生成樹算法：
  • Kruskal 算法：基于邊列表的最小生成樹。
  • Prim 算法：基于頂點的最小生成樹。
• 拓撲排序：
  • 用于 有向無環圖（DAG） 的排序。
• 強連通分量：
  • Kosaraju 算法：用于查找有向圖的強連通分量。

我將在接下來幾篇文章中和大家分享相關的題目。歡迎大家點贊收藏，持續關注！