導讀

大家好，很高興又和大家見面啦！！！

在上一篇中，我們探討了圖的基本概念與術語，如頂點、邊、有向圖與無向圖的區別等。今天，我們將邁入實戰階段，深入解析圖的存儲結構——這一復雜關系的「翻譯器」。

如何將頂點與邊的抽象關系轉化為代碼可操作的數據？面對稀疏圖與稠密圖，存儲結構的選擇如何影響算法效率？本文將以鄰接矩陣法為起點，系統拆解圖的存儲邏輯：

• 從基礎定義到代碼實現，手把手構建鄰接矩陣模型
• 通過矩陣冪運算揭示「路徑數量」的隱藏規律（如$A^2$的奇妙意義）
• 無向圖對稱性、頂點度計算等特性的一一驗證

無論你是希望夯實基礎，還是渴望用數學工具優化算法，本文的圖文解析與場景化案例都將為你提供清晰的技術地圖。

一、圖的存儲結構

圖是由頂點集與邊集組成，因此我們想要完整的存儲圖的信息，那就需要完整的將圖中的頂點信息以及邊的信息給存儲下來。

根據不同圖的結構和算法，采用不同的存儲方式將對程序的效率產生相當大的影響，因此所選的存儲結構應適合于待求解的問題。

1.1 分類

在圖中我們將會介紹4種存儲結構：

• 鄰接矩陣法——通過一維數組與二維數組實現
• 鄰接表法——通過一維數組與鏈表實現
• 十字鏈表法——通過一維數組與鏈表實現
• 鄰接多重表——通過一維數組與鏈表實現

從實現方式的原理上來看，不管是哪種存儲結構，都是需要用到兩種存儲方式，這剛好對應了圖中的兩種元素——頂點集與邊集。

無需多言，相信大家應該已經猜到了，圖中對于頂點集的存儲，采用的就是一維數組，而對于邊集的存儲，則會有所區別。

接下來我們就來看一下圖的第一種存儲結構——鄰接矩陣法，它的實現原理究竟是怎么樣的。

二、鄰接矩陣法

鄰接矩陣法就是指用一維數組存儲圖中的頂點信息，用二維數組存儲圖中邊的信息（各頂點之間的鄰接關系）。

存儲頂點之間鄰接關系的二維數組稱為鄰接矩陣。

對于一個頂點數量為 $n$ 的圖 $G=(V,E)$ ，其鄰接矩陣 $A$ 是一個n階方陣，即 $n\times n$ 的矩陣。

2.1 鄰接矩陣

在鄰接矩陣中，我們可以用0和1來表示頂點之間的鄰接關系：

在鄰接矩陣中，行坐標和列坐標所代表的結點與一維數組中結點對應的下標一致，矩陣的值就是依附于該頂點的邊。

比如上圖中的邊 $(A,B)$ 對應到矩陣 $A$ 中，那就是點$a_{01}$ 與點 $a_{10}$ 這兩個點的值均為1；

如果上圖為無向圖，且我們要表示弧 $<A,B>$ ，那么對應的點就是點 $a_{01}=1$ 與點 $a_{10}=0$ ；

可以看到，鄰接矩陣既可以完整的存儲無向圖中邊的信息，也可以完整的存儲有向圖中弧的信息；

2.2 鄰接矩陣存儲網

當我們給圖的每條邊（弧）加上權值時，該圖就變成了一張網，那此時我們又應該如何通過鄰接矩陣存儲邊的信息呢？

對于網的存儲也不復雜，我們可以預設一個值如 $\infty$ 表示兩個頂點之間不存在邊。

比如當網中各條邊的權值都大于等于 $0$ 時，我們就可以預設 $?1$ 表示兩個頂點之間不存在邊；

在這個網中，存儲頂點信息的一維數組為：

0	1	2	3
a	b	c	d

當我們用鄰接矩陣來存儲邊的信息時，那對應的鄰接矩陣為：

	0	1	2	3
0	-1	1	3	4
1	1	-1	2	-1
2	3	2	-1	-1
3	4	-1	-1	-1

三、鄰接矩陣的存儲結構

鄰接矩陣的存儲結構的C語言表示為：

typedef char VertexType;
typedef int EdgeType;
#define MAXSIZE 5	// 一維數組最大長度
//鄰接矩陣法
typedef struct Adjacency_Matrix {VertexType Vertex[MAXSIZE];			// 一維數組存儲頂點信息EdgeType Edge[MAXSIZE][MAXSIZE];	// 二維數組存儲邊信息int len_ver;						// 當前頂點數量int len_edge;						// 當前邊數量
}AMGraph;								// 鄰接矩陣圖

經過前面的介紹，相信大家都應該是能夠理解這個存儲結構的，這里我就不再贅述；

四、算法評價

4.1 時間復雜度

