有向图邻接矩阵实现：从存储结构到DFS/BFS遍历详解

1. 从零开始理解有向图：为什么它无处不在？

如果你接触过任何与网络、流程或依赖关系相关的编程问题，那么“图”这个概念你一定不陌生。而“有向图”，则是图论中最基础、最核心，也是应用最广泛的结构之一。它远不止是教科书上的一个抽象概念，而是我们解决现实问题的强大思维模型。简单来说，有向图就是由一组“顶点”和一组带有方向的“边”构成的集合。每条边从一个顶点指向另一个顶点，清晰地定义了关系的方向性。

这个“方向性”是其灵魂所在。想想看，网页之间的超链接（A页面链接到B页面）、社交网络中的关注关系（你关注了某人，但对方未必关注你）、任务之间的依赖（编译代码前必须先安装依赖库）、甚至是交通网络中的单行道，这些都是天然的有向图。理解有向图，就等于掌握了一把解开这些复杂系统内在联系的钥匙。对于开发者而言，无论是设计一个微服务间的调用拓扑，还是优化一个工作流引擎，有向图的相关算法都是必须装备的核心技能。

在算法面试和实际工程中，有向图的遍历、环检测、拓扑排序、最短路径等问题更是高频考点。很多人觉得图算法难，往往是因为一开始就被抽象的数学定义和复杂的实现吓退了。其实，只要我们找到一个直观的切入点，从“如何用代码表示它”开始，一步步拆解，就会发现它的脉络非常清晰。本文，我将以一个从业多年的工程师视角，带你从最基础的图类设计与邻接矩阵实现入手，彻底搞懂有向图的存储与核心操作，为后续学习更复杂的算法打下坚实基础。

2. 图的基石：如何选择与实现存储结构？

当我们决定用程序来处理一个图时，面临的第一个也是最关键的问题就是：如何在计算机内存中表示它？这个选择直接决定了后续所有算法的实现效率和编码复杂度。对于顶点数不多（比如题目中限制的小于10个）的场景，我们主要有两种经典选择：邻接矩阵和邻接表。这里，我们聚焦于邻接矩阵，因为它最直观，也最适合作为理解图存储的起点。

2.1 邻接矩阵 vs. 邻接表：一次彻底的选择分析

邻接矩阵是一个n x n的二维数组（通常叫matrix或adj），其中n是顶点个数。如果存在一条从顶点i指向顶点j的边，那么matrix[i][j] = 1（对于有权图，则存储权重值）；否则为0（或一个表示无穷大的特殊值）。

它的优点非常突出：

1. 直观清晰：矩阵本身就是一个表格，matrix[i][j]的值直接回答了“从i到j有没有边？”这个问题。检查任意两个顶点间是否存在边，时间复杂度是惊人的 O(1)。
2. 实现简单：特别是对于稠密图（边数接近顶点数的平方），邻接矩阵的空间利用率高，代码也简洁。
3. 便于计算：一些基于矩阵运算的图算法（如图的幂运算求路径数）天然适合用邻接矩阵。

但缺点同样明显：

1. 空间开销大：需要 O(n²) 的空间。当顶点数 n 很大时（例如上万个），这个开销是难以承受的。这也是为什么在处理大规模稀疏图（边数远小于 n²）时，邻接表是更优的选择。
2. 遍历邻居效率低：要找出顶点v的所有出边，你需要扫描矩阵的第v整行，即使它只有一两个邻居，也需要 O(n) 的时间。而邻接表可以做到 O(邻居个数)。

对于我们的学习场景——顶点数小于10，邻接矩阵的空间开销完全可以忽略不计，而其带来的代码清晰度和理解上的便利性是巨大的。因此，我们选择用它作为入门实现。

2.2 构建图类：封装与初始化细节

明确了存储结构，我们就可以开始设计一个DirectedGraph类。好的封装不仅能让我们用起来舒服，更能保证图数据的一致性。

首先，我们需要决定顶点的标识。虽然题目中提到“节点分别用1”，但在内部实现中，使用从0开始的连续整数索引是更通用的做法，这样可以方便地直接用作数组下标。对外，我们可以按需映射（比如显示时+1）。

