1. 项目概述：为什么图的遍历是算法世界的“导航系统”

在C++的世界里，数据结构是构建复杂程序的骨架，而图（Graph）无疑是其中最复杂、也最贴近现实世界关系的一种。想象一下，你面前有一张巨大的地铁线路图，站点是节点，轨道是边。你想从“家”这个站去到“公司”站，有多少种换乘方案？哪条路线最快？或者，你想探索整个地铁网络的所有站点，是先一条线坐到底再换线，还是每到一站就先把能换乘的线路都坐一遍？这两种截然不同的探索策略，就是我们今天要深入骨髓去理解的深度优先搜索（DFS）和广度优先搜索（BFS）。

很多朋友初学数据结构，学到链表、栈、队列都觉得还能跟上，一碰到图就开始发怵，更别提DFS和BFS了。网上教程要么一上来就甩出一段递归代码让人云里雾里，要么只讲理论不接地气，导致大家记住了名字却不知道到底该怎么用、什么时候用。我自己在早期做项目时，就曾因为用错了遍历方式，导致在一个社交网络关系分析的程序里，找两个人的最短联系路径时，程序像钻进了死胡同，效率低得令人发指。后来才明白，不是算法不行，是我没理解它们各自的“性格”。

这篇内容，我就以一个老码农的身份，带你彻底拆解DFS和BFS。我们不玩虚的，直接从图的两种最常用存储方式（邻接矩阵和邻接表）开始，用C++手把手实现它们。然后，我们会像解剖麻雀一样，分析DFS那种“不撞南墙不回头”的递归与栈实现，以及BFS那种“层层递进、雨露均沾”的队列实现。更重要的是，我会分享在哪些实际场景下（比如迷宫求解、社交网络、编译器依赖分析）应该选择DFS，哪些场景下（比如最短路径、广播消息、网络爬虫）必须用BFS，以及那些教科书里不会写的性能陷阱和调试技巧。

无论你是正在啃《数据结构》课本的学生，还是准备面试急需梳理算法的求职者，抑或是工作中突然需要处理图关系数据的工程师，这篇文章都能给你一套可直接运行、能真正理解背后思想的代码和思路。我们不止步于“是什么”，更要深挖“为什么”和“怎么用得好”。

2. 图的基石：两种存储方式的选择与C++实现

在讨论怎么“走”图之前，我们必须先解决图怎么“存”的问题。存储结构选对了，后续的遍历算法才能写得清晰、跑得高效。主流有两种方式：邻接矩阵和邻接表。它们的关系，有点像数组和链表，一个胜在查询快，一个赢在空间省。

2.1 邻接矩阵：直观的“城市间航班表”

邻接矩阵用一个二维数组（在C++中常用vector<vector<int>>）来表示图。假设图有V个顶点，我们就创建一个V x V的矩阵graph。如果顶点i和顶点j之间存在一条边，那么graph[i][j]的值就设为1（对于无权图）或边的权重（对于有权图）；如果不存在边，则设为0或一个特定的无效值（如INT_MAX）。

它的优点极其明显：

1. 查询速度极快：判断任意两个顶点u和v之间是否有边，直接访问graph[u][v]，时间复杂度是O(1)。
2. 实现简单：结构非常规整，对于稠密图（边数接近顶点数平方）来说，空间利用率高。
3. 方便计算：某些基于矩阵运算的图算法（如通过计算矩阵幂来求路径数）天然适合。

但缺点也同样突出：

1. 空间消耗大：空间复杂度是O(V²)。对于一个有10000个顶点的稀疏社交网络图，如果用它存储，需要1亿个存储单元，其中绝大部分是0，这是巨大的浪费。
2. 添加/删除顶点麻烦：动态增加顶点需要重新分配和拷贝整个矩阵，成本高。

C++实现示例（无向图）：

