一.鄰接矩陣法存儲不帶權圖：

結點不帶權值：

1.左圖的無向圖中，A到B直達的有一條路，所以A行B列的值為1；

左圖的無向圖中，A到F沒有直達的路，所以A行F列的值為0；

結論：無向圖中采用鄰接矩陣法，0表示兩個頂點不鄰接，1表示兩個頂點鄰接，邊對應兩個1；

2.右圖的有向圖中，A到B直達的有一條路，所以A行B列的值為1，

B到A沒有直達的路，所以B行A列的值為0；

結論：有向圖中采用鄰接矩陣法，1表示有向邊(弧)，有向邊(弧)對應一個1；

3.上述圖片中的代碼，頂點表是要存入邊表的即表中存點；

4.頂點表也可以是其他類型，如整型，自定義數據類型；

5.int型表示邊占4個字節(4B)或者8個字節(8B)，用bool型或枚舉型變量表示邊則占1個字節(1B)；

6.注：表中的頂點是有下標(編號)的，這樣是為了在表中方便尋找兩個頂點的關系，如A的下標為0，B的下標為1，這樣比如在左圖的無向圖中只需要找第0行第1列就可以查找頂點A和B的關系；

7.如何求頂點的度(針對無向圖和有向圖)，入度和出度(只針對有向圖)：

• 無向圖：如上述圖片中的B結點，在B結點這一行中，有幾個非0元素就有幾個度，顯然A,E,F列為1即不為0，因此B的度為3(看B結點這一列也可以，結果一致)

結論：第i個結點的度=第i行(第i列)的非零元素個數，時間復雜度為O(n)或者O(|v|)，v是頂點數

• 有向圖：某個結點的出度的個數就是該結點所在行(不能是列)中非0元素的個數，如A結點的出度為1；

  某個結點的入度的個數就是該結點所在列(不能是行)中非0元素的個數，如A結點的入度為2；

  有向圖中某個結點的度等于該結點入度的個數加出度的個數，時間復雜度為O(n)或者O(|v|)，v是頂點

  數，因此A結點的度為3；

---

二.鄰接矩陣法存儲帶權圖(網)：

1.帶權圖中存儲的就是權值，比如左圖的無向圖A直達B的權值為5，那么A行B列的值為5，

左圖的無向圖B直達C不存在權值即B直達不了C，那么B行C列的值可以用無窮來表示；

2.權值的類型可以是整型，浮點型或者自定義數據類型等；

3.有時也會把自己指向自己的權值設為0，如A到A的權值為0；

4.鄰接矩陣法存儲帶權圖(網)中結點到結點的權值如果為0或者是無窮，那么表示與之對應的兩個結點之間不存在邊：

---

三.鄰接矩陣法的性能分析：

1.如果圖中有n個頂點(結點)，那么存儲該圖的頂點就需要一個一維數組，此時存儲頂點的空間復雜度為O(n),

還需要定義一個n * n的二維數組來存儲和這些頂點相關的邊的信息，所以存儲邊的空間復雜度為O(n * n)，

所以總共空間復雜度為O(n)+O(n * n)，等價于O(n * n)，

結論：鄰接矩陣法的空間復雜度為O(n * n)或O(|v| * |v|)，v為頂點數-->只和頂點數有關，和實際的邊數無關，導致的弊端就是如果頂點很多，但邊比較少，就會使得存儲邊的二維數組空間浪費，因此鄰接矩陣法適用于存儲稠密圖即邊多的圖；

---

四.鄰接矩陣法的性質：討論不帶權值的圖即矩陣元素只有0，1

0表示從一個頂點到另一個頂點沒有路徑，1表示從一個頂點到另一個頂點有路徑，

A到B到D的長度為2，符合要找的路徑長度，所以算了進去；

注：簡單圖中自己到自己的權值為0；

上述圖片中右下角的矩陣中的值表示的是頂點到頂點長度為2的路有幾條，如A行C列中頂點A到頂點C長度為2的路有1條；

---

五.總結：

鄰接矩陣法的空間復雜度為O(n*n)，n為頂點數，由此可看出鄰接矩陣法的空間復雜度較高，不適合存儲稀疏圖，如果使用鄰接矩陣法存儲稀疏圖，會造成大量的空間浪費。

---