圖的表示法

6.1 鄰接矩陣：原理、優缺點.

鄰接矩陣 是一種將圖表現為大小為 n x n 的方陣的方法，這裡 n 表示 圖中的頂點數。矩陣的元素指示頂點之間是否存在邊：

• 如果頂點 i 和 j 之間存在邊，則元素 A[i][j] = 1（或者是邊的權重，如果圖是有權圖）。
• 如果沒有邊，則 A[i][j] = 0.

示例:

對於具有頂點 A, B, C 和邊 (A, B), (B, C), (C, A) 的圖，鄰接矩陣將是：

如果所有頂點都相互連接，則鄰接矩陣看起來會是這樣：

優點：

• 簡單: 易於理解和實現。
• 快速訪問: 檢查兩個 頂點之間的邊需耗時 O(1)。
• 適合密集圖: 對於具有大量邊的圖很有效。

缺點：

• 高記憶體開銷: 需要 O(n^2) 的記憶體，即使圖中含少量邊（稀疏圖）。
• 對稀疏圖效率低: 當頂點數量大而邊數少時，矩陣的大多數元素將為零，導致記憶體使用效率低。

6.2 鄰接表：原理、優缺點。

鄰接表 是將圖表現為列表數組的方法。數組的每個元素對應圖中的一個頂點，並包含與其相鄰的所有頂點的列表。

示例:

對於具有頂點 A, B, C 和邊 (A, B), (B, C), (C, A) 的圖，鄰接表將是：

如果所有頂點都相互連接，則鄰接表看起來會是這樣：

優點：

• 有效記憶體使用: 需要 O(V + E) 記憶體，其中 V 是頂點數量，E 是邊數量，適合稀疏圖。
• 易於遍歷: 方便執行圖遍歷操作（例如，廣度優先搜索或深度優先搜索）。

缺點：

• 較複雜的訪問: 檢查兩個頂點之間的邊需耗時 O(k)，其中 k 是頂點的鄰居數量。
• 結構不太明顯: 相較於鄰接矩陣較難實現和理解。

6.3 不同圖表示方法的比較.

我們來比較不同的圖表示方法。

1. 鄰接矩陣：

• 簡單: 易於理解和實現。
• 記憶體: 需要 O(n^2) 記憶體，對稀疏圖可能效率低。
• 快速訪問: 檢查是否存在邊需耗時 O(1)。
• 適合: 適合具有大量邊的密集圖。

2. 鄰接表：

• 簡單: 相較於鄰接矩陣不太直觀，但也易於理解。
• 記憶體: 需要 O(V + E) 記憶體，對稀疏圖更有效。
• 訪問速度: 檢查是否存在邊需耗時 O(k)，其中 k 是頂點的鄰居數量。
• 適合: 適合具有少量邊的稀疏圖。

比較：

鄰接矩陣 更適合於密集圖，大多數頂點相互連接，因為它提供快速訪問邊的信息且易於實現。

鄰接表 在於稀疏圖更優選，當邊的數量遠少於可能的頂點對數量時。它們提供有效的記憶體使用並方便圖的遍歷操作。