1．圖的鄰接矩陣表示法
??? 　在圖的鄰接矩陣表示法中：
　① 用鄰接矩陣表示頂點(diǎn)間的相鄰關(guān)系
　② 用一個(gè)順序表來(lái)存儲(chǔ)頂點(diǎn)信息

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

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

3．網(wǎng)（帶權(quán)值的圖）的鄰接矩陣
??? 　若G是網(wǎng)絡(luò)，則鄰接矩陣可定義為：
????? ??
??

? 其中：
????? w _ij 表示邊上的權(quán)值；
????? ∞表示一個(gè)計(jì)算機(jī)允許的、大于所有邊上權(quán)值的數(shù)。
【例】下面(a)是一個(gè)帶權(quán)圖，（b）是對(duì)應(yīng)的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)

??????? （a）帶權(quán)圖 ??????????????????????? （b）鄰接矩陣

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

圖的鄰接矩陣