化解資料結構----圖的基礎知識（萬字系列，必備知識）

📢📢📢📣📣📣

🌻🌻🌻Hello，大家好我叫是Dream呀，一個有趣的Python部落客，多多關照😜😜😜

🏅🏅🏅Python領域優質創作者，歡迎大家找我合作學習（文末有名片歡迎+++）

💕

入門須知：這片樂園從不缺乏天才，努力才是你的最終入場券！🚀🚀🚀

💓

最後，願我們都能在看不到的地方閃閃發光，一起加油進步🍺🍺🍺

🍉🍉🍉“一萬次悲傷，依然會有Dream，我一直在最溫暖的地方等你”，唱的就是我！哈哈哈~🌈🌈🌈

🌟🌟🌟✨✨✨

圖知識架構：

(圖的基礎知識：)

一、圖的定義和基本術語

1.圖的定義

圖： 簡單的說，圖是一個用線或邊連接配接在一起的頂點或節點的集合，嚴格的說，

圖是有限頂點V和邊E的有序對

。

圖的表示：一般使用圓圈表示頂點，使用線段表示邊，一條邊連接配接兩個不同的頂點。有些邊是帶方向的稱為有向邊，當頂點v到u含有一條有向邊，就畫一個箭頭從v指向u，使用元組<v，u>表示；而沒有方向的邊稱為無向邊，當頂點v到u含有一條有向邊，就畫一條線段從v指向u，使用元組（v，u）表示。例如下面分别是有向圖和無向圖。

圖根據邊的分類分為有向圖和無向圖：

1. 有向圖的邊是有向邊，它就像公路的單行道一樣，隻能從一個方向到另一個方向

   。

2. 無向圖的邊是無向邊，當然它就像雙向車道一樣可以互相到達，而且兩個頂點是沒有差別的。

當且僅當（u，v）是圖的邊，稱頂點v和u是鄰接的。邊（u，v）關聯于頂點u和v。

對于無向圖這種鄰接和關聯是對等的，而有向圖是單向的，它僅僅從u到v。

無向邊用小括号（）表示，有向邊用尖括号<>表示。
           

2.圖的基本術語

2.1子圖

如果圖H的頂點和邊的集合是圖G的子集，那麼稱圖H是圖G的子圖。

2.2 無向完全圖和有向完全圖

任意兩點間都存在邊使其相連的無向圖或任意兩點間都存在兩條不同邊的有向圖稱作完全圖

N個頂點的完全圖:

• 有向 有n(n-1)條邊

  無向 有n(n-1)/2條邊

2.3稀疏圖和稠密圖

顧名思義，就是讨論多少的問題，注意分界點，這個依據是大家預設的一個依據，而不是必須的分界依據！

資料結構中對于稀疏圖的定義為：有很少條邊或弧（邊的條數|E|遠小于|V|²）的圖稱為稀疏圖（sparse graph），反之邊的條數|E|接近|V|²，稱為稠密圖（dense graph）。此定義來自百度百科，實際上是一種樸素的了解，簡單來說邊越多，圖就越稠密

2.4權和網

權： 在圖的一些應用中，可能要為每條邊賦予一個表示大小的值，這個值就稱為權。例如從城市A到城市B存在一條公路，而可以使用權表示這條公路的距離。

那我們把

**帶權的圖稱為網**

。

2.5鄰接點

2.6度、入度、出度

頂點的度為以該頂點為一個端點的邊的數目。

對于無向圖，頂點的邊數為度，

度數之和是頂點邊數的兩倍

。

對于有向圖，入度是以頂點為終點，出度相反。

有向圖的全部頂點入度之和等于出度之和且等于邊數

。頂點的度等于入度與出度之和。

注意：入度與出度是針對有向圖來說的。

2.7路徑和路徑長度

兩頂點之間的路徑指頂點之間經過的頂點序列，經過路徑上邊的數目稱為路徑長度。

2.8回路和環

第一個頂點和最後一個頂點相同的路徑稱為回路或者環。

