二维数组图遍历的复杂度是多少？BFS与DFS是否为(M*N)^(M*N)？

首先直接给结论：完全不是，你提到的(M*N)^(M*N)是完全错误的量级。

BFS和DFS这类图遍历算法的时间复杂度，由图中的节点总数和边总数共同决定，通用计算式为O(V + E)——其中V代表节点数，E代表边数。

放到你描述的场景里：

• 节点数V = M*N
• 最坏全连通的情况下，每个节点都与其他所有节点相连，边数E的量级为V²（精确计算是V*(V-1)/2，但复杂度分析取最高阶项）

将数值代入公式后，时间复杂度为O(V + V²)，简化后是O((M*N)²)，这和你说的指数级复杂度完全不是一个概念。

额外补充：(M*N)^(M*N)这种夸张的量级，一般出现在枚举所有节点排列组合这类场景中，和BFS/DFS的遍历逻辑根本不沾边。

内容的提问来源于stack exchange，提问作者Pasha