1．圖的鄰接矩陣表示法
??? 　在圖的鄰接矩陣表示法中：
　① 用鄰接矩陣表示頂點間的相鄰關系
　② 用一個順序表來存儲頂點信息

2．圖的鄰接矩陣(Adacency Matrix)
??? 　設G=(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質的n階方陣：
?????

??
【例】下圖中無向圖G ₅ 和有向圖G ₆ 的鄰接矩陣分別為A _l 和A ₂ 。
??? 從圖的鄰接矩陣表示法中可以得到如下結論： 　　（1）對于n個頂點的無向圖，有A（i，i）=0，1≤i≤n。
　　（2）無向圖的鄰接矩陣是對稱的，即A（i，j）=A（j，i），1≤i≤n，1≤j≤n。
　　（3）有向圖的鄰接矩陣不一定對稱的。因此用鄰接矩陣來表示一個具有n個頂點的有向圖時需要n ² 個單位來存儲鄰接矩陣；對有n個頂點的無向圖則需存入上（下）三角形，故只需n（n+1）/2個單位。
　　（4）無向圖的鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的度TD（v _i ）。
　　（5）有向圖的鄰接矩陣的第i行（或第i列）非零元素的個數正好是第i個頂點的出度OD（v _i
）[或入度ID（v _i ）]。

3．網（帶權值的圖）的鄰接矩陣
??? 　若G是網絡，則鄰接矩陣可定義為：
????? ??
??

? 其中：
????? w _ij 表示邊上的權值；
????? ∞表示一個計算機允許的、大于所有邊上權值的數。
【例】下面(a)是一個帶權圖，（b）是對應的鄰接矩陣的存儲結構

??????? （a）帶權圖 ??????????????????????? （b）鄰接矩陣

4．鄰接矩陣的圖類
const int MaxVertices=10;
const int MaxWeight=32767;
class AdjMWGraph
? { private:
?? int Vertices[10];? ? ? ?? ? //頂點信息的數組
?? int Edge[MaxVertices][MaxVertices]; ? ? ? ? //邊的權值信息的矩陣
? ? int numE;? ? ? ? ? ? //當前的邊數
? ? int numV;? ? ? ? ? ? //當前的頂點數
? ? public: ………;? ? ? ? ? //公有函數
? ? private: ………;? ? ? ? ? //私有函數
? }
? 注意：
　??? ① 在簡單應用中，可直接用二維數組作為圖的鄰接矩陣（頂點表及頂點數等均可省略）。
??? 　② 當鄰接矩陣中的元素僅表示相應的邊是否存在時，EdgeTyPe可定義為值為0和1的枚舉類型。
??? 　③ 無向圖的鄰接矩陣是對稱矩陣，對規模特大的鄰接矩陣可壓縮存儲。
??? 　④ 鄰接矩陣表示法的空間復雜度S(n)=0(n ² )。

圖的鄰接矩陣