C++实现图的邻接矩阵与邻接表存储及DFS/BFS遍历算法详解

1. 项目概述：图的存储与遍历，算法能力的试金石

在数据结构与算法的学习道路上，图（Graph）无疑是一座承上启下的关键里程碑。它不像线性表那样简单直接，也不像树那样层次分明，图以其节点（顶点）和边构成的复杂网状关系，模拟了现实世界中社交网络、交通路网、任务调度等无数场景。这次实验的核心任务，就是用C++亲手实现图的两种主流存储方式（邻接矩阵与邻接表），并在此基础上完成深度优先搜索（DFS）和广度优先搜索（BFS）这两种最基础的图遍历算法。这不仅是完成一个课程实验，更是对抽象建模能力和算法实现功底的一次全面检验。很多同学在链表、树上感觉良好，一到图就“懵圈”，问题往往就出在存储结构没吃透，导致遍历逻辑混乱。通过这个实验，你将彻底打通从数据结构定义到算法执行的任督二脉，为后续学习最短路径、最小生成树等高级图算法打下坚实基础。

2. 核心数据结构设计与选型解析

图的存储，核心目标就两个：一是能准确表示顶点和边的关系，二是要便于后续遍历等操作的执行。邻接矩阵和邻接表是两种最经典的结构，选择哪一种，取决于你面对的图是“稠密”还是“稀疏”。

2.1 邻接矩阵：直观的“关系表格”

邻接矩阵的思想非常直观：用一个二维数组（矩阵）来表示图中顶点之间的邻接关系。假设图有V个顶点，我们就创建一个V x V的矩阵matrix。如果顶点i到顶点j之间存在一条边，那么matrix[i][j]的值就设为1（对于无权图）或边的权重（对于有权图）；如果不存在边，则设为0或一个特定的无穷大值。

C++实现要点：

#include <vector> using namespace std; class GraphMatrix { private: int numVertices; // 顶点数 vector<vector<int>> adjMatrix; // 邻接矩阵 bool isDirected; // 是否为有向图 public: // 构造函数 GraphMatrix(int V, bool directed = false) : numVertices(V), isDirected(directed) { // 初始化一个 V x V 的矩阵，所有元素为0 adjMatrix.resize(V, vector<int>(V, 0)); } // 添加边 void addEdge(int src, int dest, int weight = 1) { if (src >= 0 && src < numVertices && dest >= 0 && dest < numVertices) { adjMatrix[src][dest] = weight; if (!isDirected) { // 如果是无向图，对称位置也要设置 adjMatrix[dest][src] = weight; } } } // 打印矩阵 void printMatrix() { for (int i = 0; i < numVertices; ++i) { for (int j = 0; j < numVertices; ++j) { cout << adjMatrix[i][j] << " "; } cout << endl; } } };

为什么选择邻接矩阵？它的最大优点是查询任意两个顶点间是否存在边非常快，时间复杂度是O(1)。同时，对于稠密图（边数接近顶点数的平方），矩阵存储的空间利用率高。但它的致命缺点是空间复杂度为O(V²)，如果一个社交网络有10万用户，矩阵就需要100亿个存储单元，这显然是无法接受的。因此，邻接矩阵更适合顶点数不多、边非常稠密的图。

2.2 邻接表：高效的“关系链表”

邻接表是更常用、更节省空间的存储方式。它为图中的每一个顶点都维护一个链表（或动态数组），链表中存储的是与该顶点直接相邻的所有顶点。

C++实现要点（使用vector存储链表）：

