C# 資料結構 - 圖的儲存結構：鄰接矩陣與鄰接表 (1)

8.2 圖的儲存結構

除儲存頂點資訊，還需儲存頂點間關係 (邊)。常用四種：鄰接矩陣、鄰接表、十字鏈表、鄰接多重表。

8.2.1 鄰接矩陣

n 階方陣 A[i,j]：1/true 表示邊存在，0/false/null 表示不存在。帶權圖直接存權值。

• 無向圖：矩陣對稱 A[i,j]=A[j,i]，第 i 列/行非零數 = 第 i 頂點度。存在資料冗餘。
• 有向圖：非對稱。第 i 列非零數 = 出度，第 i 行非零數 = 入度，度 = 出度+入度。

稀疏圖使用矩陣空間浪費嚴重，宜改用鄰接表。

8.2.2 鄰接表

順序分配 (頂點陣列) + 鏈式分配 (邊鏈表)。每頂點對應一表頭節點，鄰接頂點存於鏈表。

• 無向圖：雙向各存一邊，有冗餘
• 有向圖：出邊表 (尾頂點)、入邊表/逆鄰接表 (頭頂點)
• 帶權圖：表節點增加權值欄位