专栏文章

深度优先搜索（DFS）、广度优先搜索（BFS）和二叉树搜索算法

EEmily1234
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min0o24d
此快照首次捕获于
2025/12/01 18:38
3 个月前
此快照最后确认于
2025/12/01 18:38
3 个月前
查看原文

我的想法：

深度优先搜索（DFS）是 “一条路走到黑” 的递归 / 栈式搜索策略，广度优先搜索（BFS）是 “逐层扩散” 的队列式遍历方法，二叉树的搜索则分普通二叉树的遍历查找和二叉查找树（BST）的二分查找，三者在数据结构遍历和问题求解中各有核心应用场景。

正题：

深度优先搜索算法（DFS）

C++ 中实现 DFS 主要有递归和手动栈模拟两种方式，以下以无向图的邻接表为例实现，邻接表用
CPP
vector<vector<int>>
存储。

1. 递归实现 DFS

CPP
#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;

// 递归实现DFS
void dfsRecursive(const vector<vector<int>>& graph, int node, unordered_set<int>& visited) {
    // 标记当前节点为已访问
    visited.insert(node);
    cout << node << " ";

    // 遍历邻接节点
    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

int main() {
    // 无向图的邻接表：节点0-5
    vector<vector<int>> graph = {
        {1, 2},   // 节点0的邻接节点
        {0, 3, 4}, // 节点1的邻接节点
        {0, 5},   // 节点2的邻接节点
        {1},      // 节点3的邻接节点
        {1},      // 节点4的邻接节点
        {2}       // 节点5的邻接节点
    };

    unordered_set<int> visited;
    cout << "递归DFS遍历结果：";
    dfsRecursive(graph, 0, visited); // 从节点0开始遍历
    cout << endl;

    return 0;
}

2. 栈模拟实现 DFS（非递归）

避免递归深度过深导致的栈溢出问题，手动用stack模拟递归调用栈：
CPP
#include <iostream>
#include <vector>
#include <unordered_set>
#include <stack>
using namespace std;

// 栈模拟实现DFS（非递归）
void dfsStack(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    stack<int> st;
    st.push(start);
    visited.insert(start);

    while (!st.empty()) {
        int node = st.top();
        st.pop();
        cout << node << " ";

        // 逆序压入邻接节点（保证遍历顺序与递归一致）
        for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
            int neighbor = *it;
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                st.push(neighbor);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 5},
        {1},
        {1},
        {2}
    };

    cout << "栈模拟DFS遍历结果：";
    dfsStack(graph, 0);
    cout << endl;

    return 0;
}

二、广度优先搜索（BFS）

C++ 中 BFS 通过队列（queue）实现，利用 STL 的queue存储待访问节点，核心是先进先出的遍历规则。
CPP
#include <iostream>
#include <vector>
#include <unordered_set>
#include <queue>
using namespace std;

