📚 【考研408數據結構-08】 圖論基礎:存儲結構與遍歷算法
🎯 考頻:????? | 題型:選擇題、綜合應用題、算法設計題 | 分值:約8-15分
引言
想象你正在規劃一次跨省自駕游,面前攤開一張復雜的公路地圖。城市是節點,公路是邊,有的路是單向的高速公路,有的是雙向的國道。如何在計算機中表示這張地圖?如何找到從起點到終點的所有可能路徑?這正是圖論要解決的核心問題。
在408考試中,圖論是數據結構部分的重頭戲,幾乎每年必考,不僅在選擇題中頻繁出現,更是算法設計題的重要考點。據統計,近5年的408真題中,有超過15次直接考察了圖的存儲和遍歷相關內容,其中DFS/BFS遍歷序列、拓撲排序更是高頻考點。
本文將幫你徹底掌握圖的基礎知識,包括兩種經典存儲結構的對比、深度優先和廣度優先遍歷的實現細節、連通性判斷以及拓撲排序的應用。
學完本文,你將能夠:
- ? 熟練選擇和實現圖的存儲結構
- ? 手寫DFS和BFS的遞歸與非遞歸代碼
- ? 快速判斷圖的連通性并求解拓撲序列
- ? 準確分析各種操作的時間復雜度
一、知識精講
1.1 概念定義
圖(Graph) 是由頂點集V和邊集E組成的數據結構,記為G=(V,E)。與線性表、樹不同,圖中的元素之間可以有任意的關系。
💡 核心概念對比:
- 有向圖 vs 無向圖:邊是否有方向性
- 完全圖:任意兩個頂點間都有邊(無向完全圖有n(n-1)/2條邊,有向完全圖有n(n-1)條邊)
- 稀疏圖 vs 稠密圖:通常|E|<|V|log|V|為稀疏圖,否則為稠密圖
- 連通圖:無向圖中任意兩頂點都有路徑;有向圖中為強連通圖
- 生成樹:包含全部頂點的極小連通子圖
?? 408考綱要求:
- 掌握:圖的存儲結構(鄰接矩陣、鄰接表)
- 掌握:圖的遍歷算法(DFS、BFS)
- 理解:圖的連通性、拓撲排序
- 了解:關鍵路徑、最短路徑(下一章重點)
1.2 原理分析
1.2.1 存儲結構原理
鄰接矩陣(Adjacency Matrix)
- 用二維數組A[n][n]表示,A[i][j]=1表示存在邊(i,j)
- 空間復雜度:O(n2),適合稠密圖
- 判斷邊存在:O(1)時間
- 獲取頂點度:O(n)時間
鄰接表(Adjacency List)
- 每個頂點對應一個鏈表,存儲所有鄰接點
- 空間復雜度:O(n+e),適合稀疏圖
- 判斷邊存在:O(degree)時間
- 獲取頂點度:O(1)或O(degree)時間
1.2.2 遍歷算法原理
深度優先搜索(DFS)
- 類似樹的先序遍歷,“不撞南墻不回頭”
- 使用棧(遞歸調用棧或顯式棧)
- 時間復雜度:O(n+e)鄰接表,O(n2)鄰接矩陣
廣度優先搜索(BFS)
- 類似樹的層序遍歷,“地毯式搜索”
- 使用隊列實現
- 時間復雜度:O(n+e)鄰接表,O(n2)鄰接矩陣
1.3 性質與特點
對比項 | 鄰接矩陣 | 鄰接表 |
---|---|---|
空間復雜度 | O(n2) | O(n+e) |
判斷邊(i,j) | O(1) | O(degree[i]) |
遍歷所有邊 | O(n2) | O(n+e) |
適用場景 | 稠密圖、邊頻繁查詢 | 稀疏圖、節省空間 |
408考頻 | ???? | ????? |
DFS vs BFS 特點對比:
- DFS:適合求解路徑問題、連通分量、拓撲排序
- BFS:適合求解最短路徑(無權圖)、層次遍歷
- DFS使用棧,空間O(n);BFS使用隊列,空間O(n)
- 兩者遍歷序列一般不唯一(408常考)
二、代碼實現
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAXV 100 // 最大頂點數// ========== 鄰接矩陣存儲結構 ==========
typedef struct {int vexnum, arcnum; // 頂點數和邊數int arcs[MAXV][MAXV]; // 鄰接矩陣char vexs[MAXV]; // 頂點信息
} MGraph;// ========== 鄰接表存儲結構 ==========
typedef struct ArcNode {int adjvex; // 鄰接點下標struct ArcNode *next; // 指向下一個鄰接點
} ArcNode;typedef struct VNode {char data; // 頂點信息ArcNode *first; // 指向第一個鄰接點
} VNode, AdjList[MAXV];typedef struct {AdjList vertices; // 鄰接表int vexnum, arcnum; // 頂點數和邊數
} ALGraph;// ========== 基本操作實現 ==========// 創建無向圖的鄰接矩陣
void CreateMGraph(MGraph *G) {printf("輸入頂點數和邊數: ");scanf("%d %d", &G->vexnum, &G->arcnum);// 初始化鄰接矩陣for (int i = 0; i < G->vexnum; i++) {for (int j = 0; j < G->vexnum; j++) {G->arcs[i][j] = 0; // 0表示無邊}}// 輸入邊信息for (int k = 0; k < G->arcnum; k++) {int i, j;printf("輸入第%d條邊的兩個頂點: ", k+1);scanf("%d %d", &i, &j);G->arcs[i][j] = 1; // 無向圖,對稱存儲G->arcs[j][i] = 1;}
}// 創建無向圖的鄰接表
void CreateALGraph(ALGraph *G) {printf("輸入頂點數和邊數: ");scanf("%d %d", &G->vexnum, &G->arcnum);// 初始化頂點表for (int i = 0; i < G->vexnum; i++) {G->vertices[i].data = 'A' + i; // 頂點命名G->vertices[i].first = NULL;}// 輸入邊信息,頭插法建立鄰接表for (int k = 0; k < G->arcnum; k++) {int i, j;printf("輸入第%d條邊的兩個頂點: ", k+1);scanf("%d %d", &i, &j);// 插入邊(i,j)ArcNode *p = (ArcNode*)malloc(sizeof(ArcNode));p->adjvex = j;p->next = G->vertices[i].first;G->vertices[i].first = p;// 無向圖,插入邊(j,i)ArcNode *q = (ArcNode*)malloc(sizeof(ArcNode));q->adjvex = i;q->next = G->vertices[j].first;G->vertices[j].first = q;}
}// ========== DFS遍歷(鄰接表版本)==========
bool visited[MAXV]; // 訪問標記數組void DFS(ALGraph *G, int v) {visited[v] = true;printf("%c ", G->vertices[v].data); // 訪問頂點v// 遍歷v的所有鄰接點ArcNode *p = G->vertices[v].first;while (p != NULL) {if (!visited[p->adjvex]) {DFS(G, p->adjvex); // 遞歸訪問未訪問的鄰接點}p = p->next;}
}// DFS遍歷主函數(處理非連通圖)
void DFSTraverse(ALGraph *G) {// 初始化訪問標記for (int i = 0; i < G->vexnum; i++) {visited[i] = false;}// 對每個連通分量調用DFSfor (int i = 0; i < G->vexnum; i++) {if (!visited[i]) {DFS(G, i);}}
}// ========== BFS遍歷(鄰接表版本)==========
void BFS(ALGraph *G, int v) {int queue[MAXV], front = 0, rear = 0; // 循環隊列visited[v] = true;printf("%c ", G->vertices[v].data);queue[rear++] = v; // v入隊while (front != rear) { // 隊列非空int u = queue[front++]; // 出隊// 遍歷u的所有鄰接點ArcNode *p = G->vertices[u].first;while (p != NULL) {if (!visited[p->adjvex]) {visited[p->adjvex] = true;printf("%c ", G->vertices[p->adjvex].data);queue[rear++] = p->adjvex; // 入隊}p = p->next;}}
}// BFS遍歷主函數
void BFSTraverse(ALGraph *G) {// 初始化訪問標記for (int i = 0; i < G->vexnum; i++) {visited[i] = false;}// 對每個連通分量調用BFSfor (int i = 0; i < G->vexnum; i++) {if (!visited[i]) {BFS(G, i);}}
}// ========== 拓撲排序(鄰接表)==========
bool TopologicalSort(ALGraph *G) {int indegree[MAXV] = {0}; // 入度數組int stack[MAXV], top = -1; // 棧int count = 0; // 已輸出頂點數// 計算所有頂點的入度for (int i = 0; i < G->vexnum; i++) {ArcNode *p = G->vertices[i].first;while (p != NULL) {indegree[p->adjvex]++;p = p->next;}}// 入度為0的頂點入棧for (int i = 0; i < G->vexnum; i++) {if (indegree[i] == 0) {stack[++top] = i;}}// 拓撲排序主過程while (top != -1) {int v = stack[top--]; // 出棧printf("%c ", G->vertices[v].data);count++;// 刪除v的所有出邊ArcNode *p = G->vertices[v].first;while (p != NULL) {indegree[p->adjvex]--;if (indegree[p->adjvex] == 0) {stack[++top] = p->adjvex; // 新的入度為0的頂點入棧}p = p->next;}}return count == G->vexnum; // 判斷是否有環
}
復雜度分析:
- DFS/BFS遍歷:時間O(n+e),空間O(n)
- 拓撲排序:時間O(n+e),空間O(n)
- 鄰接矩陣DFS/BFS:時間O(n2),空間O(n)
三、圖解說明
【圖1】DFS遍歷過程示意
初始圖: 步驟1(訪問A): 步驟2(訪問B): 步驟3(訪問D):A [A] [A] [A]/|\ /|\ /|\ /|\B C D B C D [B] C D [B] C [D]| | | | | | | |E F E F E F E F步驟4(訪問F): 步驟5(訪問C): 步驟6(訪問E):[A] [A] [A]/|\ /|\ /|\[B][C][D] [B][C][D] [B][C][D]| | | | | |E [F] E [F] [E] [F]DFS序列: A-B-D-F-C-E 或 A-C-F-D-B-E(序列不唯一)
【圖2】BFS遍歷過程示意
使用隊列:
步驟1: 隊列[A] 訪問A
步驟2: 隊列[B,C,D] 訪問B
步驟3: 隊列[C,D,E] 訪問C
步驟4: 隊列[D,E,F] 訪問D
步驟5: 隊列[E,F] 訪問E
步驟6: 隊列[F] 訪問FBFS序列: A-B-C-D-E-F(層序遍歷)
【圖3】存儲結構對比
原圖: 鄰接矩陣: 鄰接表:0---1 0 1 2 3 0 -> 1 -> 3|\ /| 0[0 1 1 1] 1 -> 0 -> 2 -> 3| X | 1[1 0 1 1] 2 -> 1 -> 3|/ \| 2[1 1 0 1] 3 -> 0 -> 1 -> 22---3 3[1 1 1 0]
四、真題演練
📝 真題1(2023年408第41題)
題目:對如下有向圖進行深度優先遍歷,假設從頂點1開始,且鄰接點按編號從小到大的順序訪問,則可能的DFS序列是?
解題思路:
- 從頂點1開始,標記visited[1]=true
- 訪問1的鄰接點(按編號順序):2、3、4
- 遞歸訪問2,再訪問2的鄰接點
- 回溯并繼續訪問其他未訪問頂點
標準答案:1-2-5-4-3-6(示例)
易錯點:
- ?? 忽略"按編號從小到大"的條件
- ?? 混淆DFS和BFS的訪問順序
📝 真題2(2022年408第23題)
題目:已知一個有向圖的鄰接表如下,從頂點0開始進行廣度優先遍歷,訪問序列是____。
解題思路:
- 初始化隊列Q,visited數組
- 頂點0入隊,visited[0]=true
- 0出隊,將0的所有未訪問鄰接點入隊
- 重復直到隊列為空
評分要點:
- 正確使用隊列(2分)
- 訪問標記正確(2分)
- 序列完整正確(3分)
📝 真題3(2021年408算法設計題)
題目:設計算法判斷有向圖是否存在環。
參考答案:
// 方法1:DFS+遞歸棧標記
bool hasCycleDFS(ALGraph *G) {int color[MAXV]; // 0:白色, 1:灰色, 2:黑色for(int i = 0; i < G->vexnum; i++) color[i] = 0;for(int i = 0; i < G->vexnum; i++) {if(color[i] == 0) {if(dfs(G, i, color)) return true;}}return false;
}// 方法2:拓撲排序
bool hasCycleTopo(ALGraph *G) {return !TopologicalSort(G); // 無法完成拓撲排序則有環
}
五、在線練習推薦
LeetCode精選題目
- 200. 島嶼數量(Medium,DFS/BFS經典)
- 207. 課程表(Medium,拓撲排序)
- 133. 克隆圖(Medium,圖的遍歷)
- 797. 所有可能的路徑(Medium,DFS)
牛客網408專項
- 圖的存儲與遍歷專項練習
- 2024考研真題模擬
練習順序建議
- 先練習基礎的DFS/BFS模板題
- 進階到連通分量、環檢測
- 掌握拓撲排序的應用
- 最后綜合練習圖論算法設計題
六、思維導圖
圖論基礎
├── 基本概念
│ ├── 有向圖/無向圖
│ ├── 完全圖/稀疏圖/稠密圖
│ ├── 連通性(連通圖/強連通圖)
│ └── 路徑/環/生成樹
├── 存儲結構
│ ├── 鄰接矩陣
│ │ ├── 二維數組實現
│ │ ├── 空間O(n2)
│ │ └── 適合稠密圖
│ └── 鄰接表
│ ├── 數組+鏈表實現
│ ├── 空間O(n+e)
│ └── 適合稀疏圖
├── 遍歷算法
│ ├── DFS深度優先
│ │ ├── 遞歸/棧實現
│ │ ├── 回溯思想
│ │ └── 時間O(n+e)
│ └── BFS廣度優先
│ ├── 隊列實現
│ ├── 層次遍歷
│ └── 最短路徑(無權)
└── 經典應用├── 連通性判斷├── 拓撲排序├── 環的檢測└── 強連通分量
七、復習清單
? 本章必背知識點清單
概念理解
- 能準確區分有向圖、無向圖、完全圖的定義
- 理解稀疏圖與稠密圖的區別(|E|<|V|log|V|)
- 掌握連通圖、強連通圖、連通分量的概念
- 記住完全圖的邊數公式(無向n(n-1)/2,有向n(n-1))
代碼實現
- 能手寫鄰接矩陣和鄰接表的結構定義
- 能手寫DFS的遞歸版本(5分鐘內)
- 能手寫BFS的隊列實現(5分鐘內)
- 掌握拓撲排序的完整代碼
- 記住DFS/BFS時間復雜度:鄰接表O(n+e),鄰接矩陣O(n2)
應用能力
- 會根據圖的特點選擇存儲結構
- 能手動模擬DFS/BFS遍歷過程
- 能判斷給定序列是否為合法的DFS/BFS序列
- 掌握用DFS判斷圖的連通性
- 掌握用拓撲排序判斷有向圖是否有環
真題要點
- 理解DFS/BFS序列不唯一的原因
- 掌握"按編號順序訪問"的處理方法
- 記住常見陷阱:未處理非連通圖
- 熟悉算法設計題的標準答題模板
八、知識拓展
🔍 常見誤區
-
誤區:認為DFS一定比BFS快
正解:兩者時間復雜度相同,選擇取決于具體問題 -
誤區:鄰接矩陣一定浪費空間
正解:對于稠密圖,鄰接矩陣反而更高效 -
誤區:拓撲排序結果唯一
正解:拓撲序列可能有多個
💡 記憶技巧
- DFS:想象走迷宮,一條路走到黑
- BFS:想象水波擴散,一圈一圈向外
- 鄰接表:稀疏(Sparse)用表(List)
- 拓撲排序:刪邊減度,入度為零就輸出
📊 自測題
-
一個有n個頂點的強連通圖至少有多少條邊?
A. n-1 B. n C. n+1 D. n(n-1) -
用鄰接表存儲有1000個頂點、2000條邊的有向圖,DFS遍歷的時間復雜度是?
A. O(1000) B. O(2000) C. O(3000) D. O(10002)
答案:1.B 2.C 3.C
結語
圖論是數據結構的核心內容,也是408考試的必考知識點。本章我們重點掌握了:
🎯 核心要點總結:
- 存儲結構選擇:稀疏圖用鄰接表,稠密圖用鄰接矩陣
- DFS本質:遞歸回溯,適合路徑搜索
- BFS本質:層次遍歷,適合最短路徑
- 拓撲排序:判環利器,AOV網的基礎
- 復雜度分析:永遠不要忘記O(n+e) vs O(n2)
圖的遍歷是后續學習最短路徑、最小生成樹的基礎。這些算法看似獨立,實際上都是DFS/BFS的變體和應用。下一篇文章,我們將深入探討**《圖論進階:最短路徑與最小生成樹》**,學習Dijkstra、Floyd、Prim、Kruskal等經典算法,這些都是408算法設計題的高頻考點。
💪 學習建議:圖論算法較為抽象,建議多畫圖模擬算法執行過程,多寫代碼加深理解。記住:圖論不難,關鍵在于把抽象的概念具象化!
加油,考研人!圖論雖然是難點,但也是拿高分的關鍵。掌握了圖論,你就掌握了408數據結構的半壁江山!🚀