#include <vector> #include <list> using namespace std; class GraphList { private: int numVertices; vector<list<int>> adjList; // 每个顶点对应一个链表（这里用list） // 或者使用 vector<vector<int>> adjList; 用动态数组也可 bool isDirected; public: GraphList(int V, bool directed = false) : numVertices(V), isDirected(directed) { adjList.resize(V); } void addEdge(int src, int dest) { if (src >= 0 && src < numVertices && dest >= 0 && dest < numVertices) { adjList[src].push_back(dest); if (!isDirected) { adjList[dest].push_back(src); // 无向图，双向添加 } } } // 打印邻接表 void printList() { for (int i = 0; i < numVertices; ++i) { cout << "顶点 " << i << " 的邻居: "; for (int neighbor : adjList[i]) { cout << neighbor << " "; } cout << endl; } } };

为什么选择邻接表？它的空间复杂度是O(V + E)，其中V是顶点数，E是边数。这对于边数远少于V²的稀疏图来说，节省了大量空间。查询某个顶点的所有邻居非常高效（直接遍历其链表），但查询任意两个顶点间是否有边，则需要遍历其中一个顶点的链表，时间复杂度为O(degree(V))。在实际应用中，如社交网络、网页链接关系，图几乎都是稀疏的，所以邻接表是绝对的主流选择。

实操心得：在实验或面试中，如果题目没有特别说明，默认使用邻接表。因为它更通用，性能更好。但在实现时要注意，vector<list>和vector<vector>各有优劣。list在中间插入删除更快，但内存不连续，遍历稍慢；vector内存连续，遍历快，但中间插入删除成本高。对于单纯的遍历操作，vector<vector>通常是更优选择，因为CPU缓存友好。我个人的习惯是：除非需要频繁在邻接表中部插入删除，否则优先用vector<vector>。

3. 深度优先搜索（DFS）算法实现与细节

深度优先搜索，顾名思义，就是“一条道走到黑”，探索到底再回头。它的核心思想是递归（或显式使用栈），非常适合解决“连通性”、“路径存在性”、“拓扑排序”等问题。

3.1 递归实现：最直观的思路

递归实现DFS非常符合其“深度优先”的语义。我们需要一个visited数组来记录哪些顶点已经被访问过，防止重复访问和陷入循环。

基于邻接表的DFS递归实现：

