一、圖的基本概念

圖： 圖G是一個有序二元組(V,E)，其中V稱為頂集(Vertices Set)，E稱為邊集(Edges set)，E與V不相交。它們亦可寫成V(G)和E(G)。其中，頂集的元素被稱為頂點(Vertex)，邊集的元素被稱為邊(edge)。

有向圖： 若E是有向邊（也稱弧）的有限集合時，則圖G為有向圖。弧是頂點的有序對，記為 $<v,w>$ ，稱為從頂點v到頂點w的弧。如上圖中（a）：$G_1=(V_1,E_1)||V_1=\{1,2,3\}||E_1=\{<1,2>,<2,1>,<2,3>\}$

無向圖： 若E是無向邊（簡稱邊）的有限集合時，則圖G為無向圖。邊是頂點的無序對，記為 $<v,w>$ ，稱為從頂點v和頂點w的互為鄰接點。如上圖中（b）：$G_1=(V_1,E_1)||V_1=\{1,2,3,4\}||E_1=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4))\}$

簡單圖： 一個圖滿足：① 不存在重復邊；② 不存在頂點到自身的邊，則稱圖G為簡單圖。數據結構中只討論簡單圖，如圖a,b,c

多重圖： 不滿足簡單圖中兩個條件，則稱為多重圖。

完全圖： 在無向圖中，若任意兩個頂點之間都存在邊，則稱該圖為無向完全圖。擁有n個頂點的無向完全圖有 $\frac{n(n?1)}{2}$ 條邊，如圖b

子圖： 設有兩個圖 $G=(V,E)$ 和 $G_1=(V_1,E_1)$ ，若 $V_1$ 是 $V$ 的子集，且 $E_1$ 是 $E$ 的子集，則稱 $G_1$ 是 $G$ 的子圖。如圖a和c

連通： 若從頂點v到頂點w有路徑存在，則稱v和w是連通的

連通圖： 若圖 $G$ 中任意兩個頂點都是連通的，則稱圖 $G$ 為連通圖，否則稱為非連通圖

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

極大連通子圖：

連通圖只有一個極大連通子圖，就是它本身。（是唯一的）

非連通圖有多個極大連通子圖。（非連通圖的極大連通子圖叫做連通分量，每個分量都是一個連通圖

稱為極大是因為如果此時加入任何一個不在圖的點集中的點都會導致它不再連通。

下圖為非連通圖，圖中有兩個極大連通子圖（連通分量）。

極小連通子圖：

一個連通圖的生成樹是該連通圖頂點集確定的極小連通子圖。（同一個連通圖可以有不同的生成樹，所以生成樹不是唯一的）
（極小連通子圖只存在于連通圖中）

用邊把極小連通子圖中所有節點給連起來，若有n個節點，則有n-1條邊。如下圖生成樹有6個節點，有5條邊。

之所以稱為極小是因為此時如果刪除一條邊，就無法構成生成樹，也就是說給極小連通子圖的每個邊都是不可少的。

如果在生成樹上添加一條邊，一定會構成一個環。

也就是說只要能連通圖的所有頂點而又不產生回路的任何子圖都是它的生成樹。

總結來說：極大連通子圖是討論連通分量的,極小連通子圖是討論生成樹的。

強連通圖： 有向圖 $G$ 中， 若對于 $V(G)$ 中任意兩個不同的頂點 $v_i$ 和 $v_j$ ，都存在從 $v_i$ 到 $v_j$ 以及從 $v_j$ 到 $v_i$ 的路徑，則稱圖 $G$ 是強連通圖。如圖c

強連通分量： 有向圖的極大強連通子圖稱為 $G$ 的強連通分量，強連通圖只有一個強連通分量，即是其自身。非強連通的有向圖有多個強連通分量。

生成樹： 連通圖的生成樹是包含圖中所有頂點的一個極小連通子圖。若圖中有n個點，那么生成樹含有n-1條邊，無論消去哪條邊，整個圖就不再連通；而無論在哪兩個頂點加上一條邊，都會形成回路

