深度优先搜索（c++）相关的内容有什么？

2025-05-20 04:14:15

推荐回答（1个）

回答1：

这个问题问的让我摸不着头脑。

深度优先搜索广泛应用于树和图的结构中。深度顾名思义，就是一直向前进，直到走不动了，向后退一步，继续前进。直到将全部的路径走完，程序结束。这个很像函数的调用堆栈，一直函数调用，然后一直压堆栈，最内层的函数执行完毕，堆栈弹出一个。因此深度优先搜索的其中一种实现策略就是完全利用函数堆栈的调用方式，实现。
例如树的先根遍历：
preOrderTraverse(T root){
visit(root);
preOrderTraverse(root->leftChild);
preOrderTraverse(root->rightChild);
}
这就是典型的通过递归实现深度遍历的策略。

还有另外一种实现策略就是用栈，它常被叫做递归策略的非递归版本。深度优先策略的递归改为非递归的中心思想就是用人工栈模拟函数调用栈的操作，用栈实现非递归。具体代码我就不写了，自己多写多思考。