#include <iostream> #include <vector> using namespace std; class GraphMatrix { private: int V; // 顶点数 vector<vector<int>> adjMatrix; // 邻接矩阵 bool isDirected; // 是否为有向图 public: // 构造函数，初始化V x V的矩阵，所有元素为0 GraphMatrix(int numVertices, bool directed = false) : V(numVertices), isDirected(directed) { adjMatrix.resize(V, vector<int>(V, 0)); } // 添加边（无权图） void addEdge(int u, int v) { if (u >= V || v >= V) { cerr << "顶点索引超出范围!" << endl; return; } adjMatrix[u][v] = 1; if (!isDirected) { // 如果是无向图，对称位置也设为1 adjMatrix[v][u] = 1; } } // 打印邻接矩阵 void printMatrix() { for (int i = 0; i < V; ++i) { for (int j = 0; j < V; ++j) { cout << adjMatrix[i][j] << " "; } cout << endl; } } // 获取邻接矩阵（供遍历算法使用） const vector<vector<int>>& getMatrix() const { return adjMatrix; } int getNumVertices() const { return V; } };

注意：在工程中，对于纯无权图，可以用vector<vector<bool>>来节省空间；对于有权图，则用vector<vector<int>>或vector<vector<double>>。同时，务必在构造函数或添加边时进行边界检查，防止数组越界——这是初级程序员最容易栽跟头的地方之一。

2.2 邻接表：高效的“朋友的朋友列表”

邻接表是更常用、更节省空间的存储方式，尤其适用于稀疏图。它为图中的每一个顶点都维护一个链表（在C++中，常用vector<int>或list<int>），这个链表里存储了所有与该顶点直接相邻的顶点。

它的优点正好弥补了邻接矩阵的缺点：

1. 空间复杂度低：存储所有边需要O(V + E)的空间，其中E是边数。对于稀疏图，这比O(V²)好太多了。
2. 遍历效率高：要找出一个顶点的所有邻居，直接遍历其对应的链表即可，这在DFS/BFS中非常高效。
3. 动态增删灵活：添加边和顶点相对容易。

缺点是：

1. 查询边是否存在较慢：判断边(u, v)是否存在，需要遍历u的邻接链表，时间复杂度是O(degree(u))，最坏情况是O(V)。
2. 实现稍复杂：结构不如矩阵直观。

C++实现示例（使用vector模拟邻接表）：

#include <iostream> #include <vector> using namespace std; class GraphList { private: int V; vector<vector<int>> adjList; // 邻接表，每个顶点对应一个vector bool isDirected; public: GraphList(int numVertices, bool directed = false) : V(numVertices), isDirected(directed) { adjList.resize(V); } // 添加边 void addEdge(int u, int v) { if (u >= V || v >= V) { cerr << "顶点索引超出范围!" << endl; return; } adjList[u].push_back(v); if (!isDirected && u != v) { // 无向图且不是自环 adjList[v].push_back(u); } } // 打印邻接表 void printList() { for (int i = 0; i < V; ++i) { cout << "顶点 " << i << " 的邻居: "; for (int neighbor : adjList[i]) { cout << neighbor << " "; } cout << endl; } } // 获取邻接表（供遍历算法使用） const vector<vector<int>>& getList() const { return adjList; } int getNumVertices() const { return V; } };

实操心得：在大多数算法竞赛和实际工程中，邻接表是默认首选。除非你明确知道图非常稠密，或者需要频繁进行任意两点间是否存在边的查询，否则都用邻接表。用vector<vector<int>>实现邻接表在缓存友好性和访问速度上通常优于list<int>。另外，如果顶点有复杂的属性（如字符串名称），通常会用一个数组或vector存储顶点属性，并用顶点索引来关联邻接表。

3. 深度优先搜索（DFS）：一条道走到黑的“探险家”