生成森林： 在非連通圖中，連通分量的生成樹構成了非連通圖的生成森林。

頂點的度：（無向圖）該頂點為一個端點的邊的數目，記為 $TD(v)$。度與邊之比為 $2e:e$

頂點的入度：（有向圖）以頂點v的為終點的有向邊的數目$ID(v)$

頂點的出度：（有向圖）以頂點v的為起點的有向邊的數目$OD(v)$

邊的權和網： 在一個圖中，每條邊都可以標上具有某種含義的數值，該數值稱為該邊的權值；這種邊上帶有權值的圖稱為帶權圖，也稱為網

稠密圖： 邊數很多的圖。一般滿足 $E\ge VlogV$ 的圖稱為稀疏圖

稀疏圖： 邊數很少的圖。一般滿足 $E<VlogV$ 的圖稱為稀疏圖

路徑： 頂點 $V_p$ 到頂點 $V_q$ 之間的一條路徑是指頂點序列 $V_p$ ， $V_{i1}$ ， $V_{i2}$ ，…， $V_m$ ， $V_p$

路徑長度： 路徑上邊的數目

回路： 第一個頂點和最后一個頂點相同的路徑

簡單路徑： 頂點不重復出現的路徑

簡單回路： 除第一個頂點和最后一個頂點外，其余頂點不重復出現的回路

距離： 從頂點 $V_1$ 到頂點 $V_2$ 的最短路徑若存在，則此路徑的長度稱為從頂點 $V_1$ 到頂點 $V_2$ 的距離

有向樹： 一個頂點的入度為0、其余頂點的入度均為1

二、圖的構造

2.1 構造鄰接矩陣

