SCP 模拟 · SCP 2021 第一轮（初赛）模拟 第 5 题

具有 $n$ 个顶点，$m$ 条边的连通图采用邻接矩阵存储结构，进行深度优先遍历运算的时间复杂度为

这题考邻接矩阵存图时DFS的时间复杂度，别被‘连通图’带偏，核心是看矩阵访问次数。

学生常误选Θ(n+m)，那是邻接表DFS的复杂度，混淆两种存储结构。还有人把连通图当成一定只走n个点，忘了邻接矩阵里每个点都要扫一遍整行，哪怕实际边很少。

这道题考查的是图论中深度优先遍历（DFS）在不同存储结构下的时间复杂度，属于算法复杂度分析的基础题。

先说概念：邻接矩阵是用一个 n×n 的二维数组存图，矩阵中第 i 行第 j 列的值表示顶点 i 和 j 之间是否有边。不管图里实际有多少条边，这个矩阵的大小永远是 n²。

命题人挖坑点在于：题目特意强调‘连通图’，容易让人以为边数 m 接近 n²，从而直接选 Θ(n²)；但真正的考点是存储结构本身决定的操作次数。DFS 在邻接矩阵上的标准实现是：对每个顶点，都要遍历它所在的那一行（共 n 个元素），判断是否有边。因此，无论图是稀疏还是稠密，每个顶点都要做 n 次检查，总共有 n 个顶点，就是 n×n = n² 次操作。

思考心法：拿到题先想‘访问了哪些数据’。邻接表只访问存在的边，所以是 O(n+m)；邻接矩阵则必须扫描整行，所以是 O(n²)。别被‘连通’干扰，连通只保证所有点都能被访问到，不影响每点扫 n 个元素的事实。

避坑指南：最容易错选 C（Θ(n+m)），那是邻接表的复杂度；D（Θ(m²)）毫无依据；A（Θ(n³)）更是把矩阵当成三维数组了。记住：邻接矩阵的边数 m 不影响时间复杂度，只影响空间复杂度。

考频与趋势：从历年信息学竞赛真题分布看，邻接矩阵与邻接表的复杂度对比是高频考点，尤其在 CSP-J/S 的算法题中，常以‘给定存储结构，求 DFS/BFS 复杂度’的形式出现。该题在 2021 年 SCP 模拟卷中作为单选题出现，说明命题人有意区分两种存储结构的性能差异，这类题目在后续 CSP-J/S 真题中仍会反复考查，尤其是涉及图遍历或最短路的题目。

预测：基于现有数据，未来考试大概率继续用‘邻接矩阵 vs 邻接表’的对比来考复杂度，可能会结合具体算法（如 BFS、Prim、Dijkstra）问时间复杂度，或者给出一个具体图的数据规模，要求估算运行时间。暂无足够依据预测是否会引入加权边或动态图的变化，但核心思路仍是‘存储结构决定遍历代价’。