????????鄰接矩陣的圖的表示方法里最簡單的一個(gè)，在它的存儲結(jié)構(gòu)就是由一個(gè)存放頂點(diǎn)的數(shù)組和一個(gè)二維數(shù)組組成。圖的表示方法也很簡單，如果兩個(gè)頂點(diǎn)間有邊（或?。S數(shù)組對應(yīng)位置的值就設(shè)為1，反之則為零。

????????這樣的話，對于無向圖，如果想要求得一個(gè)頂點(diǎn)的度，只需遍歷求和其對應(yīng)行或列的非零元素，其復(fù)雜的是O(n)。類似地，對于有向圖，若要求出度，則遍歷頂點(diǎn)對應(yīng)行，求入度則遍歷頂點(diǎn)對應(yīng)列。度則是入度和出度的和。

????????而對于帶權(quán)圖的存儲結(jié)構(gòu)，只需給二維數(shù)組的對應(yīng)節(jié)點(diǎn)賦值為對應(yīng)的權(quán)值，其余無邊的節(jié)點(diǎn)設(shè)為無窮即可，對于無窮的定義可以通過宏定義一個(gè)最大值來將其當(dāng)作無窮。

????????了解完鄰接矩陣的定義之后，下面開始分析其性能。首先，其空間復(fù)雜度為O（|v|^2）,適合存儲稠密圖。

????????雖然鄰接矩陣如此簡單，但是其仍有許多優(yōu)良的性質(zhì)可以方便我們計(jì)算。若矩陣元素為0/1的鄰接矩陣為A，那么A^n[i][j]就是從i頂點(diǎn)到j(luò)頂點(diǎn)的長度為n的路徑的數(shù)目。多么好的性質(zhì)！對于這個(gè)性質(zhì)的理解，我們可以先從A^2開始理解。比如，有ABCD四個(gè)點(diǎn)，從A到D長度為2的路徑可能有AA-AD,AB-BD，AC-CD,AD-DD，如果AB-BD路徑存在那么A-B和B-D對應(yīng)的鄰接矩陣的值均為1，其相乘也為1，而矩陣矩陣的乘法求得的A^2[1][4]恰好就是以上對應(yīng)的點(diǎn)相乘再相加，自然就是路徑數(shù)目，A^n也可以以此類推。

????????鄰接表的表示方法和樹的孩子表示法類似，即可用一個(gè)一維數(shù)組存儲結(jié)點(diǎn)的信息，用鏈表存放一個(gè)和結(jié)點(diǎn)相連的邊。而有向圖和無向圖的區(qū)別在于，無向圖每個(gè)邊都存放了兩遍，有向圖只存放結(jié)點(diǎn)向外的邊，每條邊只存放一邊，有向圖的入度也因此不好計(jì)算。