class DirectedGraph { private: int numVertices; // 顶点数，记为 n int numEdges; // 边数，记为 m vector<vector<int>> adjMatrix; // 邻接矩阵 public: // 构造函数：初始化一个具有n个顶点的图，初始时没有边 DirectedGraph(int n) : numVertices(n), numEdges(0) { // 初始化一个 n x n 的矩阵，所有元素为0 adjMatrix.resize(n, vector<int>(n, 0)); } // 添加一条从 u 指向 v 的边（注意：内部索引从0开始） void addEdge(int u, int v) { // 输入合法性检查 if (u < 0 || u >= numVertices || v < 0 || v >= numVertices) { cerr << "Error: Vertex index out of range!" << endl; return; } // 防止重复添加边（根据具体问题需求，有时允许重复边或权重叠加） if (adjMatrix[u][v] == 0) { adjMatrix[u][v] = 1; // 对于有权图，这里应赋值权重 numEdges++; } else { // 可以打印日志，或者如果是带权图则更新权重 // cout << "Edge (" << u << "->" << v << ") already exists." << endl; } } // 获取顶点数 int getNumVertices() const { return numVertices; } // 获取边数 int getNumEdges() const { return numEdges; } // 判断是否存在从 u 到 v 的边 bool hasEdge(int u, int v) const { if (u < 0 || u >= numVertices || v < 0 || v >= numVertices) return false; return adjMatrix[u][v] != 0; } // 获取邻接矩阵的引用（只读），用于遍历或算法 const vector<vector<int>>& getAdjMatrix() const { return adjMatrix; } };

关键细节与踩坑点：

1. 索引从0开始：这是C++/Java等语言中数组的天然特性。坚持内部从0开始，能避免大量“下标-1”的转换，减少错误。仅在输入输出时进行映射。
2. 输入验证：在addEdge中检查顶点索引是否越界是必须的。一个健壮的类应该能处理无效输入，而不是直接崩溃。
3. 重复边处理：这是初学者常忽略的。我们的实现选择忽略重复添加的边（adjMatrix[u][v]从0变为1只发生一次），这符合简单有向图的定义。但在某些应用（如统计调用次数）中，你可能需要累加。明确你的图模型很重要。
4. 空间初始化：在构造函数中一次性resize并填充0，比在添加边时动态调整要高效和清晰得多。

2.3 从用户输入构建图：一个完整的流程示例

有了图类，我们需要一个方法来从标准输入（如控制台）构建它。这个过程虽然简单，但隐藏着一些决定代码是否健壮的细节。

DirectedGraph buildGraphFromInput() { int n, m; cout << "Enter number of vertices (n < 10): "; cin >> n; cout << "Enter number of edges (m): "; cin >> m; // 输入校验 if (n <= 0 || n >= 10) { // 根据题目要求 n<10 cerr << "Invalid number of vertices. Must be 1 <= n < 10." << endl; exit(1); // 或抛出异常 } if (m < 0 || m > n * (n - 1)) { // 有向图最多可能有 n*(n-1) 条边 cerr << "Invalid number of edges." << endl; exit(1); } DirectedGraph graph(n); cout << "Enter " << m << " edges (format: u v), where vertices are from 1 to " << n << ":" << endl; for (int i = 0; i < m; ++i) { int u, v; cin >> u >> v; // 将用户输入的1-based索引转换为0-based内部索引 u--; v--; graph.addEdge(u, v); } return graph; }

实操心得：

• 交互提示：清晰的提示信息（cout）能让用户（或调试时的你自己）知道该输入什么，尤其是在输入格式固定时。
• 严格的输入校验：这是区分“玩具代码”和“健壮代码”的关键。校验n和m的范围可以提前发现数据错误。例如，有向简单图的最大边数是n*(n-1)（每个顶点到其他所有顶点各一条边）。如果m超过这个值，输入数据肯定有问题。
• 索引转换：在输入循环中集中进行u--; v--;转换，比在图类的每个方法里处理要清晰。这明确了边界：图类内部统一使用0-based索引，输入输出层负责转换。

3. 核心操作一：深度优先搜索遍历有向图

存储结构搭建好后，我们终于可以开始“探索”这个图了。遍历是图算法中最基础的操作，如同树的遍历一样。对于有向图，深度优先搜索因其天然的递归性质和解决后续问题的扩展性，成为我们必须掌握的第一个算法。

3.1 DFS递归实现：深入探索每一条路径

DFS的策略是“一条路走到黑，没路了再回头”。对于有向图，我们从某个起点出发，沿着它的出边不断深入，直到当前顶点没有未被访问过的出边，然后回溯到上一个顶点，尝试其他出边。

class DirectedGraph { // ... 之前的成员变量和方法 ... private: void dfsUtil(int v, vector<bool>& visited) { // 标记当前顶点为已访问 visited[v] = true; cout << (v + 1) << " "; // 输出时转换回1-based，方便阅读 // 遍历当前顶点的所有出边邻居 for (int neighbor = 0; neighbor < numVertices; ++neighbor) { // 如果存在从 v 到 neighbor 的边，且 neighbor 未被访问 if (adjMatrix[v][neighbor] != 0 && !visited[neighbor]) { dfsUtil(neighbor, visited); } } // 递归结束，自动回溯 } public: // 对外的DFS入口，处理图可能不连通的情况 void dfs(int startVertex) { if (startVertex < 0 || startVertex >= numVertices) { cerr << "Invalid start vertex!" << endl; return; } vector<bool> visited(numVertices, false); cout << "DFS starting from vertex " << (startVertex + 1) << ": "; dfsUtil(startVertex, visited); cout << endl; } // 完整的图遍历：即使从某个点开始无法到达所有点，也保证每个顶点都被检查到 void dfsFull() { vector<bool> visited(numVertices, false); cout << "DFS full traversal: "; for (int v = 0; v < numVertices; ++v) { if (!visited[v]) { dfsUtil(v, visited); } } cout << endl; } };

为什么递归实现是教学首选？递归代码非常简洁地反映了DFS“深度优先”的核心思想。dfsUtil函数完美诠释了“访问当前节点，然后对其每一个未访问的邻居递归调用自身”这个过程。对于初学者，理解递归调用栈如何模拟了“探索”和“回溯”是至关重要的。

3.2 DFS迭代实现：显式使用栈

递归虽然优雅，但在极端深度很大的图上可能导致栈溢出。迭代实现使用显式的栈数据结构，逻辑同样清晰。

void DirectedGraph::dfsIterative(int startVertex) { if (startVertex < 0 || startVertex >= numVertices) return; vector<bool> visited(numVertices, false); stack<int> s; s.push(startVertex); cout << "DFS (Iterative) from vertex " << (startVertex + 1) << ": "; while (!s.empty()) { int v = s.top(); s.pop(); // 注意：因为栈是LIFO，这里需要在pop后检查是否已访问 // 同一个顶点可能被多次压入栈（通过不同的路径），但只需处理一次 if (!visited[v]) { visited[v] = true; cout << (v + 1) << " "; // 将邻居逆序压栈，使得遍历顺序与递归版更接近（先访问下标小的邻居） // 邻接矩阵遍历是0到n-1，正序压栈会导致遍历顺序相反 for (int neighbor = numVertices - 1; neighbor >= 0; --neighbor) { if (adjMatrix[v][neighbor] != 0 && !visited[neighbor]) { s.push(neighbor); } } } } cout << endl; }

迭代实现的几个关键点：

1. 已访问检查的时机：在pop出栈顶元素后立即检查。因为一个顶点可能通过不同路径被多次压入栈中，我们只处理第一次真正访问它的时候。
2. 邻居压栈顺序：为了模拟递归版本“先遇到的邻居先深入”的行为，我们需要将邻居逆序压栈。因为栈是“后进先出”，最后压入的会最先被弹出访问。如果我们按0到n-1的顺序压栈，那么n-1会先被访问，这与递归的顺序相反。逆序压栈可以保证顺序一致（虽然DFS的结果序列不唯一，但这是一个有益的细节）。
3. 空间复杂度：显式栈的空间复杂度在最坏情况下也是 O(n)，与递归的调用栈深度相同。

3.3 DFS的应用：环检测与拓扑排序的基石

DFS遍历本身不是目的，它是实现更高级算法的基础。在有向图中，DFS遍历过程中顶点的状态变化，为我们提供了两个极其重要的信息：

• 顶点的发现与完成时间：我们可以记录每个顶点进入递归（discover）和退出递归（finish）的时刻。
• 递归栈上的顶点：在递归调用dfsUtil的过程中，所有尚未返回的顶点构成了一个从起点到当前点的路径。

利用这两点，我们可以进行有向图的环检测。如果在探索从顶点u到邻居v的边时，发现v正处于“已发现但未完成”的状态（即v在当前的递归栈中），那么就存在一条从v回到u的路径，加上u->v这条边，就形成了一个环。这是判断有向无环图的关键。

而拓扑排序，正是对有向无环图所有顶点的一种线性排序，使得对于任何一条有向边u->v，u在排序中都出现在v之前。利用DFS的完成时间，一个非常巧妙的实现是：在dfsUtil函数退出时，将当前顶点压入一个栈。当整个DFS遍历结束后，将栈中元素依次弹出，得到的序列就是一个逆拓扑序。我们将在后续章节详细探讨。

踩坑经验：遍历顺序的“不确定性”很多初学者会纠结DFS的输出顺序为什么和书上的例子不一样。需要明确：DFS的遍历结果不是唯一的。它取决于你访问邻居的顺序。在我们的邻接矩阵实现中，我们按照顶点索引从小到大的顺序检查邻居（for (int neighbor = 0; ...)），这定义了一种确定的顺序。如果你使用邻接表且插入边的顺序不同，或者迭代实现中压栈顺序不同，结果就会不同。只要满足“深度优先”的特性，所有结果都是正确的。在面试或解决问题时，理解这一点比死记一个输出序列更重要。

4. 核心操作二：广度优先搜索与最短路径初探

如果说DFS是探险家，喜欢深入一条路径直到尽头，那么BFS就像是测绘队，严谨地一层层推进，测量起点到所有可达点的“距离”。对于有向图，BFS是求解无权图最短路径问题的标准工具。

4.1 BFS算法实现：队列的完美应用

BFS使用队列来维护待访问的顶点。它从起点开始，先访问所有距离为1（直接邻居）的顶点，然后是距离为2的顶点（邻居的邻居），依此类推。

void DirectedGraph::bfs(int startVertex) { if (startVertex < 0 || startVertex >= numVertices) return; vector<bool> visited(numVertices, false); queue<int> q; // 初始化 visited[startVertex] = true; q.push(startVertex); cout << "BFS starting from vertex " << (startVertex + 1) << ": "; while (!q.empty()) { int v = q.front(); q.pop(); cout << (v + 1) << " "; // 访问当前顶点 // 遍历所有出边邻居 for (int neighbor = 0; neighbor < numVertices; ++neighbor) { if (adjMatrix[v][neighbor] != 0 && !visited[neighbor]) { visited[neighbor] = true; // **关键：入队时标记已访问** q.push(neighbor); } } } cout << endl; }

BFS与DFS实现的核心区别：

1. 数据结构：BFS用队列（FIFO），DFS用栈（LIFO，递归隐式使用调用栈）。
2. 访问标记时机：这是极易出错的地方。在BFS中，必须在顶点入队时就将其标记为visited。为什么？想象一下，顶点A和B都是顶点C的邻居，它们会在同一次循环中被发现。如果不在入队时标记，A和B可能都会将C加入队列，导致C被重复访问和处理。而在DFS中，我们是在“处理”顶点时（递归函数开头）标记，因为递归栈保证了同一路径上的唯一性。

4.2 记录层数与最短路径距离

BFS的强大之处在于，它天然地按“层”遍历图。我们可以轻松地记录每个顶点到起点的最短距离（边数）。

vector<int> DirectedGraph::bfsShortestPath(int startVertex) { vector<int> distance(numVertices, -1); // -1 表示不可达 if (startVertex < 0 || startVertex >= numVertices) return distance; queue<int> q; distance[startVertex] = 0; q.push(startVertex); while (!q.empty()) { int v = q.front(); q.pop(); for (int neighbor = 0; neighbor < numVertices; ++neighbor) { if (adjMatrix[v][neighbor] != 0 && distance[neighbor] == -1) { // 找到一个新的可达顶点，其距离为当前顶点距离+1 distance[neighbor] = distance[v] + 1; q.push(neighbor); } } } return distance; }

算法逻辑解析：

• distance数组同时充当了visited数组的角色。-1表示未访问/不可达。
• 起点的距离初始化为0。
• 当我们从队列中取出顶点v，并发现一个通过边v->neighbor可达的、且未被访问过的邻居neighbor时，neighbor的距离就是distance[v] + 1。这是因为BFS是按层遍历的，neighbor一定是在v的下一层被首次发现。
• 这个distance数组就是起点到图中所有其他顶点的最短路径长度（假设边权为1）。要重建具体路径，还需要一个parent数组记录每个顶点的前驱节点。

4.3 BFS与DFS的对比与应用场景选择

理解两者差异，才能在做题或设计时做出正确选择。

如何选择？

• 问题涉及“最短”、“最少步数”：无条件选择BFS。因为BFS第一次到达目标点的路径就是最短路径。DFS可能会绕远路，需要遍历所有路径才能确定最短。
• 问题需要遍历所有可能状态或路径（如排列组合、求所有解）：通常用DFS+回溯，它的空间开销更可控。
• 检查图是否为有向无环图或求拓扑序：用DFS。
• 图非常深而宽有限（如一条长链）：BFS的队列可能爆内存，DFS更合适。
• 图非常宽而深度有限（如星型图）：DFS的递归栈可能很深，BFS更合适。

一个常见的误解：认为DFS一定比BFS快或慢。它们的时间复杂度都是 O(V+E)（顶点数+边数），因为每个顶点和边最多被访问一次。区别在于访问顺序和空间开销，这决定了它们适用于不同的问题。

5. 从存储到应用：邻接矩阵的局限性分析与实战建议

通过前面的实现，我们已经用邻接矩阵完成了有向图的基础构建、DFS和BFS遍历。这是一个完美的学习起点。然而，在迈向更复杂算法和更大规模问题时，我们必须清醒地认识到邻接矩阵的局限性，并知道何时该转向更高效的存储结构。

5.1 邻接矩阵的性能瓶颈与邻接表的优势

让我们量化一下邻接矩阵在稀疏图上的浪费。假设一个社交网络有1万个用户（顶点），平均每个用户关注（边）500人。那么总边数 m ≈ 10000 * 500 = 5百万。邻接矩阵需要 10000 * 10000 = 1亿个存储单元，但其中只有5百万个是有效的（值为1），空间利用率只有5%。另外9500万个单元存储的都是0，这是巨大的浪费。

而邻接表则不同。它为一个图维护一个数组（或列表）adjList，其中adjList[i]存储的是顶点i的所有出边邻居的列表（可以用vector<int>,LinkedList等实现）。对于上面的例子，我们只需要存储大约5百万个邻居引用，空间复杂度是 O(V+E)，与实际使用的边数成正比。

邻接表的代码示意：

class DirectedGraphAdjList { private: int numVertices; vector<vector<int>> adjList; // 每个元素是一个动态数组 public: DirectedGraphAdjList(int n) : numVertices(n), adjList(n) {} void addEdge(int u, int v) { adjList[u].push_back(v); } // 遍历顶点v的所有邻居 for (int neighbor : adjList[v]) { // 处理 neighbor } };

在邻接表上执行BFS/DFS，遍历某个顶点所有邻居的时间复杂度是 O(该顶点的出度)，而不是邻接矩阵的 O(V)。对于稀疏图，这带来了巨大的性能提升。

5.2 基于邻接矩阵的算法扩展思考

尽管有局限性，但在顶点数少的情况下，邻接矩阵依然有其用武之地，并且一些算法概念在其上更容易理解。

例如，求图的传递闭包（判断任意两点间是否存在路径），可以使用经典的Warshall 算法（或基于矩阵乘法的重复平方法），其核心操作就是对邻接矩阵进行动态规划：

// 简单的Warshall算法，计算可达性矩阵 vector<vector<bool>> reachability = adjMatrix; // 先将邻接矩阵转为bool矩阵 for (int k = 0; k < n; ++k) { for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) { // 如果i能到k，且k能到j，则i能到j reachability[i][j] = reachability[i][j] || (reachability[i][k] && reachability[k][j]); } } }

这个三重循环的算法在邻接矩阵上表达非常直观。虽然时间复杂度是 O(n³)，但对于n<10的情况完全可行。

5.3 给初学者的实战建议与下一步方向

1. 从矩阵开始，理解本质：我强烈建议图算法的初学者从邻接矩阵实现开始。它强迫你去思考“顶点i到j是否有边”这个最根本的问题，并且代码的对称性让很多算法（如上面Warshall算法）更容易被看懂。理解了这个“基准模型”，再学习邻接表等优化结构，你会更清楚它们优化了什么。
2. 抽象接口，隔离变化：在实际项目中，你可以定义一个Graph接口或抽象基类，包含addEdge,getNeighbors,hasEdge等方法。然后分别用MatrixGraph和ListGraph实现它。这样，上层的遍历算法（如dfs,bfs）可以基于接口编写，而不依赖具体存储，提高了代码的复用性和可测试性。
3. 下一步学什么：掌握了图的表示和遍历，你的图算法之旅才算真正起步。接下来，我建议按这个顺序深入：
   • 拓扑排序：理解DFS如何通过完成时间产生逆序，以及Kahn算法（基于入度）的BFS实现。
   • 有向图的环检测：深入理解DFS中的“灰色节点”（递归栈中节点）判断。
   • 最短路径算法：从BFS解决无权图，到学习Dijkstra算法（带权非负图）和Bellman-Ford算法（允许负权边）。这时，你的存储结构很可能需要升级为邻接表，并存储边的权重。
   • 连通分量：对于有向图，有强连通分量，需要用Kosaraju或Tarjan算法，这又是DFS的经典应用。

回过头看，我们通过一个简单的“创建图类，使用邻接矩阵存储”的起点，已经串联起了有向图的存储、遍历、以及算法选择的初步思想。记住，图算法不是一堆孤立的魔法，它们都建立在你对图这个结构本身深刻理解的基础之上。把基础打牢，后续那些听起来高大上的算法，不过是这些基本操作的精妙组合。