前端面試專欄-算法篇：23. 圖結構與遍歷算法

🔥 歡迎來到前端面試通關指南專欄！從js精講到框架到實戰，漸進系統化學習，堅持解鎖新技能，祝你輕松拿下心儀offer。
前端面試通關指南專欄主頁
前端面試專欄規劃詳情

圖結構與遍歷算法

在計算機科學中，圖（Graph）是一種復雜的非線性數據結構，由頂點（Vertex）和邊（Edge）組成，用于描述元素之間多對多的關系。從社交網絡的用戶關系到地圖的路徑規劃，圖結構都有著廣泛的應用。本文將系統介紹圖的基本概念、存儲方式以及兩種核心遍歷算法——深度優先搜索（DFS）和廣度優先搜索（BFS），并結合實例講解其實現與應用。

一、圖的基本概念

1.1 圖的定義與組成

圖是由頂點集合（V）和邊集合（E）組成的二元組，記為 $G = (V, E)$ 。這種數據結構廣泛應用于計算機科學、數學、工程學和社會科學等領域。

頂點（Vertex）：
- 圖中的基本元素，也稱為節點（Node）
- 可表示具體對象：
  - 社交網絡中的用戶（如微信好友關系圖中的個人賬號）
  - 交通網絡中的地點（如百度地圖中的交叉路口或公交站點）
  - 計算機網絡中的設備（如路由器、服務器等）
- 頂點可帶有屬性信息，例如社交網絡中用戶的年齡、性別等元數據
邊（Edge）：
- 連接兩個頂點的線，表示頂點之間的關系
- 邊的類型包括：
  - 有向邊：帶有方向性的邊，用箭頭表示（如A→B）
    - 應用示例：微博的關注關系（A關注B不代表B關注A）
    - 表示單向關系：網頁的超鏈接、工作流中的任務依賴
  - 無向邊：沒有方向性的邊，用直線表示（如A-B）
    - 應用示例：微信好友關系（互為好友）
    - 表示雙向關系：社交網絡中的友誼、電路中的連接
- 邊可帶有權重：
  - 表示關系的強度或成本（如交通網絡中兩地的距離）
  - 示例：快遞路線規劃中的運輸成本、神經網絡中的連接權重

補充說明：

圖的數學形式化表示：
- 頂點集V = {v?, v?, …, v?}
- 邊集E ? V×V（對于有向圖）或E ? {{u,v} | u,v ∈ V}（對于無向圖）
特殊邊的類型：
- 自環邊：頂點連接到自身的邊
- 平行邊：兩個頂點間存在多條邊（在多重圖中允許）
圖的視覺表示：
- 通常用圓圈表示頂點
- 用連線表示邊
- 有向邊帶箭頭，無向邊無箭頭

應用場景示例：

互聯網網頁鏈接分析（有向圖）
城市公交線路規劃（可表示為帶權無向圖）
知識圖譜構建（帶屬性的異構圖）
電路板布線設計（平面圖）

1.2 圖的分類

無向圖

無向圖中的邊沒有方向性，表示頂點之間的雙向關系。例如在社交網絡中，好友關系可以用無向圖表示：如果用戶A和用戶B是好友，則存在邊(A,B)和(B,A)，這兩個邊在無向圖中被視為同一條邊。無向圖的鄰接矩陣是對稱矩陣，因為邊(A,B)和邊(B,A)表示同一個連接。

有向圖

有向圖的邊具有明確的方向性，表示單向關系。例如在網頁鏈接圖中，網頁A鏈接到網頁B表示為<A,B>，但這并不意味著網頁B會自動鏈接回網頁A。有向圖的鄰接矩陣通常不對稱。有向圖常用于表示流程、依賴關系等場景，如課程先修關系圖或任務調度圖。

加權圖

加權圖的邊帶有數值權重，用于量化頂點間關系的某些屬性。例如：

交通網絡中，邊權重可以表示兩地間的距離或通行時間
通信網絡中，邊權重可以表示帶寬或延遲
經濟網絡中，邊權重可以表示交易金額或關聯強度
加權圖可以是無向的（如雙向道路）或有向的（如單行道）。最短路徑算法（如Dijkstra算法）常應用于加權圖。