2.9簡單路徑、簡單回路和簡單環

頂點不重複出現的路徑稱為簡單路徑。

除第一個頂點和最後一個頂點外，其餘頂點不重複出現的回路稱為簡單回路或者簡單環。

2.10連通、連通圖和連通分量

在無向圖中，

兩頂點有路徑存在，就稱為連通的

。若

圖中任意兩頂點都連通

，同此圖為連通圖。

無向圖中的極大連通子圖稱為連通分量。

2.11強連通圖和強連通分量

在有向圖中，

兩頂點兩個方向都有路徑，兩頂點稱為強連通

。

若任一頂點都是強連通的，稱為強連通

。

有向圖中

極大強連通子圖為有向圖的強連通分量

。

2.12連通圖的生成樹

• 連通圖的生成樹

  是包含圖中全部頂點的一個極小連通子圖

  ，

  若圖中有n個頂點，則生成樹有n-1條邊

  。是以對于生成樹而言，若砍去一條邊，就會變成非連通圖。
• 一顆有

  n個頂點

  的生成樹有且僅有

  n-1條邊

  。
• 如果一個圖

  n個頂點，邊數多于n-1則說明其一定有環

• n-1條邊的圖卻不一定是生成樹。

2.13有向樹和生成森林

一個有向圖的生成森林是

由若幹顆有向樹組成的，含有圖中的全部頂點，

但隻有足以構成若幹棵不相交的有向樹的弧。

二、圖的類型定義

emmmm，😍😍😍你在期待哪種圖呢😍😍😍…………………………………………

1.

CreateGraph(*G,V,VR)

//按照頂點集V合邊弧集VR定義構造圖G

2.

DestroyGraph(*G)

//銷毀圖G

3.

LocateVex(G,u)

//傳回圖G中頂點u的位置，若不存在，則傳回其他資訊

4.

GetVex(G,v)

//傳回圖G中頂點v的值

5.

PutVex(G,v,value)

//将圖G中頂點v指派value

6.

FirstAdjVex(G,*v)

//傳回頂點v的一個鄰接頂點，若無則傳回空

7.

NextAdjVex(G,v,w)

//頂點w是頂點v的鄰接頂點，傳回頂點v相對于頂點w的下一個鄰接頂點；若頂點w是頂點v的最後一個鄰接頂點，則傳回空

8.

InsertVex(*G,v)

//在圖G種添加頂點v

9.

DeleteVex(*G,v)

//删除圖G中頂點v及其相關的弧

10.

InsertArc(*G,v,w)

//在圖G中添加弧<v,w>,如果是無向圖，還要添加對稱弧<w,v>

11.

DeleteArc(*G,v,w)

//在圖G中删除弧<v,w>,如果是無向圖，還要删除對稱弧<w,v>

12.

DFSTraverse(G)

//對圖G進行深度優先周遊

13.

HFSTraverse(G)

//對圖G進行廣度優先周遊

三、圖的存儲結構

1.鄰接矩陣

所謂鄰接矩陣存儲結構就每個頂點用一個一維數組存儲邊的資訊，這樣所有點合起來就是用矩陣表示圖中各頂點之間的鄰接關系。所謂矩陣其實就是二維數組。

1.1無向圖的鄰接矩陣表示法

1. 無向圖的鄰接矩陣是對稱的；
2. 頂點i的度 = 第i行（列）中1的個數

注意： 完全圖的鄰接矩陣中，對角元素為0，其餘的為1

1.2有向圖的鄰接矩陣表示法

1. 有向圖的鄰接矩陣可能是不對稱的；
2. 頂點的出度 = 第i行元素之和
3. 頂點的入度 = 第i列元素之和
4. 頂點的度 = 第i行元素之和+第i列元素之和

1.3網的鄰接矩陣表示法

網就是有權的圖（路徑上有數值，即有權重）

• 有邊或者有弧：權
• 無邊或者無弧：無窮

  

1.4鄰接矩陣存儲表示

用兩個數組分别存儲頂點表和鄰接矩陣！

C語言版：