// BFS实现
void bfs(const vector<vector<int>>& graph, int start) {
    unordered_set<int> visited;
    queue<int> q;

    // 初始化队列
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";

        // 遍历邻接节点
        for (int neighbor : graph[node]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

int main() {
    vector<vector<int>> graph = {
        {1, 2},
        {0, 3, 4},
        {0, 5},
        {1},
        {1},
        {2}
    };

    cout << "BFS遍历结果：";
    bfs(graph, 0);
    cout << endl;

    return 0;
}

三、二叉树的搜索算法

二叉树的搜索分为普通二叉树的遍历查找和二叉搜索树（BST）的高效查找，C++ 中通过 “结构体（struct）”定义二叉树节点，结合指针实现树的操作。

1. 普通二叉树的搜索（前序遍历查找）

普通二叉树无值的排序规则，需通过前序 / 中序 / 后序遍历逐个节点检查，以下是前序遍历的递归实现：
CPP
#include <iostream>
using namespace std;

// 定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 前序遍历查找目标值
TreeNode* searchBinaryTree(TreeNode* root, int target) {
    if (root == nullptr) {
        return nullptr; // 递归终止：节点为空，未找到
    }

    // 先检查当前节点
    if (root->val == target) {
        return root;
    }

    // 递归查找左子树
    TreeNode* leftRes = searchBinaryTree(root->left, target);
    if (leftRes != nullptr) {
        return leftRes;
    }

    // 递归查找右子树
    return searchBinaryTree(root->right, target);
}

// 释放二叉树内存（避免内存泄漏）
void deleteTree(TreeNode* root) {
    if (root == nullptr) return;
    deleteTree(root->left);
    deleteTree(root->right);
    delete root;
}

int main() {
    // 构建二叉树
    //        1
    //       / \
    //      2   3
    //     / \
    //    4   5
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);

    int target = 5;
    TreeNode* res = searchBinaryTree(root, target);
    if (res != nullptr) {
        cout << "找到目标值：" << res->val << endl;
    } else {
        cout << "未找到目标值" << endl;
    }

    deleteTree(root); // 释放内存
    return 0;
}

2. 二叉搜索树（BST）的高效查找

二叉搜索树的核心特性：左子树所有节点值 <根节点值，右子树所有节点值> 根节点值， 利用该特性可实现 O (logN) 的高效查找（平衡 BST）。
CPP
#include <iostream>
using namespace std;

// 定义二叉搜索树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// BST查找（递归实现）
TreeNode* searchBSTRecursive(TreeNode* root, int target) {
    if (root == nullptr || root->val == target) {
        return root;
    }

    // 目标值小于当前节点，查找左子树
    if (target < root->val) {
        return searchBSTRecursive(root->left, target);
    }
    // 目标值大于当前节点，查找右子树
    else {
        return searchBSTRecursive(root->right, target);
    }
}

// BST查找（非递归实现，效率更高）
TreeNode* searchBSTIterative(TreeNode* root, int target) {
    while (root != nullptr && root->val != target) {
        root = (target < root->val) ? root->left : root->right;
    }
    return root;
}

// 释放BST内存
void deleteBST(TreeNode* root) {
    if (root == nullptr) return;
    deleteBST(root->left);
    deleteBST(root->right);
    delete root;
}

int main() {
    // 构建二叉搜索树
    //        4
    //       / \
    //      2   7
    //     / \
    //    1   3
    TreeNode* root = new TreeNode(4);
    root->left = new TreeNode(2);
    root->right = new TreeNode(7);
    root->left->left = new TreeNode(1);
    root->left->right = new TreeNode(3);

    int target = 3;
    // 递归查找
    TreeNode* res1 = searchBSTRecursive(root, target);
    if (res1) cout << "递归查找结果：" << res1->val << endl;

    // 非递归查找
    TreeNode* res2 = searchBSTIterative(root, target);
    if (res2) cout << "非递归查找结果：" << res2->val << endl;

    deleteBST(root); // 释放内存
    return 0;
}

四、关键知识点总结

  1. DFS：递归实现简洁，适合小规模数据；非递归（栈）避免栈溢出，适合大规模数据。
  2. BFS：队列实现，天然适合无权图最短路径、层次遍历等场景。
  3. 二叉树搜索：
  • 普通二叉树需遍历所有节点，时间复杂度O(N)；
  • 二叉搜索树利用 “左小右大” 特性，平均时间复杂度O(logN)，最坏（退化为链表）O(N)。
  1. C++ 特性：使用 STL 的vector、queue、stack、unordered_set简化容器操作，通过指针管理二叉树节点，注意手动释放内存避免泄漏。

刷题

  1. P1135 奇怪的电梯
  2. P1162 填涂颜色
  3. P1189 SEARCH
  4. P1232 [NOI2013] 树的计数
  5. P1330 封锁阳光大学
  6. P1331 海战
  7. P1451 求细胞数量
  8. P1460 [USACO2.1] 健康的荷斯坦奶牛 Healthy
  9. P1506 拯救oibh总部
  10. P1700 [USACO19OPEN] Milk Factory B
  11. P2052 [NOI2011] 道路修建
  12. P2097 资料分发 1
  13. P2540 [NOIP 2015 提高组] 斗地主 加强版
  14. P2845 [USACO15DEC] Switching on the Lights S
  15. P2937 [USACO09JAN] Laserphones S
  16. P3456 [POI 2007] GRZ-Ridges and Valleys
  17. P3496 [POI 2010] GIL-Guilds
  18. B3625 迷宫寻路
  19. P3659 [USACO17FEB] Why Did the Cow Cross the Road
  20. P3663 [USACO17FEB] Why Did the Cow Cross the
  21. P3749 [六省联考 2017] 寿司餐厅
题太多了，不打了
题目广场

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...