連通圖

對于無向圖：

連通圖：任意兩個頂點間都存在路徑。例如城市道路網如果是連通的，則可以從任意地點到達其他地點。
非連通圖：存在至少兩個頂點之間沒有路徑。例如孤立的島嶼與大陸的交通圖。

對于有向圖：

強連通圖：任意兩個頂點u和v之間存在u到v和v到u的路徑。例如閉合的循環供水系統。
弱連通圖：忽略方向后對應的無向圖是連通的。例如單向街道組成的城市道路網。
非連通圖：存在至少兩個頂點之間沒有任何路徑。例如多個獨立的有向循環系統。

特殊情形：

完全圖：每對不同的頂點之間都恰有一條邊相連。無向完全圖有n(n-1)/2條邊，有向完全圖有n(n-1)條邊。
稀疏圖/稠密圖：根據邊數與頂點數的比例劃分，通常邊數遠小于可能的最大邊數時為稀疏圖。

1.3 圖的基本術語

路徑

在圖論中，路徑是指從一個頂點到另一個頂點的一系列頂點序列，其中相鄰頂點之間必須通過邊連接。在有向圖中，路徑的方向必須與邊的方向保持一致。例如，在有向圖中若存在邊A→B和B→C，則A→B→C構成一條有效路徑，而A→C→B則不是（除非存在邊A→C和C→B）。

示例：

無向圖：在社交網絡中，用戶A通過共同好友B認識用戶C，可表示為路徑A-B-C。
有向圖：在網頁鏈接圖中，若網頁A鏈接到B，B鏈接到C，則A→B→C是一條有向路徑。

環

環（也稱為回路）是一種特殊的路徑，其起點和終點為同一頂點。環的存在可能表示系統中的循環依賴或重復關系。

示例：

交通網絡：若城市A到B有單向道路，B到C有單向道路，C又返回A，則A→B→C→A形成一個環。
任務調度：若任務X依賴任務Y，Y依賴任務Z，而Z又依賴X，則形成環，可能導致死鎖。

度

度是描述頂點連接性質的重要指標：

無向圖：一個頂點的度是其連接的邊的總數。例如，在社交網絡中，某用戶的度表示其好友數量。
有向圖：度分為兩類：
- 入度：指向該頂點的邊數。例如，在微博關注關系中，某用戶的入度表示其粉絲數。
- 出度：從該頂點出發的邊數。例如，某用戶的出度表示其關注的人數。

應用場景：

網頁排名：入度高的網頁可能更重要。
網絡中心性分析：度高的節點可能是關鍵樞紐。

二、圖的存儲方式

圖的存儲需高效表達頂點間的連接關系，常用方式有鄰接矩陣和鄰接表兩種。

2.1 鄰接矩陣（Adjacency Matrix）

鄰接矩陣是一種用二維數組表示圖結構的方法，適用于各種類型的圖（無向圖、有向圖、加權圖等）。其核心是通過矩陣的行列索引映射頂點，矩陣元素表示頂點間的關系。

存儲原理

對于一個包含 $n$ 個頂點的圖，鄰接矩陣是一個 $n \times n$ 的方陣，具體定義如下：

無向圖：矩陣對稱，matrix[i][j] = matrix[j][i]。值為1表示頂點 $i$ 和 $j$ 之間存在邊，0表示無邊。
- 例如社交網絡中的好友關系：若用戶A和B是好友，則對應矩陣位置置1。
有向圖：矩陣不對稱，matrix[i][j] = 1表示存在從頂點 $i$ 指向 $j$ 的邊。
- 例如網頁鏈接圖：網頁A鏈接到網頁B時，matrix[A][B] = 1。
加權圖：矩陣元素存儲具體權重值，無邊時通常用∞或特殊值（如-1）表示。
- 例如城市交通圖：matrix[i][j]可表示城市 $i$ 到 $j$ 的公路距離。

示例解析

以無向圖為例，頂點集合為{0,1,2,3}，其鄰接矩陣表示如下：