在鄰接矩陣中，時間復雜度我們需要從頂點和邊兩個方面分別來評價：

• 當我們遍歷頂點時，就是在遍歷一個一維數組，那么遍歷頂點的時間復雜度為：$O(N)$
• 當我們遍歷邊時，就是在遍歷一個二維數組，那么遍歷邊的時間復雜度為：$O(N^2)$

因此我們遍歷整個圖的時間復雜度就應該為：$$T(n)=O(N)+O(N^2)=O(N^2)$$

4.2 空間復雜度

在鄰接矩陣法中，當我們為頂點數為 $n$ 的圖申請空間時，我們總共需要分別為頂點和邊申請空間：

• 頂點：需要申請 $n$ 個空間
• 邊：需要申請 $n^2$ 個空間

記錄頂點數和邊數的變量空間為一個常數空間，因此整個圖所對應的空間復雜度應該為：
$$T(n)=O(N)+O(N^2)+O(1)=O(N^2)$$

五、鄰接矩陣的特點

圖的鄰接矩陣表示法具有以下特點：

1. 無向圖的鄰接矩陣一定是一個對稱矩陣（并且唯一）。
2. 對于無向圖，鄰接矩陣的第i行（或第i列）非零元素（或非預設值元素如 $\infty$）的個數正好是頂點 $i$ 的度 $TD(v_i)$ 。
3. 對于有向圖，鄰接矩陣的第 $i$ 行非零元素（或非 $\infty$元素）的個數正好是頂點 $i$ 的出度 $OD(v_i)$ ；第 $i$ 列非零元素（或非 $\infty$ 元素）的個數正好是頂點 $i$ 的入度 $ID(v_i)$ 。
4. 用鄰接矩陣存圖，很容易確定圖中任意兩個頂點之間是否有邊相連。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。
5. 稠密圖（邊數較多的圖）適合采用鄰接矩陣的存儲表示。
6. 設圖 $G$ 的鄰接矩陣為 $A$ ，$A^n$ 的元素 $A_{[i][j]}^n$ 等于由頂點i到頂點j的長度為n的路徑的數目。

接下來我們來對這些特點逐個解析；

5.1 特點1解析

在鄰接矩陣中，我們采用的是n階方陣存儲的圖中邊的信息。

在無向圖中，當兩個頂點之間存在將其連通的邊時，從有向圖的角度來看，這條邊是一條雙向邊：

因此，在鄰接矩陣中的反映就一定是一個對稱矩陣。

在第三章——特殊矩陣的壓縮存儲中我們有詳細介紹過如何對像對稱矩陣這種特殊矩陣進行壓縮存儲，有需要的朋友可以點擊鏈接詳細閱讀。

5.2 特點2解析

在無向圖中，一個頂點的度就是依附于該頂點的邊的數量。

在鄰接矩陣中，每一行或者每一列都表示的是依附于該頂點的邊。

因此在第 $i$ 行或者第 $i$ 列中所有不為0，或者存儲網時，不為預設值（如 $\infty 、?1\dots \dots$）的點 $a_{ij}$ 或者 $a_{ji}$ 的數量之和就是該頂點 $i$ 的度 $TD(v_i)$ 。

這里需要注意，當我們計算了第 $i$ 行就不需要再計算第 $i$ 列，即行和列只需要取其一即可；

5.3 特點3解析

在有向圖中，鄰接矩陣中點 $a_{ij}$ 的行坐標 $i$ 表示的是弧尾，列坐標 $j$ 表示的是弧頭。這里我們用實例來說明：

在這個有向圖中，我們在存儲頂點 $a,b$ 時分別將頂點 $a$ 存儲在下標0，頂點 $b$ 存儲在下標1處，此時弧 $<a,b>$ 在鄰接矩陣中存儲時，代表該弧的點為 $a_{01}$ ，可以看到該點的橫坐標就是弧尾，縱坐標就是弧頭；

同理，弧 $<b,a>$ 所對應的鄰接矩陣中的點為 $a_{10}$，同樣的，橫坐標代表的是弧尾，縱坐標代表的是弧頭。

因此我們說在有向圖中，鄰接矩陣的第 $i$ 行非零元素的個數正好是頂點 $i$ 的出度 $OD(v_i)$;
第 $i$ 列非零元素的個數正好是頂點 $i$ 的入度 $ID(v_i)$

5.4 特點4解析

在鄰接矩陣中，我們要求邊的個數，實際上就是遍歷整個二維數組，而二維數組遍歷的時間復雜度為：$O(N^2)$ ，因此所耗費的時間代價是巨大的。

5.5 特點5解析

在鄰接矩陣中，我們在存儲邊的信息時，不管兩個之間是否存在邊，我們都為其申請了空間。

