圖的鄰接矩陣與鄰接表表示細則一、概述

圖的鄰接矩陣和鄰接表是兩種常見的圖數(shù)據(jù)結(jié)構(gòu)表示方法，用于存儲圖中的節(jié)點（頂點）和邊（?。┬畔?。這兩種表示方法各有優(yōu)缺點，適用于不同的應(yīng)用場景。本細則將詳細說明圖的鄰接矩陣和鄰接表的定義、表示方法、優(yōu)缺點及適用場景。

二、鄰接矩陣表示

鄰接矩陣是一種使用二維數(shù)組來表示圖的結(jié)構(gòu)，其中矩陣的行和列分別代表圖的頂點，矩陣中的元素表示頂點之間的邊關(guān)系。

（一）定義

1.矩陣表示：用\(n\timesn\)的矩陣\(A\)表示包含\(n\)個頂點的圖，其中\(zhòng)(A[i][j]\)表示頂點\(i\)和頂點\(j\)之間的邊關(guān)系。

2.無向圖：若\(A[i][j]=1\)，表示頂點\(i\)和頂點\(j\)之間存在無向邊；若\(A[i][j]=0\)，表示不存在邊。

3.有向圖：若\(A[i][j]=1\)，表示從頂點\(i\)到頂點\(j\)存在一條有向邊；若\(A[i][j]=0\)，表示不存在邊。

（二）表示方法

1.初始化矩陣：創(chuàng)建一個\(n\timesn\)的矩陣，所有元素初始化為0或無窮大（表示無邊）。

2.填充矩陣：根據(jù)圖的邊信息，將對應(yīng)的矩陣元素設(shè)置為1或其他表示邊的值。

3.示例：

-無向圖：

\(A=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}\)

-有向圖：

\(A=\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\end{pmatrix}\)

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間復(fù)雜度：對于稀疏圖，鄰接矩陣存儲效率較低，但實現(xiàn)簡單。

(2)查詢效率：快速判斷兩個頂點之間是否存在邊，時間復(fù)雜度為\(O(1)\)。

2.缺點：

(1)空間浪費：對于稀疏圖，矩陣中大量元素為0，造成空間浪費。

(2)邊數(shù)限制：需要預(yù)分配固定大小的矩陣，不適合動態(tài)變化的圖。

三、鄰接表表示

鄰接表是一種使用鏈表或數(shù)組來表示圖的結(jié)構(gòu)，其中每個頂點對應(yīng)一個鏈表，鏈表中的節(jié)點表示與該頂點相鄰的頂點。

（一）定義

1.結(jié)構(gòu)：用數(shù)組\(G\)表示圖，其中\(zhòng)(G[i]\)是一個鏈表，鏈表中的節(jié)點表示頂點\(i\)的鄰接頂點。

2.無向圖：鏈表中的節(jié)點表示與頂點\(i\)相鄰的頂點\(j\)。

3.有向圖：鏈表中的節(jié)點表示從頂點\(i\)出發(fā)的邊指向的頂點\(j\)。

（二）表示方法

1.初始化：創(chuàng)建一個數(shù)組，每個元素初始化為空鏈表。

2.添加邊：

(1)無向圖：在頂點\(i\)和\(j\)的鏈表中分別添加節(jié)點。

(2)有向圖：在頂點\(i\)的鏈表中添加指向頂點\(j\)的節(jié)點。

3.示例：

-無向圖：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

-有向圖：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間效率：對于稀疏圖，鄰接表更節(jié)省空間，只存儲實際存在的邊。

(2)邊數(shù)靈活性：可以動態(tài)添加或刪除邊，適合動態(tài)變化的圖。

2.缺點：

(1)查詢效率：判斷兩個頂點之間是否存在邊，需要遍歷鏈表，時間復(fù)雜度為\(O(d)\)，其中\(zhòng)(d\)是頂點的度數(shù)。

(2)實現(xiàn)復(fù)雜度：鏈表操作相對矩陣操作更復(fù)雜。

四、適用場景

1.鄰接矩陣：

(1)稠密圖：邊數(shù)接近頂點平方，鄰接矩陣空間效率較高。

(2)需要頻繁查詢邊關(guān)系：快速判斷頂點間是否存在邊。

2.鄰接表：

(1)稀疏圖：邊數(shù)遠小于頂點平方，鄰接表空間效率更高。

(2)動態(tài)變化的圖：方便添加或刪除邊。

一、概述

