1.2 圖的存儲與遍歷

1.2.1 鄰接矩陣與關聯矩陣

作為一種常見的數據結構，在計算機里圖的存儲表示方法有很多種，本節只著重介紹鄰接矩陣（Adjacency matrix）和關聯矩陣（Incidence matrix）這兩種方式。

設圖G=（V，E），在這里我們對邊重新進行了編號e1，e2，…，eM，如圖1-7所示。我們用鄰接矩陣A描述圖中頂點之間的關聯，A∈RN×N，其定義為：

圖1-7 圖G示例

用鄰接矩陣存儲圖的時候，我們需要一個一維數組表示頂點集合，需要一個二維數組表示鄰接矩陣。需要特別說明的是，由于在實際的圖數據中，鄰接矩陣往往會出現大量的0值，因此可以用稀疏矩陣的格式來存儲鄰接矩陣，這樣可以將鄰接矩陣的空間復雜度控制在O（M）的范圍內。圖1-8中a圖給出了圖G的鄰接矩陣存儲表示，通過該圖可以看出，無向圖的鄰接矩陣是沿主對角線對稱的，即Aij=Aji。

圖1-8 圖G的鄰接矩陣和關聯矩陣

除了鄰接矩陣外，我們有時也用關聯矩陣B∈RN×M來描述節點與邊之間的關聯，定義如下：

用關聯矩陣存儲圖的時候，我們需要兩個一維數組分別表示頂點集合和邊集合，需要一個二維數組表示關聯矩陣。同樣，關聯矩陣也可以用稀疏矩陣來存儲，這是因為B的任意一列僅有兩個非0值。圖1-8中b圖展示了用關聯矩陣來存儲圖的示例。