[[0, 1, 1, 0],  // 頂點0與1、2相連[1, 0, 1, 1],  // 頂點1與0、2、3相連[1, 1, 0, 1],  // 頂點2與0、1、3相連[0, 1, 1, 0]   // 頂點3與1、2相連
]

對應圖形化表示為：

      0/ \1---2\ /3

性能分析

優勢場景：

快速查詢：判斷任意兩頂點是否相鄰僅需 $O (1)$ 時間，適合頻繁查詢的場景。
稠密圖高效：當邊數接近 $n^2$ 時，空間利用率高。
算法適配：如Floyd-Warshall全源最短路徑算法直接依賴鄰接矩陣。

局限性：

空間消耗：空間復雜度固定為 $O(n^2)$ ，存儲1000個頂點的圖需要1MB空間（假設每元素占1字節）。
稀疏圖不適用：例如社交網絡中用戶平均好友數遠小于總用戶數時，矩陣中大量0值造成浪費。
動態操作成本高：添加/刪除頂點需重構整個矩陣。

擴展應用：

在GPU并行計算中，鄰接矩陣的規整結構利于加速矩陣運算。
可通過位壓縮技術（如位矩陣）優化稀疏圖的存儲。

2.2 鄰接表（Adjacency List）

鄰接表是一種常用的圖存儲結構，它為圖中的每個頂點維護一個鏈表（或動態數組），用于存儲與該頂點直接相連的所有頂點及相關的邊信息。這種結構特別適合表示稀疏圖（邊數遠小于頂點數平方的圖）。

數據結構實現方式

鏈表實現：每個頂點對應一個鏈表頭節點，后續節點存儲鄰接頂點信息
動態數組實現：現代編程語言中更常用，如C++的vector、Python的list
字典/哈希表實現：用頂點ID作為鍵，鄰接列表作為值

具體示例：無向圖的鄰接表表示

頂點0: [1, 2]       // 0與1、2相連
頂點1: [0, 2, 3]    // 1與0、2、3相連
頂點2: [0, 1, 3]    // 2與0、1、3相連
頂點3: [1, 2]       // 3與1、2相連

加權圖的鄰接表表示（存儲頂點和權重信息）：

頂點0: [(1, 5), (2, 3)]  // 0→1邊權重為5，0→2邊權重為3
頂點1: [(0, 5), (2, 2), (3, 6)]  // 1→0邊權重5，1→2邊權重2，1→3邊權重6
頂點2: [(0, 3), (1, 2), (3, 7)]
頂點3: [(1, 6), (2, 7)]

典型應用場景：

社交網絡中的好友關系存儲
路由算法中的網絡拓撲表示
稀疏矩陣的存儲優化

操作復雜度分析：

操作	時間復雜度	空間復雜度
添加頂點	O(1)	O(n)
添加邊	O(1)	O(1)
查詢相鄰頂點	O(1)	-
判斷兩頂點連接	O(k)	-

優缺點深入分析：

優點：
1. 空間效率高：僅存儲實際存在的邊，空間復雜度為 $O (n + e)$ （n為頂點數，e為邊數）
2. 遍歷效率高：獲取某頂點的所有鄰接點只需 $O (1)$ 時間
3. 動態擴展性好：添加新邊/頂點操作簡單
缺點：
1. 連接查詢慢：判斷頂點u和v是否相連需要 $O (k)$ 時間（k為頂點u的度）
2. 不適合頻繁的邊刪除操作（某些實現中）
3. 反向查詢困難：需要額外存儲逆鄰接表才能快速找到"指向"某頂點的邊

優化變體：

十字鏈表：有向圖的優化存儲
鄰接多重表：無向圖的優化存儲
跳表實現：加速連接查詢

三、圖的遍歷算法

圖的遍歷是按某種規則訪問所有頂點，核心算法為深度優先搜索（DFS）和廣度優先搜索（BFS）。

3.1 深度優先搜索（DFS）

算法思想

從起點出發，優先深入探索路徑，直到無法前進時回溯，繼續探索其他分支。類似“走迷宮時沿一條路走到頭，再回頭嘗試其他路”。

實現方式

遞歸：利用函數調用棧記錄路徑。
棧：手動維護棧存儲待訪問頂點。

步驟