int g[N][N];
int main() {
	int n, m; //n個點 m條邊 
	scanf("%d%d", &n, &m);
	int u, v; //從u到v
	for (int i = 0; i < m; ++i) {
		scanf("%d%d", &u, &v);
		g[u][v] = 1; 
		//g[v][u] = 1;//無向圖要建雙邊 
		//g[u][v] = w; //帶權圖
	} 
}
           

1.5采用鄰接矩陣表示法建立無向網

步驟：

1. 輸入總頂點數和總邊數
2. 依次輸入點的資訊存入頂點表中
3. 初始化鄰接矩陣，使每個權值初始化為最大值
4. 構造鄰接矩陣

   

   代碼實作：

   

1.6鄰接矩陣好處

1. 直覺、簡單、好了解
2. 友善檢查任意一對頂點間是否存在邊
3. 友善找任意一項的所有鄰接點
4. 友善計算度

   

1.7鄰接矩陣壞處

1. 不便于增加和删除頂點
2. 浪費空間，對稀疏圖而言
3. 浪費時間

   

2.鄰接表

2.1鄰接表表示法（鍊式）

• 頭結點data：存儲頂點
• 表結點 鄰接點域adjvex：存儲相連的頂點的序号，從0開始
• 表結點 鍊域nextarc：訓示下一條邊或者弧

  

  無向圖：

1. 鄰接表不唯一（表結點位置可以互換）
2. 若無向圖中有n個頂點、e條邊，則其鄰接表需n個頭結點和2e個表結點。适合存儲稀疏圖。
3. 無向圖中的頂點vi的度為第i個單連結清單中的結點數。

   

有向圖：

1.鄰接表

• 找出度（vi的出度是第i個單連結清單中結點的個數）易，找入度（vi的入度為整個單連結清單中鄰接點域值是i-1的結點個數）難；

2.逆鄰接表

• 同理 找入度易，找出度難

2.2圖的鄰接表存儲形式

2.3鄰接表的操作舉例說明

2.4利用鄰接表表示法建立無向網

2.5鄰接表的特點

• 友善找任一頂點的所有“鄰接點”
• 節約稀疏圖的空間（·需要N個頭指針＋2E個結點(每個結點至少2個域)）
• 友善計算任一頂點的“度”：1.對無向圖:是的 2.對有向圖:隻能計算“出度”;需要構造“逆鄰接表”求入度
• 不友善檢查任意一對頂點間是否存在邊

  

2.6鄰接矩陣和鄰接表表示法的關系

1.聯系: 鄰接表中每個連結清單對應于鄰接矩陣中的一行，連結清單中結點個數等于一行中非零元素的個數。

2.差別：

• 對于任一确定的無向圖，鄰接矩陣是

  唯一

  的(行列号與頂點編号一緻)，但鄰接表

  不唯一

  （連結次序與頂點編号無關)。
• 鄰接矩陣的空間複雜度為O(n2),而鄰接表的空間複雜度為O(n+e)。無向e，有向2e

3.用途: 鄰接矩陣多用于

稠密圖

;而鄰接表多用于

稀疏圖

3.十字連結清單——用于有向圖

十字連結清單(Orthogonal List)是有向圖的另一種鍊式存儲結構。

我們也可以把它看成是将

有向圖的鄰接表和逆鄰接表

結合起來形成的一種連結清單。

有向圖中的

每一條弧

對應十字連結清單中的一個

弧結點

，同時有向圖中的

每個頂點

在十字連結清單中對應有一個結點，叫做

頂點結點

。

頂點結點：

• firstin：第一條入弧
• firstout：第一條出弧

弧結點：

• tailvex:弧尾位置
• headvex：弧頭位置
• hilnk：弧頭相同的下一條弧
• tlink：弧尾相同的下一條弧

4.鄰接多重表（無向圖的另一種鍊式存儲結構）

鄰接表優點: 容易求得頂點和邊的資訊。

缺點: 某些操作不友善（如:删除一條邊需找表示此邊的兩個結點)