当前位置：首页 > ops >正文

前端面试专栏-算法篇：23. 图结构与遍历算法

ops 2025/7/12 6:47:38

🔥 欢迎来到前端面试通关指南专栏！从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(V²)），但能快速判断任意两顶点是否相邻，如交通路网中查询两城市是否有直达航班。

基础遍历算法方面：