試想一下，如果在一個稀疏圖中，邊的數量為 $|E|<|V|lo{g}_2|V|$ ，也就是說，如果該圖中有4個頂點時，邊的數量不足8個，但是我們通過鄰接矩陣存儲時，申請了 $4^2=16$ 個空間。

此時我們對空間的實際利用率 $<50$ ，換句話說就是我們浪費的空間 $>50$ 。

這么一看，當我們用鄰接矩陣法存儲這種邊數量很少的圖時，會造成大量的空間浪費。

因此，鄰接矩陣法不適合存儲稀疏圖這種邊數量很少的圖，更加適合存儲稠密圖這種邊數量很多的圖。

5.6 特點6解析

要理解特點6，首先我們要清楚矩陣相乘的規則：

• 當且僅當一個矩陣的行數與另一個矩陣的列數相等時兩個矩陣才能相乘；
• 當矩陣 $A$ 為 $m\times n$ 的矩陣與矩陣 $B$ 為 $n\times m$ 的矩陣相乘時， 得到的矩陣 $C$ 中的元素 $c_{ij}$ 為：
  $$c_{ij}=\sum _{k=1}^n{a}_{ik}?b_{kj}$$

這里我們以有向圖 $G$ 為例進行說明：

在該有向圖中，頂點a對應的下標為0，頂點b對應的下標為1，其鄰接矩陣 $A$ 如下所示：

	0	1
0	0	1
1	0	0

對應的 $A^2$ 中的個元素為：
$$\begin{gathered} a_{00}^{\prime }=a_{00}\times a_{00}+a_{01}\times a_{10}=0+0=0 \\ {a}_{01}^{\prime }=a_{00}\times a_{01}+a_{01}\times a_{11}=0+0=0 \\ {a}_{10}^{\prime }=a_{10}\times a_{00}+a_{11}\times a_{10}=0+0=0 \\ {a}_{11}^{\prime }=a_{10}\times a_{01}+a_{11}\times a_{11}=0+0=0 \end{gathered}$$

以 $a_{00}^{\prime }$ 為例，該點表示的是頂點 $a^{\prime }$ 到頂點 $a^{\prime }$ 的長度為2的路徑的數目。

$$a_{00}^{\prime }=a_{00}\times a_{00}+a_{01}\times a_{10}=0+0=0$$

該公式中各項的含義為：

• $a_{00}$：頂點a到頂點a的弧
• $a_{01}$：頂點a到頂點b的弧
• $a_{10}$：頂點b到頂點a的弧

我們要想得到 $A^2$ 中 頂點 $a^{\prime }$ 到頂點 $a^{\prime }$ 的長度為2的路徑，那我們就有兩種方式從頂點 $a^{\prime }$ 到達頂點 $a^{\prime }$：

• 從頂點 $a^{\prime }$ 到達頂點 $a^{\prime }$，再從頂點 $a^{\prime }$ 到達頂點 $a^{\prime }$，此時路徑長度為2；
• 從從頂點 $a^{\prime }$ 到達頂點 $b^{\prime }$，再從頂點 $b^{\prime }$ 到達頂點 $a^{\prime }$，此時的路徑長度為2；

因此要得到長度為2的路徑，就必須存在弧 $<b,a>$ ，但是圖中不存在弧 $<b,a>$ 因此就不存在長度為2的路徑，此時長度為2的路徑的數量為0；

同理，我們也能夠驗證矩陣 $A^2$ 中的其它三個元素。

這個特點比較繞，如果實在不理解也沒關系，我們只做了解即可。

結語

鄰接矩陣法以矩陣的簡潔性，將圖的頂點與邊關系凝練為二維數組的0/1或權值，成為稠密圖存儲的經典選擇。通過本文的解析，我們可總結其核心價值：

1. 直觀性：矩陣行列直接對應頂點，快速判斷任意兩頂點是否鄰接（O(1)時間復雜度）；
2. 數學優勢：矩陣運算（如冪運算）可高效推導路徑數與連通性；
3. 場景適配：尤其適合邊數接近頂點數平方的稠密圖，避免空間浪費。

然而，鄰接矩陣的O(n2)空間復雜度也提醒我們：面對稀疏圖（如社交網絡），鄰接表等結構可能更具優勢。技術的選擇永遠服務于具體問題，理解不同存儲結構的特性，方能靈活應對千變萬化的算法需求。

拓展思考：若圖的頂點動態增減，鄰接矩陣如何優化？權值無窮大（∞）在代碼中應如何合理表示？歡迎在評論區探討你的見解，或繼續閱讀本系列的下一篇——《鄰接表：稀疏圖的存儲利器》。

---

🌟 如果本文對你有所幫助，歡迎：
? 關注[👉] 獲取更多算法與數據結構深度解析
? 點贊[👍] 支持原創內容
? 收藏[📁] 備查或分享給需要的伙伴
? 轉發[🔄] 讓知識傳播更遠

你的每一次互動，都是我們持續創作的動力！