DFS的策略，就像你走迷宫时的“右手法则”：遇到岔路，随便选一条路（通常按固定顺序）一直走下去，直到走进死胡同，然后退回上一个岔路口，尝试另一条没走过的路。这种策略天然适合用递归来实现，因为“前进”和“回退”正好对应了递归的“递”和“归”。

3.1 递归实现：最直观的思维映射

递归实现DFS的代码非常简洁，几乎就是算法定义的直接翻译。

核心步骤：

1. 从起始顶点s开始。
2. 将s标记为“已访问”。
3. 对于s的每一个未访问的邻居顶点v：
   • 递归调用DFS(v)。

C++实现（基于邻接表）：

#include <iostream> #include <vector> using namespace std; class DFSGraph { private: int V; const vector<vector<int>>& adjList; // 引用外部构造好的邻接表 vector<bool> visited; // 访问标记数组 // 递归的核心函数 void DFSUtil(int v) { // 1. 标记当前顶点为已访问 visited[v] = true; cout << v << " "; // 执行访问操作，这里简单打印 // 2. 递归访问所有未访问的邻居 for (int neighbor : adjList[v]) { if (!visited[neighbor]) { DFSUtil(neighbor); } } } public: // 构造函数，接收顶点数和邻接表 DFSGraph(int numVertices, const vector<vector<int>>& list) : V(numVertices), adjList(list), visited(V, false) {} // 对外的DFS遍历接口 void traverseDFS(int startVertex) { // 重置访问标记（如果进行多次遍历） fill(visited.begin(), visited.end(), false); cout << "从顶点 " << startVertex << " 开始的DFS遍历顺序: "; DFSUtil(startVertex); cout << endl; // 处理非连通图的情况：遍历所有顶点 // for (int i = 0; i < V; ++i) { // if (!visited[i]) { // DFSUtil(i); // } // } } };

调用示例：