圖的鄰接矩陣和鄰接表是兩種常見的圖數(shù)據(jù)結(jié)構(gòu)表示方法，用于存儲圖中的節(jié)點（頂點）和邊（?。┬畔ⅰ＿@兩種表示方法各有優(yōu)缺點，適用于不同的應(yīng)用場景。本細則將詳細說明圖的鄰接矩陣和鄰接表的定義、表示方法、優(yōu)缺點及適用場景，并探討如何在實際應(yīng)用中選擇合適的表示方法。通過本細則的學(xué)習(xí)，讀者能夠掌握這兩種圖表示方法的實現(xiàn)細節(jié)，并能夠在具體問題中靈活運用。

二、鄰接矩陣表示

鄰接矩陣是一種使用二維數(shù)組來表示圖的結(jié)構(gòu)，其中矩陣的行和列分別代表圖的頂點，矩陣中的元素表示頂點之間的邊關(guān)系。

（一）定義

1.矩陣表示：用\(n\timesn\)的矩陣\(A\)表示包含\(n\)個頂點的圖，其中\(zhòng)(A[i][j]\)表示頂點\(i\)和頂點\(j\)之間的邊關(guān)系。

2.無向圖：若\(A[i][j]=1\)，表示頂點\(i\)和頂點\(j\)之間存在無向邊；若\(A[i][j]=0\)，表示不存在邊。

3.有向圖：若\(A[i][j]=1\)，表示從頂點\(i\)到頂點\(j\)存在一條有向邊；若\(A[i][j]=0\)，表示不存在邊。

4.權(quán)重表示：對于帶權(quán)圖，\(A[i][j]\)可以表示頂點\(i\)和頂點\(j\)之間的邊的權(quán)重，權(quán)重值可以是正數(shù)、負數(shù)或無窮大（表示無邊）。

（二）表示方法

1.初始化矩陣：創(chuàng)建一個\(n\timesn\)的矩陣，所有元素初始化為0或無窮大（表示無邊）。具體步驟如下：

(1)確定頂點數(shù)量\(n\)，創(chuàng)建一個\(n\timesn\)的矩陣\(A\)。

(2)遍歷矩陣的每個元素\(A[i][j]\)，將所有元素初始化為0或無窮大。

2.填充矩陣：根據(jù)圖的邊信息，將對應(yīng)的矩陣元素設(shè)置為1或其他表示邊的值。具體步驟如下：

(1)遍歷圖的每條邊，假設(shè)邊的起點為\(i\)，終點為\(j\)，權(quán)重為\(w\)。

(2)對于無向圖，將\(A[i][j]\)和\(A[j][i]\)都設(shè)置為1或權(quán)重\(w\)。

(3)對于有向圖，將\(A[i][j]\)設(shè)置為1或權(quán)重\(w\)。

(4)對于帶權(quán)圖，將\(A[i][j]\)設(shè)置為權(quán)重\(w\)。

3.示例：

-無向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(1,4),(2,3),(3,4)\)，鄰接矩陣表示為：

\(A=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}\)

-有向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(2,3),(3,4)\)，鄰接矩陣表示為：

\(A=\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\end{pmatrix}\)

-帶權(quán)圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2,5),(1,4,3),(2,3,2),(3,4,4)\)，鄰接矩陣表示為：

\(A=\begin{pmatrix}0&5&\infty&3\\\infty&0&2&\infty\\\infty&\infty&0&4\\\infty&\infty&\infty&0\end{pmatrix}\)

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間復(fù)雜度：對于稠密圖，鄰接矩陣存儲效率較高，時間復(fù)雜度為\(O(n^2)\)。

(2)查詢效率：快速判斷兩個頂點之間是否存在邊，時間復(fù)雜度為\(O(1)\)。

(3)易于實現(xiàn)：鄰接矩陣的實現(xiàn)相對簡單，適合用于靜態(tài)圖。

2.缺點：

(1)空間浪費：對于稀疏圖，矩陣中大量元素為0，造成空間浪費。

(2)邊數(shù)限制：需要預(yù)分配固定大小的矩陣，不適合動態(tài)變化的圖。

(3)度數(shù)計算：計算頂點的度數(shù)需要遍歷整個行或列，時間復(fù)雜度為\(O(n)\)。

三、鄰接表表示

鄰接表是一種使用鏈表或數(shù)組來表示圖的結(jié)構(gòu)，其中每個頂點對應(yīng)一個鏈表，鏈表中的節(jié)點表示與該頂點相鄰的頂點。

