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; // 顶点数 vectorvectorint adjMatrix; // 邻接矩阵 bool isDirected; // 是否为有向图 public: // 构造函数 GraphMatrix(int V, bool directed false) : numVertices(V), isDirected(directed) { // 初始化一个 V x V 的矩阵所有元素为0 adjMatrix.resize(V, vectorint(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; vectorlistint adjList; // 每个顶点对应一个链表这里用list // 或者使用 vectorvectorint 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))。在实际应用中如社交网络、网页链接关系图几乎都是稀疏的所以邻接表是绝对的主流选择。实操心得在实验或面试中如果题目没有特别说明默认使用邻接表。因为它更通用性能更好。但在实现时要注意vectorlist和vectorvector各有优劣。list在中间插入删除更快但内存不连续遍历稍慢vector内存连续遍历快但中间插入删除成本高。对于单纯的遍历操作vectorvector通常是更优选择因为CPU缓存友好。我个人的习惯是除非需要频繁在邻接表中部插入删除否则优先用vectorvector。3. 深度优先搜索DFS算法实现与细节深度优先搜索顾名思义就是“一条道走到黑”探索到底再回头。它的核心思想是递归或显式使用栈非常适合解决“连通性”、“路径存在性”、“拓扑排序”等问题。3.1 递归实现最直观的思路递归实现DFS非常符合其“深度优先”的语义。我们需要一个visited数组来记录哪些顶点已经被访问过防止重复访问和陷入循环。基于邻接表的DFS递归实现class GraphList { // ... 前面的成员变量和addEdge方法 private: void DFSUtil(int v, vectorbool visited) { // 标记当前顶点为已访问并输出 visited[v] true; cout v ; // 递归访问所有未访问的邻居 for (int neighbor : adjList[v]) { if (!visited[neighbor]) { DFSUtil(neighbor, visited); } } } public: void DFS(int startVertex) { // 初始化访问标记数组 vectorbool visited(numVertices, false); // 为了防止非连通图这里可以从startVertex开始。 // 如果需要遍历整个图可以循环调用DFSUtil cout 从顶点 startVertex 开始的DFS遍历: ; DFSUtil(startVertex, visited); cout endl; // 遍历整个非连通图的写法 // vectorbool visited(numVertices, false); // for (int i 0; i numVertices; i) { // if (!visited[i]) { // DFSUtil(i, visited); // } // } } };算法逻辑拆解访问顶点进入一个顶点首先标记为已访问并处理这里简单打印。深入探索对于该顶点的每一个邻居如果邻居未被访问则立即递归调用DFS函数访问该邻居。回溯当某个顶点的所有邻居都被探索完毕或没有未访问的邻居函数调用栈会自动回溯到上一层顶点继续检查其他邻居。这个过程就像走迷宫遇到岔路就选一条走到底走到死胡同就退回上一个岔路口换另一条路。3.2 显式栈实现避免递归深度限制递归虽然简洁但当图非常大、深度很深时可能会引起函数调用栈溢出。此时我们可以用显式的栈Stack来模拟递归过程。基于邻接表的DFS栈实现void DFS_Stack(int startVertex) { vectorbool visited(numVertices, false); stackint 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) { vectorbool visited(numVertices, false); queueint 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; }算法逻辑拆解初始化将起始顶点标记为已访问并放入队列。循环处理只要队列不为空就取出队首顶点进行处理打印。扩展 frontier遍历刚取出顶点的所有邻居。对于每一个未访问的邻居立即将其标记为已访问然后放入队列末尾。重复重复步骤2和3直到队列为空意味着所有从起始顶点可达的顶点都已访问完毕。4.2 BFS与DFS的核心区别与应用场景理解两者的区别才能正确选用。特性深度优先搜索 (DFS)广度优先搜索 (BFS)数据结构栈 (递归调用栈或显式栈)队列遍历顺序一条路径深入到底再回溯按距离起始点的层次一层一层访问空间复杂度O(h)h为递归深度/图的最大深度。对于“瘦长”的图省空间。O(w)w为图的最大宽度。对于“宽扁”的图省空间。经典应用拓扑排序、连通分量检测、路径查找不关心最短、解决迷宫找到一条路即可无权图的最短路径、层级遍历、社交网络中查找“度”分离的关系、广播网络结果唯一性不唯一依赖邻接顺序从固定起点开始结果是唯一的假设邻接顺序固定一个关键细节标记访问的时机在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; // 邻接矩阵存储 vectorvectorint adjMatrix; // 邻接表存储 (使用vectorlist) vectorlistint adjList; // 私有工具函数 void DFSUtil_Matrix(int v, vectorbool visited); void DFSUtil_List(int v, vectorbool 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, vectorint(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; }测试用例设计要点基础功能小规模无向图验证遍历序列是否符合预期可以手动画图推导。图类型分别测试无向图和有向图。存储方式分别测试邻接矩阵和邻接表实现。复杂结构包含环的图测试算法是否能正常终止不会死循环。特殊图非连通图测试遍历是否只覆盖了一个连通分量如果需要遍历全图需修改代码循环调用。边界条件空图、单顶点图、只有边没有顶点错误输入等。6. 常见问题排查与性能优化技巧在实际编码和调试过程中你肯定会遇到各种“坑”。这里总结几个最常见的问题和优化思路。6.1 遍历陷入死循环或重复访问这是图遍历中最常见的错误根本原因都是visited数组使用不当。症状程序运行不结束或输出大量重复顶点。原因1BFS没有在顶点入队时标记visited导致同一顶点多次入队。原因2DFS递归处理无向图时在递归函数中访问了父节点。例如从顶点1访问邻居2在顶点2的递归中又去访问邻居1而1是2的父节点本应跳过。解决方案对于BFS严格遵守“入队即标记”原则。对于DFS递归在遍历邻居时可以传递一个parent参数避免访问回父节点。但更通用的做法是依靠visited数组因为一旦父节点被访问过visited已为true自然不会重复访问。关键在于确保在进入递归函数的第一时间就标记visited。6.2 遍历顺序与预期不符症状程序输出的顶点顺序和教材、手动推导的不一样。原因图的遍历顺序不唯一。它依赖于邻接表中邻居的存储顺序list的插入顺序或vector的排序。遍历算法的起始顶点。在DFS显式栈实现中邻居入栈的顺序正序或逆序。解决方案这不是错误。如果你需要确定的顺序例如按顶点编号升序可以在遍历每个顶点的邻居前先对邻居列表进行排序std::sort。这会增加O(E log V)的时间复杂度但保证了结果的可重复性。6.3 内存与性能考量稠密图用矩阵稀疏图用表这是基本原则。对于顶点数N超过1000的稀疏图邻接矩阵的内存消耗是灾难性的。vectorlistvsvectorvector如前所述vectorvector在遍历时具有更好的缓存局部性通常性能更优。使用list时频繁的内存分配和指针跳转会带来开销。visited数组的选择使用vectorbool时要注意标准库可能对其做特化压缩存储这可能导致某些位操作性能问题。在极端追求性能的场景下可以使用vectorchar或vectorint但vectorbool对于实验和大多数应用完全足够。递归深度限制DFS递归版本在深度很大的图如一条长链上可能导致栈溢出。在Windows上默认栈大小约1MB在Linux上约8MB。如果预估递归深度可能超过数万层应使用显式栈的非递归版本。6.4 扩展思考如何记录遍历路径单纯的遍历输出顶点序列有时不够。我们常常需要知道从起点到某个终点的具体路径。实现思路以DFS找一条路径为例bool DFS_FindPath(int start, int target, vectorbool visited, vectorint 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这两种最基础的图算法思想及其实现细节并体验了从设计、编码到测试、调试的完整开发流程。下次当你再看到“最短路径”、“连通分量”这些词时你会知道它们都建立在今天实现的这些坚实基础之上。