深度优先遍历算法详解：递归实现与广度优先比较

深度优先遍历（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法，它从给定的起始节点（通常称为源或根节点）开始，尽可能深地探索分支，直到到达一个叶子节点，然后回溯到未访问过的节点。在C++中，DFS可以设计为递归实现，如以下代码所示： ```cpp void dfs(int u, int k) { if (u == n) { max1 = max(max1, k); return; } for (int i = 0; i < k; i++) { if (a1[i] + a[u] <= m) { a1[i] = a1[i] + a[u]; dfs(u + 1, k); a1[i] = a1[i] - a[u]; // 恢复路径权重 } } a1[k+1] = a[u]; // 保存当前路径权重 dfs(u + 1, k + 1); // 继续搜索 a1[k+1] = 0; // 清除路径权重 } ``` 在这个例子中，`u` 是当前节点，`k` 表示已探索的路径长度，`n` 是图的节点总数，`a` 和 `m` 可能是与图相关的数据结构。递归的核心逻辑是检查相邻节点并更新路径。 相比之下，广度优先搜索（Breadth-First Search, BFS）则是按层次顺序遍历图，从起始节点开始，先访问所有邻居，然后是邻居的邻居，以此类推。BFS 使用队列来存储待访问的节点，确保总是优先处理距离起点最近的节点。下面是BFS的C++代码： ```cpp while (!q.empty()) { c2 = q.front(); q.pop(); if (c2.l == b) { cout << c2.sl; return 0; } // ... (其他操作，如更新节点位置和标记) int y; y = c2.l + s[c2.l]; // ... (检查节点有效性并入队) y = c2.l - s[c2.l]; // ... (同样，检查节点有效性并入队) } ``` BFS和DFS的主要区别在于搜索策略：DFS是深度优先，追求深入节点，而BFS是宽度优先，优先探索离起点近的节点。它们的应用场景不同，如电梯问题通常适合用BFS解决，因为它模拟了上行和下行的选择；而像缆车这种单程路径问题则更适合用DFS，因为一旦做出选择就无法回头。 总结起来，深度优先遍历和广度优先遍历都是图搜索的经典算法，各有其适用场景和优缺点。理解它们的原理和特点对于在实际编程中正确选择和应用这些算法至关重要。在C++中，这两种搜索可以通过递归或迭代的方式实现，具体选择取决于问题的特性和性能需求。