（一）定義

1.結(jié)構(gòu)：用數(shù)組\(G\)表示圖，其中\(zhòng)(G[i]\)是一個鏈表，鏈表中的節(jié)點表示頂點\(i\)的鄰接頂點。

2.無向圖：鏈表中的節(jié)點表示與頂點\(i\)相鄰的頂點\(j\)。

3.有向圖：鏈表中的節(jié)點表示從頂點\(i\)出發(fā)的邊指向的頂點\(j\)。

4.帶權(quán)圖：鏈表中的節(jié)點可以包含頂點編號和邊的權(quán)重。

（二）表示方法

1.初始化：創(chuàng)建一個數(shù)組，每個元素初始化為空鏈表。具體步驟如下：

(1)確定頂點數(shù)量\(n\)，創(chuàng)建一個大小為\(n\)的數(shù)組\(G\)。

(2)遍歷數(shù)組\(G\)的每個元素，將所有元素初始化為空鏈表。

2.添加邊：

(1)無向圖：在頂點\(i\)和\(j\)的鏈表中分別添加節(jié)點。具體步驟如下：

-創(chuàng)建一個節(jié)點，節(jié)點數(shù)據(jù)為\(j\)。

-將該節(jié)點插入到頂點\(i\)的鏈表頭部。

-將該節(jié)點插入到頂點\(j\)的鏈表頭部。

(2)有向圖：在頂點\(i\)的鏈表中添加指向頂點\(j\)的節(jié)點。具體步驟如下：

-創(chuàng)建一個節(jié)點，節(jié)點數(shù)據(jù)為\(j\)。

-將該節(jié)點插入到頂點\(i\)的鏈表頭部。

(3)帶權(quán)圖：在頂點\(i\)的鏈表中添加指向頂點\(j\)的節(jié)點，節(jié)點數(shù)據(jù)為\((j,w)\)，其中\(zhòng)(w\)為邊的權(quán)重。具體步驟如下：

-創(chuàng)建一個節(jié)點，節(jié)點數(shù)據(jù)為\((j,w)\)。

-將該節(jié)點插入到頂點\(i\)的鏈表頭部。

3.示例：

-無向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(1,4),(2,3),(3,4)\)，鄰接表表示為：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

其中：

-鏈表1：節(jié)點(2,0),節(jié)點(4,0)

-鏈表2：節(jié)點(1,0),節(jié)點(3,0)

-鏈表3：節(jié)點(2,0),節(jié)點(4,0)

-鏈表4：節(jié)點(1,0),節(jié)點(3,0)

-有向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(2,3),(3,4)\)，鄰接表表示為：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

其中：

-鏈表1：節(jié)點(2,0)

-鏈表2：節(jié)點(3,0)

-鏈表3：節(jié)點(4,0)

-鏈表4：節(jié)點為空

-帶權(quán)圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2,5),(1,4,3),(2,3,2),(3,4,4)\)，鄰接表表示為：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

其中：

-鏈表1：節(jié)點(2,5),節(jié)點(4,3)

-鏈表2：節(jié)點(3,2)

-鏈表3：節(jié)點(4,4)

-鏈表4：節(jié)點為空

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間效率：對于稀疏圖，鄰接表更節(jié)省空間，只存儲實際存在的邊。

(2)邊數(shù)靈活性：可以動態(tài)添加或刪除邊，適合動態(tài)變化的圖。

(3)度數(shù)計算：計算頂點的度數(shù)只需要遍歷該頂點的鏈表，時間復(fù)雜度為\(O(d)\)，其中\(zhòng)(d\)是頂點的度數(shù)。

2.缺點：

(1)查詢效率：判斷兩個頂點之間是否存在邊，需要遍歷鏈表，時間復(fù)雜度為\(O(d)\)，其中\(zhòng)(d\)是頂點的度數(shù)。

(2)實現(xiàn)復(fù)雜度：鏈表操作相對矩陣操作更復(fù)雜。

四、適用場景

1.鄰接矩陣：

(1)稠密圖：邊數(shù)接近頂點平方，鄰接矩陣空間效率較高。

(2)需要頻繁查詢邊關(guān)系：快速判斷頂點間是否存在邊。

(3)靜態(tài)圖：鄰接矩陣的實現(xiàn)簡單，適合用于靜態(tài)圖。

2.鄰接表：

(1)稀疏圖：邊數(shù)遠小于頂點平方，鄰接表空間效率更高。