不帶權圖：
$$A[i][j]=\{\begin{array}{ll}1,& \text{若(V1?,V2?)或<V1?,V2?>是圖中的邊}\\ 0,& \text{若(V1?,V2?)或<V1?,V2?>不是圖中的邊}\end{array}$$
帶權圖：
$$A[i][j]=\{\begin{array}{ll}{W}_{ij},& \text{若(V1?,V2?)或<V1?,V2?>是圖中的邊}\\ 0或\infty ,& \text{若(V1?,V2?)或<V1?,V2?>不是圖中的邊}\end{array}$$

#include <stdio.h> int main() {const int MAX_N = 5; // 一共有五個頂點 int G[MAX_N][MAX_N] = {}; // 使用鄰接矩陣表示G[0][2] = 1; // 將圖連通且不帶權G[0][4] = 1; G[1][0] = 1; G[1][2] = 1; G[2][3] = 1; G[3][4] = 1;G[4][3] = 1;printf("G:\n");for(int i=0; i<5; i++) {for(int j=0; j<5; j++) {printf("%d",G[i][j]);}printf("\n"); }return 0; }

注意：

在簡單應用中，可直接用二維數組作為圖的鄰接矩陣

無向圖的鄰接矩陣是對稱矩陣，對規模特大的鄰接矩陣可采用壓縮存儲。

鄰接矩陣表示法的空間復雜度為$O(n^2)$，其中n為圖的頂點數。

圖的鄰接矩陣存儲表示法具有以下特點∶

無向圖的鄰接矩陣一定是一個對稱矩陣（并且唯一）。因此，在實際存儲鄰接矩陣時只需存儲上（或下）三角矩陣的元素.

對于無向圖，鄰接矩陣的第 i 行（或第 i 列）非零元素的個數態好是第 i 個頂點的度 TD（v）

對于有向圖，鄰接矩陣的第i行（或第i列）非零元素（或非四元素）的參正好是第i個頂點的出度 OD（v）（或入度ID（v）

用鄰接矩陣法存儲圖，很容易確定圖中任意兩個頂點之間是否有邊相差。但是，要確定圖中有多少條邊，則必須按行、按列對每個元素進行檢測，所花費的時間代價很大。這是用鄰接矩陣存儲圖的局限性。

密圖適合使用鄰接矩陣的存儲表示。

設圖G的鄰接矩陣為A，$A^n$的元素 $A^n[i][j]$ 等于由頂點 i 到頂點 j 的長度為n的路徑的數?目。

2.2 鄰接表

我覺得圖比問題更容易理解事物本質，所以簡單講一下概念，直接上圖。

所謂鄰接表，是指對圖 G中的每個頂點v建立一個單鏈表，第 i 個單鏈表中的結點表示依附于頂點 v 的邊（對于有向圖則是以頂點v為尾的弧），這個單鏈表就稱為頂點v的邊表（對于有向圖則稱為出邊表）。

#include <stdio.h> #include <vector> using namespace std;struct GNode{int val;vector<GNode*> neighbors;GNode(int x):val(x) {} }; int main() {int MAX_N = 5; // 五個節點GNode *Node[MAX_N];for(int i = 0; i < MAX_N; i++) {Node[i] = new GNode(i);}Node[0]->neighbors.push_back(Node[2]);Node[0]->neighbors.push_back(Node[4]);Node[1]->neighbors.push_back(Node[0]);Node[1]->neighbors.push_back(Node[2]);Node[2]->neighbors.push_back(Node[3]);Node[3]->neighbors.push_back(Node[4]);Node[4]->neighbors.push_back(Node[3]);printf("Node:\n");for(int i = 0; i < MAX_N; i++) {printf("Node[%d]:",i);for(int j = 0; j < Node[i]->neighbors.size(); j++) {printf("%d ",Node[i]->neighbors[j]->val);}printf("\n");}for (int i = 0; i < MAX_N; i++) {delete Node[i];}return 0; }

圖的鄰接表存儲方法具有以下特點∶

若G為無向圖，則所需的存儲空間為 $O(V+2E)$ ;若G為有向圖，則所需的存儲空間為 $O(V+E)$ 。前者的倍數2是由于無向圖中，每條邊在鄰接表中出現了兩次。

對于稀疏圖，采用鄰接表表示將極大地節省存儲空間。

在鄰接表中，給定一頂點，能很容易地找出它的所有鄰邊，因為只需要讀取它的鄰接表。?在鄰接矩陣中，相同的操作則需要掃描一行，花費的時間為 O(n)。但是，若要確定給定的兩個頂點間是否存在邊，則在鄰接矩陣中可以立刻查到，而在鄰接表中則需要在相應結點對應的邊表中查找另一結點，效率較低。

在有向圖的鄰接表表示中，求一個給定頂點的出度只需計算其鄰接表中的結點個數;但?求其頂點的入度則需要遍歷全部的鄰接表。因此，也有人采用逆鄰接表的存儲方式來加速求解給定頂點的入度。當然，這實際上與鄰接表存儲方式是類似的。

圖的鄰接表表示并不唯一，因為在每個頂點對應的單鏈表中，各邊結點的鏈接次序可以?是任意的，它取決于建立鄰接表的算法及邊的輸入次序。

2.3 十字鏈表

十字鏈表是有向圖的另一種鏈式存儲結構。該結構可以看成是將有向圖的鄰接表和逆鄰接表結合起來得到的。用十字鏈表來存儲有向圖，可以達到高效的存取效果。同時，代碼的可讀性也會得到提升。

頂點結點：

data域：存放頂點相關的數據信息

firstin域：以該結點為弧頭（線段上有箭頭的）

firstout域：以該結點為弧尾（線段上無箭頭的）

弧結點：

tailvex：指示弧尾（線段上無箭頭的）

headvex：指示弧頭（線段上有箭頭的）

hlink：弧頭相同的下一條弧

tlink：弧尾相同的下一條弧

info：指向該弧的相關信息

十字鏈表存儲結構：

typedef struct ArcBox // 弧的結構表示 {int tailvex, headvex;InfoType *info;struct ArcBox *hlink, *tlink; } VexNode; typedef struct VexNode // 頂點的結構表示 {VertexType data;ArcBox *firstin, *firstout; } VexNode; typedef struct {VexNode xlist[MAX_VERTEX_NUM];// 頂點結點(表頭向量)int vexnum, arcnum;//有向圖的當前頂點數和弧數 } OLGraph;

對于十字鏈表的一些認識：

表頭結點即頂點結點，與鄰接表一樣是順序存儲。

對于每個頂點結點之后是與之相關聯的弧結點（該弧結點中存有弧頭、弧尾），而鄰接表則是一些與頂點結點相連接的點。

從每個頂點結點開始有兩條鏈表，一條是以該頂點結點為弧頭的鏈表，一條是以該頂點結點為弧尾的鏈表。

對于其中的每一條鏈表必然是從頂點結點開始，直到與之相關的弧結點鏈域headlink和taillink為空是結束，構成一條完整的鏈表。

2.4 鏈表多重表

鄰接多重表存儲無向圖的方式，可看作是鄰接表和十字鏈表的結合。同鄰接表和十字鏈表存儲圖的方法相同，都是獨自為圖中各頂點建立一張鏈表，存儲各頂點的節點作為各鏈表的首元節點，同時為了便于管理將各個首元節點存儲到一個數組中。

鄰接多重表各結點的結構示意圖，如下圖所示：

data：存儲此頂點的數據；

firstedge：指針域，用于指向同該頂點有直接關聯的存儲其他頂點的節點。

各鏈表中其他節點的結構與十字鏈表中相同，如下圖所示：

mark：標志域，用于標記此節點是否被操作過，例如在對圖中頂點做遍歷操作時，為了防止多次操作同一節點，mark 域為 0 表示還未被遍歷；mark 為 1 表示該節點已被遍歷；

ivex 和 jvex：數據域，分別存儲圖中各邊兩端的頂點所在數組中的位置下標；

ilink：指針域，指向下一個存儲與 ivex 有直接關聯頂點的節點；

jlink：指針域，指向下一個存儲與 jvex 有直接關聯頂點的節點；

info：指針域，用于存儲與該頂點有關的其他信息，比如無向網中各邊的權；

無向圖的鄰接多重表表示，如下圖所示：

#define MAX_VERTEX_NUM 20 //圖中頂點的最大個數 #define InfoType int //邊含有的信息域的數據類型 #define VertexType int //圖頂點的數據類型 typedef enum {unvisited,visited}VisitIf; //邊標志域 typedef struct EBox{VisitIf mark; //標志域int ivex,jvex; //邊兩邊頂點在數組中的位置下標struct EBox * ilink,*jlink; //分別指向與ivex、jvex相關的下一個邊InfoType *info; //邊包含的其它的信息域的指針 }EBox; typedef struct VexBox{VertexType data; //頂點數據域EBox * firstedge; //頂點相關的第一條邊的指針域 }VexBox; typedef struct {VexBox adjmulist[MAX_VERTEX_NUM];//存儲圖中頂點的數組int vexnum,degenum;//記錄途中頂點個數和邊個數的變量 }AMLGraph;

三、圖的遍歷

3.1 圖的深度優先遍歷

從圖中某個頂點v出發，首先訪問該頂點

然后依次從它的各個未被訪問的鄰接點出發深度優先搜索遍歷圖

直至圖中所有和v有路徑相通且未被訪問的頂點都被訪問到。

若此時尚有其他頂點未被訪問到

則另選一個未被訪問的頂點作起始點，

重復上述過程，直至圖中所有頂點都被訪問到為止。

#include <stdio.h> #include <vector> using namespace std;struct GNode{int val;vector<GNode*> neighbors;GNode(int x):val(x){} };void DFSGraph(GNode *node, int visit[]) {visit[node->val] = 1; // 標記已訪問的頂點printf("%d ",node->val);for(int i = 0; i < node->neighbors.size(); i++) {if(visit[node->neighbors[i]->val] == 0) {DFSGraph(node->neighbors[i], visit);}} }int main() {int MAX_N = 5;GNode *Node[MAX_N];for(int i = 0; i < MAX_N; i++) {Node[i] = new GNode(i);}Node[0]->neighbors.push_back(Node[2]);Node[0]->neighbors.push_back(Node[4]);Node[1]->neighbors.push_back(Node[0]);Node[1]->neighbors.push_back(Node[2]);Node[2]->neighbors.push_back(Node[3]);Node[3]->neighbors.push_back(Node[4]);Node[4]->neighbors.push_back(Node[3]);int visit[MAX_N] = {0};for(int i = 0; i < MAX_N; i++) {if(visit[i] == 0) { // 沒有標記的頂點才會被訪問 printf("From val(%d): ", Node[i]->val);DFSGraph(Node[i], visit);printf("\n");}}for (int i = 0; i < MAX_N; i++) {delete Node[i];}return 0; }

時間復雜度：以鄰接矩陣為例，查找每個頂點的鄰接點所需的時間為 $O(|V|)$，故總的時間復雜度為 $O(|V{|}^2)$；以鄰接表為例，查找所有頂點的鄰接點所需的時間為$O(|E|)$ ，訪問頂點所需的時間為 $O(|V|)$，故總的時間復雜度為 $O(|V|+|E|)$

空間復雜度：需要一個遞歸棧，$O(|V|)$

3.2 圖的廣度優先遍歷

從圖中某個頂點v出發，在訪問了v之后依次訪問v的各個未曾訪問過的鄰接點，

然后分別從這些鄰接點出發依次訪問它們的鄰接點，

并使得"先被訪問的頂點的鄰接點先于后被訪問的頂點的鄰接點被訪問"，

直至圖中所有已被訪問的頂點的鄰接點都被訪問到。

如果此時圖中尚有頂點未被訪問，

則需要另選一個未曾被訪問過的頂點作為新的起始點，

重復上述過程，直至圖中所有頂點都被訪問到為止。

#include <stdio.h> #include <vector> #include <queue> using namespace std;struct GNode{int val;vector<GNode*> neighbors;GNode(int x):val(x){} };void BFSGraph(GNode *node, int visit[]) {queue<GNode*> q; // 廣度優先搜索使用隊列 q.push(node);visit[node->val] = 1; // 標記已訪問的頂點while(!q.empty()){GNode *temp = q.front();q.pop();printf("%d ",temp->val);for(int i = 0; i < temp->neighbors.size(); i++) {if(visit[temp->neighbors[i]->val] == 0) {q.push(temp->neighbors[i]);visit[temp->neighbors[i]->val] = 1;}} } }int main() {int MAX_N = 5;GNode *Node[MAX_N];for(int i = 0; i < MAX_N; i++) {Node[i] = new GNode(i);}Node[0]->neighbors.push_back(Node[2]);Node[0]->neighbors.push_back(Node[4]);Node[1]->neighbors.push_back(Node[0]);Node[1]->neighbors.push_back(Node[2]);Node[2]->neighbors.push_back(Node[3]);Node[3]->neighbors.push_back(Node[4]);Node[4]->neighbors.push_back(Node[3]);int visit[MAX_N] = {0};for(int i = 0; i < MAX_N; i++) {if(visit[i] == 0) { // 沒有標記的頂點才會被訪問 printf("From val(%d): ", Node[i]->val);BFSGraph(Node[i], visit);printf("\n");}}for (int i = 0; i < MAX_N; i++) {delete Node[i];}return 0; }

時間復雜度：以鄰接矩陣為例，查找每個頂點的鄰接點所需的時間為 $O(|V|)$，故總的時間復雜度為 $O(|V{|}^2)$；以鄰接表為例，在任意頂點的鄰接表，每條邊至少訪問一次，此時時間復雜度為 $O(|E|)$ ，另外，每個頂點均需搜索一次，此時時間復雜度為 $O(|V|)$，故總的時間復雜度為 $O(|V|+|E|)$

空間復雜度：需要一個輔助隊列Q，最壞的情況下，空間復雜度為 $O(|V|)$

總結

以上是生活随笔為你收集整理的【数据结构-图】1.图的构造和遍历（基本理论+代码）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。