訪問起點，標記為已訪問。
遍歷起點的未訪問鄰接頂點，選一個深入遞歸（或入棧）。
重復步驟2，直到無未訪問鄰接頂點，回溯到上一頂點繼續探索。

代碼實現（鄰接表+遞歸）

class Graph {constructor() {this.adjList = new Map(); // 鄰接表：key為頂點，value為鄰接頂點數組}// 添加頂點addVertex(v) {if (!this.adjList.has(v)) {this.adjList.set(v, []);}}// 添加邊（無向圖）addEdge(v, w) {this.adjList.get(v).push(w);this.adjList.get(w).push(v);}// DFS遞歸實現dfs(start) {const visited = new Set(); // 記錄已訪問頂點const result = [];const dfsRecursive = (v) => {visited.add(v);result.push(v);// 遍歷所有未訪問的鄰接頂點for (const neighbor of this.adjList.get(v)) {if (!visited.has(neighbor)) {dfsRecursive(neighbor);}}};dfsRecursive(start);return result;}
}// 測試
const graph = new Graph();
graph.addVertex('A');
graph.addVertex('B');
graph.addVertex('C');
graph.addVertex('D');
graph.addVertex('E');graph.addEdge('A', 'B');
graph.addEdge('A', 'C');
graph.addEdge('B', 'D');
graph.addEdge('C', 'E');console.log('DFS遍歷結果:', graph.dfs('A')); // 輸出: ['A', 'B', 'D', 'C', 'E']（路徑可能因鄰接順序變化）

3.2 廣度優先搜索（BFS）

算法思想

從起點出發，優先訪問所有鄰接頂點，再按同樣規則訪問下一層次頂點。類似“水波擴散”，逐層向外遍歷。

實現方式

隊列：使用隊列存儲待訪問頂點，保證按層次順序訪問。

步驟

訪問起點，標記為已訪問，入隊。
出隊一個頂點，遍歷其所有未訪問鄰接頂點，標記后入隊。
重復步驟2，直到隊列為空。

代碼實現（鄰接表+隊列）

// 基于上述Graph類，添加BFS方法
bfs(start) {const visited = new Set();const result = [];const queue = [start]; // 隊列初始化visited.add(start);while (queue.length > 0) {const v = queue.shift(); // 出隊result.push(v);// 遍歷所有未訪問的鄰接頂點，入隊for (const neighbor of this.adjList.get(v)) {if (!visited.has(neighbor)) {visited.add(neighbor);queue.push(neighbor);}}}return result;
}// 測試
console.log('BFS遍歷結果:', graph.bfs('A')); // 輸出: ['A', 'B', 'C', 'D', 'E']（層次順序固定）

3.3 DFS與BFS對比

特性	DFS（深度優先搜索）	BFS（廣度優先搜索）
數據結構	使用棧結構（或遞歸調用棧），后進先出的特性適合深度探索	使用隊列結構，先進先出的特性保證按層次遍歷
訪問順序	沿著一條分支深入到底（如：二叉樹的先序遍歷），可能跳躍訪問不同分支	按層次逐步擴散（如：二叉樹的層序遍歷），完全訪問完當前層才會進入下一層
空間復雜度	$O (h)$ （ $h$ 為樹高或遞歸深度），如：平衡二叉樹為 $O(log?n)O(\log n)$ ，鏈狀結構為 $O (n)$	$O (w)$ （ $w$ 為樹/圖的最大寬度），如：完全二叉樹最后一層節點數約為 $n /2$
適用場景	- 尋找可行路徑（如迷宮問題） - 拓撲排序（有向無環圖） - 檢測環 - 連通性分析	- 無權圖最短路徑（邊權相同） - 社交網絡關系擴散 - 多連通分量識別 - 廣播網絡
典型應用	1. 八皇后問題 2. 數獨求解 3. 文件系統遍歷（遞歸實現） 4. 語法分析	1. Dijkstra算法基礎（無權圖） 2. 網頁爬蟲抓取策略 3. 傳染病傳播模型 4. 網絡路由
實現示例	`python<br>def dfs(node):<br> visit(node)<br> for child in node.children:<br> dfs(child)<br>`	`python<br>def bfs(root):<br> queue = [root]<br> while queue:<br> node = queue.pop(0)<br> visit(node)<br> queue.extend(node.children)<br>`
優劣對比	優勢：內存消耗較小劣勢：不一定找到最短路徑	優勢：保證找到最短路徑劣勢：存儲空間需求較大
特殊變體	迭代加深DFS（IDDFS）結合兩者優勢	雙向BFS從起點和終點同時搜索

四、圖遍歷的應用場景

連通分量檢測：
- 用于識別圖中相互獨立的子圖集合，每個子圖內的頂點相互可達，不同子圖間完全隔離
- 算法實現：
  - 初始化所有頂點為未訪問狀態
  - 循環選取未訪問頂點，執行DFS/BFS遍歷
  - 每次完整遍歷產生的頂點集合即為一個連通分量
- 典型場景：
  - 社交網絡分析（識別不同用戶圈子）
  - 電網連通性檢測（找出獨立供電區域）
  - 示例：在10萬用戶的社交網絡中，通過DFS發現3個主要連通分量，分別對應工作圈、同學圈和親友圈
拓撲排序：
- 針對有向無環圖(DAG)的線性排序，滿足對于任意有向邊(u→v)，u總出現在v之前
- 實現方法：
  - DFS后序遍歷的逆序
  - 卡恩算法（基于入度表迭代移除入度為0的頂點）
- 應用案例：
  - 課程體系規劃（必須先完成數據結構才能學習算法分析）
  - 軟件構建依賴管理（需先編譯底層模塊）
  - 任務調度系統（前置任務必須優先執行）
最短路徑求解：
- 無權圖處理：
  - BFS天然形成層次結構，起點到各頂點的最短路徑長度等于遍歷層次
  - 示例：地鐵換乘查詢中，站點間最短換乘次數計算
- 加權圖處理：
  - Dijkstra算法（要求非負權重）：
    1. 維護優先隊列按距離排序
    2. 每次擴展距離起點最近的頂點
    3. 時間復雜度O(E+VlogV)
  - 典型應用：
    - 導航系統路線規劃
    - 網絡數據傳輸路由選擇
網絡爬蟲：
- DFS策略：
  - 沿著鏈接深度優先抓取，適合垂直領域爬取
  - 可能陷入無限深度，需設置最大深度閾值
  - 示例：學術論文爬蟲追蹤參考文獻鏈條
- BFS策略：
  - 優先抓取與種子頁面直接相連的網頁
  - 保證重要頁面優先被抓取
  - 示例：新聞網站爬取時先抓取首頁鏈接的所有新聞
- 混合策略：
  - 初期使用BFS建立索引，后期針對特定區域采用DFS
二分圖判斷：
- 定義驗證：能否用兩種顏色標記頂點，使相鄰頂點顏色不同
- 算法步驟：
  1. 選取任意頂點著紅色
  2. 其鄰居著藍色，依此類推
  3. 若發現相鄰頂點同色則非二分圖
- 實際應用：
  - 人員-崗位匹配（應聘者與合適職位）
  - 學生選課系統（學生與可選課程）
  - 廣告投放匹配（用戶畫像與廣告類型）
- 擴展應用：
  - 利用二分圖性質解決最大匹配問題（匈牙利算法）
  - 社交網絡好友推薦（避免推薦已有好友）

五、總結

圖結構作為一種重要的非線性數據結構，是描述實體間復雜關系網絡的強大工具。在計算機科學領域，圖的存儲方式主要有兩種經典實現：

鄰接表：采用鏈表結構存儲每個節點的相鄰節點，適用于稀疏圖（邊數遠小于頂點數平方的情況）。其空間復雜度為O(V+E)，在社交網絡（如好友關系）、網頁鏈接等場景表現優異。例如，Facebook的好友關系圖采用鄰接表存儲，可高效查詢某個用戶的所有直接好友。
鄰接矩陣：使用二維數組表示頂點間的連接關系，適用于稠密圖。雖然空間復雜度較高（O(V2)），但能快速判斷任意兩頂點是否相鄰，如交通路網中查詢兩城市是否有直達航班。

基礎遍歷算法方面：