(2)動態(tài)變化的圖：方便添加或刪除邊。

(3)需要頻繁添加或刪除邊：鄰接表的操作更靈活。

五、選擇方法的指導(dǎo)原則

1.圖的密度：

(1)稠密圖：選擇鄰接矩陣，因為鄰接矩陣的空間效率更高。

(2)稀疏圖：選擇鄰接表，因為鄰接表的空間效率更高。

2.操作類型：

(1)頻繁查詢邊關(guān)系：選擇鄰接矩陣，因為查詢時間復(fù)雜度為\(O(1)\)。

(2)頻繁添加或刪除邊：選擇鄰接表，因為操作時間復(fù)雜度較低。

3.圖的變化頻率：

(1)靜態(tài)圖：選擇鄰接矩陣，因為實現(xiàn)簡單。

(2)動態(tài)變化的圖：選擇鄰接表，因為操作更靈活。

4.度數(shù)計算需求：

(1)需要頻繁計算頂點的度數(shù)：選擇鄰接表，因為計算時間復(fù)雜度較低。

六、總結(jié)

1.鄰接矩陣和鄰接表是兩種常見的圖表示方法，各有優(yōu)缺點。

2.選擇合適的表示方法需要考慮圖的密度、操作類型、圖的變化頻率和度數(shù)計算需求。

3.通過合理選擇表示方法，可以提高圖算法的效率。

一、概述

圖的鄰接矩陣和鄰接表是兩種常見的圖數(shù)據(jù)結(jié)構(gòu)表示方法，用于存儲圖中的節(jié)點（頂點）和邊（?。┬畔?。這兩種表示方法各有優(yōu)缺點，適用于不同的應(yīng)用場景。本細則將詳細說明圖的鄰接矩陣和鄰接表的定義、表示方法、優(yōu)缺點及適用場景。

二、鄰接矩陣表示

鄰接矩陣是一種使用二維數(shù)組來表示圖的結(jié)構(gòu)，其中矩陣的行和列分別代表圖的頂點，矩陣中的元素表示頂點之間的邊關(guān)系。

（一）定義

1.矩陣表示：用\(n\timesn\)的矩陣\(A\)表示包含\(n\)個頂點的圖，其中\(zhòng)(A[i][j]\)表示頂點\(i\)和頂點\(j\)之間的邊關(guān)系。

2.無向圖：若\(A[i][j]=1\)，表示頂點\(i\)和頂點\(j\)之間存在無向邊；若\(A[i][j]=0\)，表示不存在邊。

3.有向圖：若\(A[i][j]=1\)，表示從頂點\(i\)到頂點\(j\)存在一條有向邊；若\(A[i][j]=0\)，表示不存在邊。

（二）表示方法

1.初始化矩陣：創(chuàng)建一個\(n\timesn\)的矩陣，所有元素初始化為0或無窮大（表示無邊）。

2.填充矩陣：根據(jù)圖的邊信息，將對應(yīng)的矩陣元素設(shè)置為1或其他表示邊的值。

3.示例：

-無向圖：

\(A=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}\)

-有向圖：

\(A=\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\end{pmatrix}\)

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間復(fù)雜度：對于稀疏圖，鄰接矩陣存儲效率較低，但實現(xiàn)簡單。

(2)查詢效率：快速判斷兩個頂點之間是否存在邊，時間復(fù)雜度為\(O(1)\)。

2.缺點：

(1)空間浪費：對于稀疏圖，矩陣中大量元素為0，造成空間浪費。

(2)邊數(shù)限制：需要預(yù)分配固定大小的矩陣，不適合動態(tài)變化的圖。

三、鄰接表表示

鄰接表是一種使用鏈表或數(shù)組來表示圖的結(jié)構(gòu)，其中每個頂點對應(yīng)一個鏈表，鏈表中的節(jié)點表示與該頂點相鄰的頂點。

（一）定義

1.結(jié)構(gòu)：用數(shù)組\(G\)表示圖，其中\(zhòng)(G[i]\)是一個鏈表，鏈表中的節(jié)點表示頂點\(i\)的鄰接頂點。

2.無向圖：鏈表中的節(jié)點表示與頂點\(i\)相鄰的頂點\(j\)。

3.有向圖：鏈表中的節(jié)點表示從頂點\(i\)出發(fā)的邊指向的頂點\(j\)。

（二）表示方法

1.初始化：創(chuàng)建一個數(shù)組，每個元素初始化為空鏈表。

