N*N迷宫最坏情况下，搜索树的最大深度是多少？

咱们来好好捋一捋这个问题——N×N的迷宫，最坏情况下DFS和BFS的搜索树最大深度其实要分两种情况来看，你提到的2*(N-1)其实只对应其中一种场景哦。

深度优先搜索（DFS）的最坏情况深度 #

DFS的特点是“一条路走到黑”，直到碰到死胡同才会回溯，所以极端情况下，迷宫的布局会逼着它遍历几乎所有格子才能找到终点。比如想象这样一个迷宫：起点在左上角(0,0)，终点在右下角(N-1,N-1)，但路径设计成螺旋形或者不断引导DFS走进死胡同，每次都要走完当前分支的所有节点才回头。这种情况下，搜索树的最大深度就是N²——因为每访问一个新格子，搜索树就会多一层，极端情况会遍历全部N²个节点才抵达终点。举个例子，2×2的迷宫，最坏情况下DFS可能要走完4个格子才找到终点，对应搜索树深度就是4。

广度优先搜索（BFS）的最坏情况深度 #

BFS是按“层”来遍历的，每次探索当前所有节点的相邻节点，所以它的搜索树深度完全等于起点到终点的最短路径长度。而迷宫里起点到终点的最长最短路径，就是曼哈顿距离的最大值：从(0,0)到(N-1,N-1)，不管怎么走，最短路径的步数都是(N-1)+(N-1) = 2*(N-1)（比如先横向走满N-1步，再纵向走满N-1步，或者反过来）。所以BFS的搜索树最大深度就是你理解的2*(N-1)，因为每一步对应搜索树的一层。

总结一下 #

• 对于DFS，最坏情况下搜索树的最大深度是N²；
• 对于BFS，最坏情况下搜索树的最大深度是2*(N-1)。

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