cpp实现dfs算法

在C++中，深度优先搜索(DFS)通常可以使用递归或迭代的方式实现。这里以递归为例，给出一个简单的DFS遍历字符串"ABC"所有可能排列的代码示例[^2]：

#include <iostream>
#include <string>

// 用于存储排列结果
std::vector<std::string> permute;

void dfs(std::string str, size_t index) {
    if (index == str.length()) {
        // 当遍历到字符串末尾，添加一个新的排列
        permute.push_back(str);
        return;
    }

    // 对每个字符进行尝试
    for (char ch : str) {
        // 构造新字符串，替换当前位置的字符
        std::string newStr = str.substr(0, index) + ch + str.substr(index + 1);
        dfs(newStr, index + 1); // 递归调用，深入下一层
    }
}

int main() {
    dfs("ABC", 0);
    for (const auto& permutation : permute) {
        std::cout << permutation << std::endl; // 打印所有排列
    }
    return 0;
}

这段代码定义了一个`dfs`函数，它接收当前未完成的字符串`str`和当前要处理的位置`index`。当位置达到字符串长度时，表示已生成一个完整排列，将其加入结果列表`permute`。接着对剩余的字符进行循环，每次构造一个新的字符串并递归地对下一位进行操作。