2.添加邊：

(1)無向圖：在頂點\(i\)和\(j\)的鏈表中分別添加節(jié)點。

(2)有向圖：在頂點\(i\)的鏈表中添加指向頂點\(j\)的節(jié)點。

3.示例：

-無向圖：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

-有向圖：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間效率：對于稀疏圖，鄰接表更節(jié)省空間，只存儲實際存在的邊。

(2)邊數(shù)靈活性：可以動態(tài)添加或刪除邊，適合動態(tài)變化的圖。

2.缺點：

(1)查詢效率：判斷兩個頂點之間是否存在邊，需要遍歷鏈表，時間復(fù)雜度為\(O(d)\)，其中\(zhòng)(d\)是頂點的度數(shù)。

(2)實現(xiàn)復(fù)雜度：鏈表操作相對矩陣操作更復(fù)雜。

四、適用場景

1.鄰接矩陣：

(1)稠密圖：邊數(shù)接近頂點平方，鄰接矩陣空間效率較高。

(2)需要頻繁查詢邊關(guān)系：快速判斷頂點間是否存在邊。

2.鄰接表：

(1)稀疏圖：邊數(shù)遠小于頂點平方，鄰接表空間效率更高。

(2)動態(tài)變化的圖：方便添加或刪除邊。

一、概述

圖的鄰接矩陣和鄰接表是兩種常見的圖數(shù)據(jù)結(jié)構(gòu)表示方法，用于存儲圖中的節(jié)點（頂點）和邊（?。┬畔?。這兩種表示方法各有優(yōu)缺點，適用于不同的應(yīng)用場景。本細則將詳細說明圖的鄰接矩陣和鄰接表的定義、表示方法、優(yōu)缺點及適用場景，并探討如何在實際應(yīng)用中選擇合適的表示方法。通過本細則的學(xué)習(xí)，讀者能夠掌握這兩種圖表示方法的實現(xiàn)細節(jié)，并能夠在具體問題中靈活運用。

二、鄰接矩陣表示

鄰接矩陣是一種使用二維數(shù)組來表示圖的結(jié)構(gòu)，其中矩陣的行和列分別代表圖的頂點，矩陣中的元素表示頂點之間的邊關(guān)系。

（一）定義

1.矩陣表示：用\(n\timesn\)的矩陣\(A\)表示包含\(n\)個頂點的圖，其中\(zhòng)(A[i][j]\)表示頂點\(i\)和頂點\(j\)之間的邊關(guān)系。

2.無向圖：若\(A[i][j]=1\)，表示頂點\(i\)和頂點\(j\)之間存在無向邊；若\(A[i][j]=0\)，表示不存在邊。

3.有向圖：若\(A[i][j]=1\)，表示從頂點\(i\)到頂點\(j\)存在一條有向邊；若\(A[i][j]=0\)，表示不存在邊。

4.權(quán)重表示：對于帶權(quán)圖，\(A[i][j]\)可以表示頂點\(i\)和頂點\(j\)之間的邊的權(quán)重，權(quán)重值可以是正數(shù)、負數(shù)或無窮大（表示無邊）。

（二）表示方法

1.初始化矩陣：創(chuàng)建一個\(n\timesn\)的矩陣，所有元素初始化為0或無窮大（表示無邊）。具體步驟如下：

(1)確定頂點數(shù)量\(n\)，創(chuàng)建一個\(n\timesn\)的矩陣\(A\)。

(2)遍歷矩陣的每個元素\(A[i][j]\)，將所有元素初始化為0或無窮大。

2.填充矩陣：根據(jù)圖的邊信息，將對應(yīng)的矩陣元素設(shè)置為1或其他表示邊的值。具體步驟如下：

(1)遍歷圖的每條邊，假設(shè)邊的起點為\(i\)，終點為\(j\)，權(quán)重為\(w\)。

(2)對于無向圖，將\(A[i][j]\)和\(A[j][i]\)都設(shè)置為1或權(quán)重\(w\)。

(3)對于有向圖，將\(A[i][j]\)設(shè)置為1或權(quán)重\(w\)。

(4)對于帶權(quán)圖，將\(A[i][j]\)設(shè)置為權(quán)重\(w\)。

3.示例：

-無向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(1,4),(2,3),(3,4)\)，鄰接矩陣表示為：

\(A=\begin{pmatrix}0&1&0&1\\1&0&1&0\\0&1&0&1\\1&0&1&0\end{pmatrix}\)