int main() { GraphList g(5); // 创建一个有5个顶点的无向图 g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 4); DFSGraph dfsWalker(5, g.getList()); dfsWalker.traverseDFS(0); // 从顶点0开始DFS // 输出可能为：从顶点 0 开始的DFS遍历顺序: 0 1 3 4 2 // 注意：顺序取决于邻接表中边的存储顺序 return 0; }

关键点解析：

1. 访问标记数组visited：这是所有图遍历算法的灵魂。必须有一个全局或类成员的数据结构（通常是vector<bool>）来记录每个顶点是否被访问过，防止重复访问陷入无限循环。
2. 递归的隐式栈：递归调用过程，系统会自动使用函数调用栈来保存每一层的状态（返回地址、局部变量等）。当深入探索到尽头时，通过函数返回自动实现“回溯”。
3. 遍历顺序的不确定性：DFS的输出顺序不唯一，它依赖于你访问邻居顶点的顺序（即邻接表中边的存储顺序）。上面的代码访问邻居的顺序就是adjList[v]中元素的顺序。

3.2 显式栈实现：理解递归的本质

递归虽然优雅，但在图非常深（比如链状图）的情况下，可能导致栈溢出。我们可以用显式的栈（stack<int>）来模拟递归过程，将递归转化为迭代。这能帮助你更深刻地理解DFS“后进先出”的特性。

迭代DFS步骤：

1. 将起始顶点s压入栈，并标记为已访问。
2. 当栈不为空时： a. 弹出栈顶顶点v。 b. 访问v（如果是在弹出时访问）。 c. 将v的所有未访问的邻居顶点压入栈，并标记为已访问。

C++实现：

#include <iostream> #include <vector> #include <stack> using namespace std; void DFS_Iterative(int startVertex, const vector<vector<int>>& adjList, int V) { vector<bool> visited(V, false); stack<int> s; // 起始顶点入栈并标记 s.push(startVertex); visited[startVertex] = true; // 注意：入栈时标记，避免同一顶点重复入栈 cout << "迭代DFS遍历顺序: "; while (!s.empty()) { int v = s.top(); s.pop(); cout << v << " "; // 在弹出时访问 // 注意：这里需要将邻居逆序入栈，以模拟与递归相同的访问顺序 // 因为栈是LIFO，而递归是正序调用 // 如果想和递归顺序一致，可以反向遍历邻居 for (auto it = adjList[v].rbegin(); it != adjList[v].rend(); ++it) { int neighbor = *it; if (!visited[neighbor]) { visited[neighbor] = true; s.push(neighbor); } } } cout << endl; }

注意事项与心得：

1. 标记时机是坑：在迭代DFS中，必须在顶点入栈时立即标记为已访问，而不是在弹出时。否则，同一个顶点可能会被其他路径重复压入栈中多次，导致重复访问和栈空间浪费。这是和递归版本（在访问函数开头标记）一个很重要的区别。
2. 顺序问题：由于栈是后进先出，为了得到和上面递归示例（正序访问邻居）相同的输出顺序，我们需要将当前顶点的邻居逆序压入栈。如果对顺序没要求，正序压入即可。
3. 访问时机：递归DFS是在“进入”顶点时访问（前序），而上面的迭代版本是在“离开”（弹出）顶点时访问。如果你想在迭代中也实现“进入时访问”，可以在入栈后、while循环开始前访问起始顶点，并在循环内、弹出顶点后立即访问。但这通常不影响DFS解决问题的本质。

3.3 DFS的核心应用场景与实战技巧

理解了DFS怎么走，更要明白它适合去哪。DFS的“深度优先”特性，让它擅长解决以下几类问题：

1. 连通性检测与路径查找：判断两个顶点是否连通，或者找出一条从起点到终点的路径（不一定是最短）。DFS会沿着一条分支深入，一旦找到目标就返回，非常适合“是否存在”这类问题。
2. 拓扑排序：用于有向无环图（DAG）中，安排任务的执行顺序。通过对图进行DFS，并记录顶点的完成时间（或逆后序），可以得到一个合法的拓扑序列。这是编译器安排指令、构建系统安排编译任务的基础。
3. 寻找图的连通分量：在无向图中，一次DFS遍历所能到达的所有顶点构成一个连通分量。对未访问的顶点反复调用DFS，就能找出图的所有连通分量。
4. 检测环：在无向图中，如果DFS过程中遇到了已访问的顶点，并且这个顶点不是当前顶点的父节点，那么就存在环。在有向图中，还需要一个额外的“在递归栈中”的标记来检测环。
5. 解决回溯问题：DFS是回溯算法（如八皇后、数独、全排列）的骨架。将问题状态空间视为一个图，DFS就是在系统地探索所有可能的状态路径。

实战技巧：在DFS中记录路径很多时候，我们不仅要知道能否到达，还要知道怎么到达的。这需要在DFS过程中维护一个路径信息。

// 递归DFS，记录从起点到任意点的路径 bool DFS_FindPath(int current, int target, const vector<vector<int>>& adjList, vector<bool>& visited, vector<int>& path) { visited[current] = true; path.push_back(current); // 将当前节点加入路径 if (current == target) { return true; // 找到目标，路径在path中 } for (int neighbor : adjList[current]) { if (!visited[neighbor]) { if (DFS_FindPath(neighbor, target, adjList, visited, path)) { return true; // 如果子调用找到了，直接返回true，不再尝试其他邻居 } } } // 当前节点的所有邻居都走不通，回溯，从路径中移除当前节点 path.pop_back(); return false; }

踩坑记录：DFS找到的路径是一条可行路径，但不一定是最短路径。如果你需要最短路径，请使用BFS或专门的最短路径算法（如Dijkstra）。我曾在一个游戏地图寻路功能中错误地使用了DFS，结果角色经常贴着地图边缘绕远路，被玩家吐槽“人工智能，人工智障”，后来换成BFS就正常了。

4. 广度优先搜索（BFS）：层层推进的“广播塔”

如果说DFS是专注的探险家，那BFS就是高效的广播站。它的策略是从起点开始，先访问所有距离为1的邻居（第一层），再访问所有距离为2的邻居（第二层），以此类推。这种“地毯式”搜索，保证了它第一次访问到某个顶点时，走过的路径一定是从起点到该顶点的最短路径（在边权为1的无权图中）。

4.1 队列实现：公平的“先来后到”

BFS的实现必须借助队列（Queue）这种“先进先出”的数据结构，这完美契合了“先访问的顶点，其邻居也先被访问”的逻辑。

核心步骤：

1. 将起始顶点s入队，并标记为已访问。
2. 当队列不为空时： a. 出队一个顶点v。 b. 访问v。 c. 将v的所有未访问的邻居顶点入队，并标记为已访问。

C++实现（基于邻接表）：

#include <iostream> #include <vector> #include <queue> using namespace std; void BFS(int startVertex, const vector<vector<int>>& adjList, int V) { vector<bool> visited(V, false); queue<int> q; // 起始顶点入队并标记 visited[startVertex] = true; q.push(startVertex); cout << "BFS遍历顺序: "; while (!q.empty()) { int v = q.front(); q.pop(); cout << v << " "; // 访问出队的顶点 // 将所有未访问的邻居入队 for (int neighbor : adjList[v]) { if (!visited[neighbor]) { visited[neighbor] = true; // 入队前标记！ q.push(neighbor); } } } cout << endl; }

调用示例（沿用之前的图）：

int main() { GraphList g(5); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(1, 4); g.addEdge(2, 4); BFS(0, g.getList(), 5); // 输出：BFS遍历顺序: 0 1 2 3 4 // 顺序是：0（第0层） -> 1, 2（第1层） -> 3, 4（第2层） return 0; }

关键点解析：

1. 队列的作用：队列保证了顶点按“被发现”的先后顺序被访问，从而实现了层次遍历。
2. 标记时机：和迭代DFS一样，必须在顶点入队时立即标记。如果等到出队时才标记，同一个顶点可能会被多个已访问的顶点重复发现并多次入队，虽然最终不会重复访问（因为出队时会检查），但队列中会充斥大量重复元素，严重浪费空间和时间，在稠密图上可能导致队列爆炸。
3. 路径最短性：BFS遍历树中，从根（起点）到任意节点的路径就是原图中的最短路径。我们可以通过记录每个顶点的“前驱”或“距离”来还原这条路径。

4.2 记录层数与最短路径

BFS的一个强大功能是能轻松计算从起点到所有其他顶点的最短距离（边权为1）。

改进的BFS，记录距离：

#include <iostream> #include <vector> #include <queue> using namespace std; vector<int> BFS_Distance(int startVertex, const vector<vector<int>>& adjList, int V) { vector<bool> visited(V, false); vector<int> distance(V, -1); // -1 表示不可达 queue<int> q; visited[startVertex] = true; distance[startVertex] = 0; // 起点到自己的距离为0 q.push(startVertex); while (!q.empty()) { int v = q.front(); q.pop(); for (int neighbor : adjList[v]) { if (!visited[neighbor]) { visited[neighbor] = true; distance[neighbor] = distance[v] + 1; // 邻居的距离是当前顶点距离+1 q.push(neighbor); } } } return distance; } int main() { GraphList g(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 3); g.addEdge(2, 4); g.addEdge(3, 5); g.addEdge(4, 5); vector<int> dist = BFS_Distance(0, g.getList(), 6); for (int i = 0; i < 6; ++i) { cout << "从0到顶点" << i << "的最短距离: " << dist[i] << endl; } // 输出示例： // 从0到顶点0的最短距离: 0 // 从0到顶点1的最短距离: 1 // 从0到顶点2的最短距离: 1 // 从0到顶点3的最短距离: 2 (通过0->1->3或0->2->3) // 从0到顶点4的最短距离: 2 (0->2->4) // 从0到顶点5的最短距离: 3 (0->2->4->5 或 0->1->3->5) return 0; }

4.3 BFS的核心应用场景

BFS的“广度优先”特性，让它成为解决以下问题的利器：

1. 无权图的最短路径：如上所示，这是BFS最经典的应用。比如社交网络中计算两个人之间的最少介绍人次数（六度空间理论），或者棋盘游戏中棋子移动到目标位置的最少步数。
2. 广播或层级传播：模拟消息在网络中的传播、病毒感染的扩散、火焰在网格上的蔓延等。BFS能清晰地展现出每一轮（每一层）影响的范围。
3. 网络爬虫的层级抓取：爬虫从种子URL开始，先抓取该页面的所有链接（第一层），再抓取这些链接页面中的所有链接（第二层），以此类推。BFS能控制抓取的深度。
4. 二分图检测：BFS可以给顶点交替染色，用来检测一个图是否是二分图（即顶点集可以分成两个独立集，使得同一集内的顶点不相邻）。
5. 寻找连通分量：和DFS一样，BFS也可以用于寻找无向图的连通分量。

5. DFS与BFS的深度对比与选型指南

光知道怎么实现还不够，在实际问题中能准确选择用DFS还是BFS，才是真正掌握了它们。下面这个表格从多个维度进行了对比：

选型决策流程图（简化）：

1. 问题是否要求“最短”、“最少步数”？
   • 是-> 优先考虑BFS。
   • 否-> 进入下一步。
2. 图的结构是否非常深（如长链状），且空间有限？
   • 是-> 谨慎使用递归DFS，考虑迭代DFS或BFS（如果宽度不大）。
   • 否-> 进入下一步。
3. 是否需要探索所有可能解（如排列组合），或判断是否存在一条路径？
   • 是->DFS（特别是回溯法）更合适。
   • 否-> 进入下一步。
4. 问题是否涉及任务依赖、编译顺序？
   • 是-> 使用基于DFS的拓扑排序。
   • 否-> 两者通常都可，根据编码习惯或额外约束选择。

一个综合例子：迷宫求解

• 问题A：判断迷宫是否有出口-> 用DFS或BFS都可以，找到一个就行。
• 问题B：找到迷宫的最短出口路径->必须用BFS。
• 问题C：找出迷宫的所有出口路径-> 用DFS（回溯）来记录所有路径。

6. 常见问题、调试技巧与性能优化实录

在实际编码和面试中，总会遇到一些坑。这里记录几个最常见的问题和我的解决心得。

6.1 为什么我的遍历陷入了死循环？

这是新手最常遇到的问题，根本原因几乎都是：忘记了使用visited访问标记数组，或者标记的时机不对。

• 递归DFS：必须在递归函数一开始就标记当前顶点为已访问。
• 迭代DFS：必须在顶点入栈时标记。
• BFS：必须在顶点入队时标记。

调试技巧：在开发过程中，可以在访问（打印）顶点时，同时打印visited数组的状态，或者打印栈/队列的内容，清晰看到算法的执行过程。对于复杂的图，可以先用一个只有3-5个顶点的小图来测试。

6.2 非连通图的遍历

上面的示例代码默认图是连通的。如果图是非连通的（由多个互不连通的子图构成），从某个起点开始的一次DFS或BFS只能遍历它所在的连通分量。为了遍历整个图，我们需要用一个外层循环来驱动。

void traverseEntireGraph(const vector<vector<int>>& adjList, int V) { vector<bool> visited(V, false); int componentCount = 0; for (int i = 0; i < V; ++i) { if (!visited[i]) { componentCount++; cout << "连通分量 " << componentCount << ": "; // 可以选择用DFS或BFS遍历这个分量 // 这里以DFS递归为例 DFSUtil(i, adjList, visited); // 需要修改DFSUtil函数，接受visited引用 cout << endl; } } cout << "图共有 " << componentCount << " 个连通分量。" << endl; }

6.3 处理大规模图时的性能考量

当图的顶点数（V）和边数（E）达到百万甚至千万级别时，每一个细微的实现差异都可能被放大。

1. 数据结构选择：

   • vector<vector<int>>作为邻接表在大多数情况下是最优的，因为内存连续，缓存友好。避免使用list<int>，它的指针跳转对缓存不友好。
   • visited数组用vector<bool>，但注意vector<bool>是特化模板，可能不是真正的布尔数组。对性能有极致要求时，可以考虑用vector<char>或bitset。

2. 递归深度限制：

   • 系统栈空间有限（通常几MB）。对于深度可能很大的图（如一条长链），递归DFS有栈溢出风险。
   • 解决方案：使用显式栈的迭代DFS。或者，在能预估深度且环境允许的情况下，调整编译器栈大小（如g++的-Wl,--stack,size参数）。

3. BFS队列内存：

   • 在极端宽（如星型图）的图上，BFS的队列可能在某一层存储几乎所有的顶点，内存消耗为O(V)。
   • 如果内存紧张，可以考虑使用双向BFS（从起点和终点同时开始搜索），当两个搜索 frontier 相遇时停止。这能显著减少搜索空间，尤其是在知道目标顶点的情况下。

4. 并行化可能：

   • BFS的每一层内部，对顶点的处理通常是独立的，这为并行化提供了可能。可以使用OpenMP等工具并行处理同一层顶点的邻居探索。而DFS由于强烈的顺序依赖，并行化困难得多。

6.4 如何优雅地处理顶点属性（非整数索引）？

我们之前的例子都用整数0, 1, 2...作为顶点索引。但现实中，顶点可能是字符串（如城市名）、对象等。

标准做法是建立映射：

#include <iostream> #include <vector> #include <unordered_map> #include <string> using namespace std; class GraphWithNames { private: unordered_map<string, int> nameToIndex; vector<string> indexToName; vector<vector<int>> adjList; int getOrCreateIndex(const string& name) { if (nameToIndex.find(name) == nameToIndex.end()) { int newIndex = indexToName.size(); nameToIndex[name] = newIndex; indexToName.push_back(name); adjList.push_back(vector<int>()); // 为新的顶点增加邻接表 } return nameToIndex[name]; } public: void addEdge(const string& u, const string& v) { int idxU = getOrCreateIndex(u); int idxV = getOrCreateIndex(v); // 防止重复添加边（根据需求可选） if (find(adjList[idxU].begin(), adjList[idxU].end(), idxV) == adjList[idxU].end()) { adjList[idxU].push_back(idxV); // 如果是无向图，还需要 adjList[idxV].push_back(idxU); } } void BFS(const string& start) { if (nameToIndex.find(start) == nameToIndex.end()) return; int startIdx = nameToIndex[start]; int V = indexToName.size(); vector<bool> visited(V, false); queue<int> q; visited[startIdx] = true; q.push(startIdx); cout << "BFS from " << start << ": "; while (!q.empty()) { int vIdx = q.front(); q.pop(); cout << indexToName[vIdx] << " "; for (int neighborIdx : adjList[vIdx]) { if (!visited[neighborIdx]) { visited[neighborIdx] = true; q.push(neighborIdx); } } } cout << endl; } };

这套映射机制（nameToIndex,indexToName）是处理非整数顶点标识的通用模式，在后续学习更高级的图算法时也会经常用到。

图的遍历是打开图算法大门的钥匙，DFS和BFS则是这把钥匙上最重要的两个齿。理解它们的本质差异——一个用栈追求深度，一个用队列追求广度——并能在具体问题中做出正确选择，你的算法工具箱里就多了两件趁手的兵器。多写，多画图（在纸上画出遍历过程），多思考“如果换一种遍历方式会怎样”，是掌握它们的不二法门。