class GraphList { // ... 前面的成员变量和addEdge方法 private: void DFSUtil(int v, vector<bool>& visited) { // 标记当前顶点为已访问并输出 visited[v] = true; cout << v << " "; // 递归访问所有未访问的邻居 for (int neighbor : adjList[v]) { if (!visited[neighbor]) { DFSUtil(neighbor, visited); } } } public: void DFS(int startVertex) { // 初始化访问标记数组 vector<bool> visited(numVertices, false); // 为了防止非连通图，这里可以从startVertex开始。 // 如果需要遍历整个图，可以循环调用DFSUtil cout << "从顶点 " << startVertex << " 开始的DFS遍历: "; DFSUtil(startVertex, visited); cout << endl; // 遍历整个非连通图的写法： // vector<bool> visited(numVertices, false); // for (int i = 0; i < numVertices; ++i) { // if (!visited[i]) { // DFSUtil(i, visited); // } // } } };

算法逻辑拆解：

1. 访问顶点：进入一个顶点，首先标记为已访问，并处理（这里简单打印）。
2. 深入探索：对于该顶点的每一个邻居，如果邻居未被访问，则立即递归调用DFS函数访问该邻居。
3. 回溯：当某个顶点的所有邻居都被探索完毕（或没有未访问的邻居），函数调用栈会自动回溯到上一层顶点，继续检查其他邻居。

这个过程就像走迷宫，遇到岔路就选一条走到底，走到死胡同就退回上一个岔路口换另一条路。

3.2 显式栈实现：避免递归深度限制

递归虽然简洁，但当图非常大、深度很深时，可能会引起函数调用栈溢出。此时，我们可以用显式的栈（Stack）来模拟递归过程。

基于邻接表的DFS栈实现：

void DFS_Stack(int startVertex) { vector<bool> visited(numVertices, false); stack<int> s; // 起始顶点入栈 s.push(startVertex); cout << "基于栈的DFS遍历: "; while (!s.empty()) { int v = s.top(); s.pop(); // **关键点**：出栈时检查是否已访问 if (!visited[v]) { visited[v] = true; cout << v << " "; // 将当前顶点的所有邻居逆序入栈 // 逆序是为了保证遍历顺序与递归版本一致（先访问第一个邻居） // 如果顺序不重要，可以直接正序入栈 for (auto it = adjList[v].rbegin(); it != adjList[v].rend(); ++it) { if (!visited[*it]) { s.push(*it); } } } } cout << endl; }

为什么出栈后要检查visited？这是显式栈实现的一个关键陷阱。因为同一个顶点可能会被不同的邻居多次压入栈中。当我们第一次将它弹出并访问后，它就被标记为已访问。后续再弹出同一个顶点时，由于它已经被访问过，我们就应该跳过，否则会导致重复处理和逻辑错误。而在递归版本中，函数调用栈天然保证了每个顶点只进入一次。

注意事项：递归DFS的代码量少，逻辑清晰，是理解和书写时的首选。但在生产环境或处理大规模数据时，显式栈的实现更稳健。另外，DFS遍历的结果不唯一，它依赖于邻接表中邻居的存储顺序以及起始顶点。在实现时，如果需要特定的顺序（例如按顶点编号升序访问），需要在访问邻居前对其进行排序。

4. 广度优先搜索（BFS）算法实现与细节

广度优先搜索采用“层层推进”的策略，先访问起始顶点的所有直接邻居，然后再访问这些邻居的邻居，以此类推。它天然借助队列（Queue）来实现，非常适合求解“最短路径”（在无权图中）、“层级遍历”等问题。

4.1 队列实现：标准的层序遍历

BFS的标准实现离不开队列。队列“先进先出”的特性完美契合了“先发现的顶点先访问”的广度优先思想。

基于邻接表的BFS实现：

void BFS(int startVertex) { vector<bool> visited(numVertices, false); queue<int> q; // 初始化：访问起始顶点并入队 visited[startVertex] = true; q.push(startVertex); cout << "从顶点 " << startVertex << " 开始的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; }

算法逻辑拆解：

1. 初始化：将起始顶点标记为已访问，并放入队列。
2. 循环处理：只要队列不为空，就取出队首顶点进行处理（打印）。
3. 扩展 frontier：遍历刚取出顶点的所有邻居。对于每一个未访问的邻居，立即将其标记为已访问，然后放入队列末尾。
4. 重复：重复步骤2和3，直到队列为空，意味着所有从起始顶点可达的顶点都已访问完毕。

4.2 BFS与DFS的核心区别与应用场景

理解两者的区别，才能正确选用。

一个关键细节：标记访问的时机

• 在BFS中，必须在顶点入队时立即标记为visited。为什么？想象一下，顶点A和B都是顶点C的邻居。A先被访问，并将C放入队列。紧接着B被访问，如果此时C还未被标记，B又会将C放入队列一次。这样队列中就有两个C，导致重复访问和错误。入队时标记可以确保每个顶点只入队一次。
• 在DFS（递归）中，是在顶点被处理（进入递归函数）时标记。因为递归调用栈保证了路径的唯一性，不会出现同一个顶点通过不同路径同时进入调用栈的情况（在无向图中，通过父节点检查避免了走回头路）。在DFS（显式栈）版本中，则是在出栈后处理前标记，但需要检查是否已标记（如前所述）。

实操心得：在实现BFS时，visited标记在入队时完成，这是一个必须牢记的“铁律”，否则极易出错。另外，BFS常用于求无权图的最短路径。你可以在BFS过程中，额外维护一个distance数组，在将邻居入队时，设置distance[邻居] = distance[当前顶点] + 1。这样当BFS结束时，distance数组里就是从起点到各点的最短距离。这是BFS一个非常强大且实用的扩展。

5. 实验程序完整架构与测试用例设计

一个健壮、清晰的实验程序，不仅要有正确的算法核心，还需要良好的架构和全面的测试。

5.1 面向对象的程序架构

将图抽象成一个类，封装数据和方法，是C++中的最佳实践。

// Graph.h #ifndef GRAPH_H #define GRAPH_H #include <vector> #include <list> #include <queue> #include <stack> #include <iostream> using namespace std; enum GraphType { MATRIX, LIST }; class Graph { private: int numVertices; bool isDirected; GraphType type; // 邻接矩阵存储 vector<vector<int>> adjMatrix; // 邻接表存储 (使用vector<list>) vector<list<int>> adjList; // 私有工具函数 void DFSUtil_Matrix(int v, vector<bool>& visited); void DFSUtil_List(int v, vector<bool>& visited); void addEdge_Matrix(int src, int dest, int weight = 1); void addEdge_List(int src, int dest); public: // 构造函数 Graph(int V, bool directed = false, GraphType t = LIST); // 边操作接口 void addEdge(int src, int dest, int weight = 1); // 遍历接口 void DFS(int startVertex); void DFS_Stack(int startVertex); void BFS(int startVertex); // 辅助功能 void printGraph(); }; #endif // GRAPH_H

// Graph.cpp (部分关键实现) Graph::Graph(int V, bool directed, GraphType t) : numVertices(V), isDirected(directed), type(t) { if (type == MATRIX) { adjMatrix.resize(V, vector<int>(V, 0)); } else { // LIST adjList.resize(V); } } void Graph::addEdge(int src, int dest, int weight) { if (src < 0 || src >= numVertices || dest < 0 || dest >= numVertices) { cerr << "错误：顶点索引越界！" << endl; return; } if (type == MATRIX) { addEdge_Matrix(src, dest, weight); } else { addEdge_List(src, dest); } } // ... 其他成员函数的实现

这种设计允许用户在构造时选择存储方式，对外提供统一的接口addEdge,DFS,BFS，内部根据type自动分派到不同的实现。这体现了封装和多态的思想。

5.2 设计全面的测试用例

测试是验证程序正确性的关键。不要只用一个简单的图测试。

// main.cpp int main() { cout << "=== 测试用例1：无向图 (邻接表) ===" << endl; Graph g1(6, false, LIST); // 6个顶点，无向图，邻接表 g1.addEdge(0, 1); g1.addEdge(0, 2); g1.addEdge(1, 3); g1.addEdge(1, 4); g1.addEdge(2, 4); g1.addEdge(3, 5); g1.addEdge(4, 5); g1.printGraph(); g1.DFS(0); g1.BFS(0); cout << "\n=== 测试用例2：有向图 (邻接矩阵) ===" << endl; Graph g2(5, true, MATRIX); // 5个顶点，有向图，邻接矩阵 g2.addEdge(0, 1); g2.addEdge(0, 3); g2.addEdge(1, 2); g2.addEdge(2, 4); g2.addEdge(3, 1); g2.addEdge(4, 0); // 形成一个环 g2.printGraph(); g2.DFS_Stack(0); g2.BFS(0); cout << "\n=== 测试用例3：非连通图 ===" << endl; Graph g3(7, false, LIST); g3.addEdge(0, 1); g3.addEdge(0, 2); g3.addEdge(3, 4); g3.addEdge(5, 6); // 注意：当前的DFS/BFS接口只从指定起点遍历连通分量。 // 可以修改接口或循环调用以遍历整个图。 g3.DFS(0); g3.DFS(3); // 从另一个连通分量开始 return 0; }

测试用例设计要点：

1. 基础功能：小规模无向图，验证遍历序列是否符合预期（可以手动画图推导）。
2. 图类型：分别测试无向图和有向图。
3. 存储方式：分别测试邻接矩阵和邻接表实现。
4. 复杂结构：包含环的图，测试算法是否能正常终止，不会死循环。
5. 特殊图：非连通图，测试遍历是否只覆盖了一个连通分量（如果需要遍历全图，需修改代码循环调用）。
6. 边界条件：空图、单顶点图、只有边没有顶点（错误输入）等。

6. 常见问题排查与性能优化技巧

在实际编码和调试过程中，你肯定会遇到各种“坑”。这里总结几个最常见的问题和优化思路。

6.1 遍历陷入死循环或重复访问

这是图遍历中最常见的错误，根本原因都是visited数组使用不当。

• 症状：程序运行不结束，或输出大量重复顶点。
• 原因1（BFS）：没有在顶点入队时标记visited，导致同一顶点多次入队。
• 原因2（DFS递归）：处理无向图时，在递归函数中访问了父节点。例如，从顶点1访问邻居2，在顶点2的递归中又去访问邻居1，而1是2的父节点，本应跳过。
• 解决方案：
  • 对于BFS，严格遵守“入队即标记”原则。
  • 对于DFS递归，在遍历邻居时，可以传递一个parent参数，避免访问回父节点。但更通用的做法是依靠visited数组，因为一旦父节点被访问过，visited已为true，自然不会重复访问。关键在于确保在进入递归函数的第一时间就标记visited。

6.2 遍历顺序与预期不符

• 症状：程序输出的顶点顺序和教材、手动推导的不一样。
• 原因：图的遍历顺序不唯一。它依赖于：
  1. 邻接表中邻居的存储顺序（list的插入顺序或vector的排序）。
  2. 遍历算法的起始顶点。
  3. 在DFS显式栈实现中，邻居入栈的顺序（正序或逆序）。
• 解决方案：这不是错误。如果你需要确定的顺序（例如按顶点编号升序），可以在遍历每个顶点的邻居前，先对邻居列表进行排序（std::sort）。这会增加O(E log V)的时间复杂度，但保证了结果的可重复性。

6.3 内存与性能考量

• 稠密图用矩阵，稀疏图用表：这是基本原则。对于顶点数N超过1000的稀疏图，邻接矩阵的内存消耗是灾难性的。
• vector<list>vsvector<vector>：如前所述，vector<vector>在遍历时具有更好的缓存局部性，通常性能更优。使用list时，频繁的内存分配和指针跳转会带来开销。
• visited数组的选择：使用vector<bool>时要注意，标准库可能对其做特化（压缩存储），这可能导致某些位操作性能问题。在极端追求性能的场景下，可以使用vector<char>或vector<int>，但vector<bool>对于实验和大多数应用完全足够。
• 递归深度限制：DFS递归版本在深度很大的图（如一条长链）上可能导致栈溢出。在Windows上默认栈大小约1MB，在Linux上约8MB。如果预估递归深度可能超过数万层，应使用显式栈的非递归版本。

6.4 扩展思考：如何记录遍历路径？

单纯的遍历输出顶点序列有时不够。我们常常需要知道从起点到某个终点的具体路径。

实现思路（以DFS找一条路径为例）：

bool DFS_FindPath(int start, int target, vector<bool>& visited, vector<int>& path) { visited[start] = true; path.push_back(start); if (start == target) { return true; // 找到目标 } for (int neighbor : adjList[start]) { if (!visited[neighbor]) { if (DFS_FindPath(neighbor, target, visited, path)) { return true; // 如果子调用找到，直接返回 } } } // 此分支未找到，回溯 path.pop_back(); return false; }

在BFS中记录最短路径则需要维护一个parent数组，记录每个顶点的前驱节点，当找到目标后，从目标反向追溯到起点即可得到路径。

完成这个实验，你收获的远不止是两段可以运行的代码。你理解了图这种非线性结构的两种物理表示方法及其适用场景，掌握了DFS和BFS这两种最基础的图算法思想及其实现细节，并体验了从设计、编码到测试、调试的完整开发流程。下次当你再看到“最短路径”、“连通分量”这些词时，你会知道，它们都建立在今天实现的这些坚实基础之上。