-有向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(2,3),(3,4)\)，鄰接矩陣表示為：

\(A=\begin{pmatrix}0&1&0&0\\0&0&1&0\\0&0&0&1\\0&0&0&0\end{pmatrix}\)

-帶權(quán)圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2,5),(1,4,3),(2,3,2),(3,4,4)\)，鄰接矩陣表示為：

\(A=\begin{pmatrix}0&5&\infty&3\\\infty&0&2&\infty\\\infty&\infty&0&4\\\infty&\infty&\infty&0\end{pmatrix}\)

（三）優(yōu)缺點

1.優(yōu)點：

(1)空間復(fù)雜度：對于稠密圖，鄰接矩陣存儲效率較高，時間復(fù)雜度為\(O(n^2)\)。

(2)查詢效率：快速判斷兩個頂點之間是否存在邊，時間復(fù)雜度為\(O(1)\)。

(3)易于實現(xiàn)：鄰接矩陣的實現(xiàn)相對簡單，適合用于靜態(tài)圖。

2.缺點：

(1)空間浪費：對于稀疏圖，矩陣中大量元素為0，造成空間浪費。

(2)邊數(shù)限制：需要預(yù)分配固定大小的矩陣，不適合動態(tài)變化的圖。

(3)度數(shù)計算：計算頂點的度數(shù)需要遍歷整個行或列，時間復(fù)雜度為\(O(n)\)。

三、鄰接表表示

鄰接表是一種使用鏈表或數(shù)組來表示圖的結(jié)構(gòu)，其中每個頂點對應(yīng)一個鏈表，鏈表中的節(jié)點表示與該頂點相鄰的頂點。

（一）定義

1.結(jié)構(gòu)：用數(shù)組\(G\)表示圖，其中\(zhòng)(G[i]\)是一個鏈表，鏈表中的節(jié)點表示頂點\(i\)的鄰接頂點。

2.無向圖：鏈表中的節(jié)點表示與頂點\(i\)相鄰的頂點\(j\)。

3.有向圖：鏈表中的節(jié)點表示從頂點\(i\)出發(fā)的邊指向的頂點\(j\)。

4.帶權(quán)圖：鏈表中的節(jié)點可以包含頂點編號和邊的權(quán)重。

（二）表示方法

1.初始化：創(chuàng)建一個數(shù)組，每個元素初始化為空鏈表。具體步驟如下：

(1)確定頂點數(shù)量\(n\)，創(chuàng)建一個大小為\(n\)的數(shù)組\(G\)。

(2)遍歷數(shù)組\(G\)的每個元素，將所有元素初始化為空鏈表。

2.添加邊：

(1)無向圖：在頂點\(i\)和\(j\)的鏈表中分別添加節(jié)點。具體步驟如下：

-創(chuàng)建一個節(jié)點，節(jié)點數(shù)據(jù)為\(j\)。

-將該節(jié)點插入到頂點\(i\)的鏈表頭部。

-將該節(jié)點插入到頂點\(j\)的鏈表頭部。

(2)有向圖：在頂點\(i\)的鏈表中添加指向頂點\(j\)的節(jié)點。具體步驟如下：

-創(chuàng)建一個節(jié)點，節(jié)點數(shù)據(jù)為\(j\)。

-將該節(jié)點插入到頂點\(i\)的鏈表頭部。

(3)帶權(quán)圖：在頂點\(i\)的鏈表中添加指向頂點\(j\)的節(jié)點，節(jié)點數(shù)據(jù)為\((j,w)\)，其中\(zhòng)(w\)為邊的權(quán)重。具體步驟如下：

-創(chuàng)建一個節(jié)點，節(jié)點數(shù)據(jù)為\((j,w)\)。

-將該節(jié)點插入到頂點\(i\)的鏈表頭部。

3.示例：

-無向圖：

假設(shè)有圖\(G\)包含4個頂點，邊為\((1,2),(1,4),(2,3),(3,4)\)，鄰接表表示為：

\(G=[\text{鏈表1},\text{鏈表2},\text{鏈表3},\text{鏈表4}]\)

其中：

-鏈表1：節(jié)點(2,0),節(jié)點(4,0)

-鏈表2：節(jié)點(1,0),節(jié)點(3,0)

-鏈表3：節(jié)點(2,0),節(jié)點(4,0)

-鏈表4：節(jié)點(1,0),節(jié)點(3,0)

-有向圖：

假設(shè)有圖\(G\)