12、算法

1、深度优先搜索（Depth-First Search，简称 DFS）和广度优先搜索（Breadth-First Search，简称 BFS）是图论和树结构遍历中常用的两种算法策略，它们的主要区别如下：
搜索方式
深度优先搜索：沿着一条路径尽可能深地探索下去，直到达到叶子节点或者无法继续深入为止，然后回溯到上一个节点，继续探索其他分支。
广度优先搜索：从起始节点开始，首先访问它的所有邻居节点，然后按照这些邻居节点的顺序，依次访问它们的邻居节点，以此类推，一层一层地向外扩展。
使用的数据结构
深度优先搜索：通常使用递归或者栈来实现。递归实现时，系统栈会记录函数调用的顺序和状态；手动使用栈实现时，将节点压入栈中，然后从栈中弹出节点进行访问，并将其未访问的邻居节点压入栈中。
广度优先搜索：一般使用队列来实现。先将起始节点放入队列，然后从队列中取出节点进行访问，把该节点的未访问邻居节点依次加入队列，直到队列为空。

代码示例：

#include <iostream>
#include <vector>

// 定义图的邻接表表示
using Graph = std::vector<std::vector<int>>;

// 递归实现深度优先搜索
void dfs(const Graph& graph, int node, std::vector<bool>& visited) {
    // 标记当前节点为已访问
    visited[node] = true;
    std::cout << node << " ";

    // 遍历当前节点的所有邻居节点
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            // 递归访问未访问的邻居节点
            dfs(graph, neighbor, visited);
        }
    }
}

int main() {
    // 构建一个简单的图（邻接表表示）
    Graph graph = {
        {1, 2},  // 节点 0 的邻居节点为 1 和 2
        {0, 3},  // 节点 1 的邻居节点为 0 和 3
        {0, 3},  // 节点 2 的邻居节点为 0 和 3
        {1, 2}   // 节点 3 的邻居节点为 1 和 2
    };

    // 初始化访问标记数组
    std::vector<bool> visited(graph.size(), false);

    // 从节点 0 开始进行深度优先搜索
    std::cout << "深度优先搜索结果: ";
    dfs(graph, 0, visited);
    std::cout << std::endl;

    return 0;
}