L6_03 搜索算法

一、深度优先搜索算法(DFS)

1.1 DFS 的定义

深度优先搜索（Depth-First Search）是一种图遍历算法，沿着一条路径尽可能深地探索，直到无法继续再回溯。

1.2 DFS 的特点

• 利用栈（递归调用栈或显式栈）实现
• 可能陷入无限循环（需标记已访问节点）
• 适合探索所有可能路径

1.3 递归实现

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfsRecursive(int node, const vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << node << " ";
    
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfsRecursive(neighbor, graph, visited);
        }
    }
}

1.4 非递归实现

void dfsIterative(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    stack<int> s;
    
    s.push(start);
    visited[start] = true;
    
    while (!s.empty()) {
        int node = s.top();
        s.pop();
        cout << node << " ";
        
        for (auto it = graph[node].rbegin(); it != graph[node].rend(); ++it) {
            if (!visited[*it]) {
                visited[*it] = true;
                s.push(*it);
            }
        }
    }
}

1.5 DFS 应用场景

• 图的连通性检测
• 拓扑排序
• 寻找路径
• 解决迷宫问题

二、宽度优先搜索算法(BFS)

2.1 BFS 的定义

宽度优先搜索（Breadth-First Search）是一种图遍历算法，按层遍历节点，先访问离起点最近的节点。

2.2 BFS 的特点

• 利用队列实现
• 保证找到最短路径（无权图）
• 空间复杂度较高

2.3 BFS 实现

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << " ";
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

2.4 BFS 求最短路径

vector<int> bfsShortestPath(int start, int end, const vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    vector<int> parent(n, -1);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        
        if (node == end) break;
        
        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                parent[neighbor] = node;
                q.push(neighbor);
            }
        }
    }
    
    vector<int> path;
    for (int v = end; v != -1; v = parent[v]) {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

2.5 BFS 应用场景

• 最短路径问题
• 层序遍历
• 连通分量
• 社交网络分析

三、二叉树的搜索算法

3.1 二叉树的深度优先遍历

3.1.1 前序遍历

void preorder(TreeNode* root) {
    if (!root) return;
    cout << root->val << " ";
    preorder(root->left);
    preorder(root->right);
}

3.1.2 中序遍历

void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

3.1.3 后序遍历

void postorder(TreeNode* root) {
    if (!root) return;
    postorder(root->left);
    postorder(root->right);
    cout << root->val << " ";
}

3.2 二叉树的层序遍历（BFS）

void levelOrder(TreeNode* root) {
    if (!root) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->val << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

3.3 二叉搜索树的查找

TreeNode* searchBST(TreeNode* root, int target) {
    if (!root || root->val == target) return root;
    if (target < root->val) return searchBST(root->left, target);
    return searchBST(root->right, target);
}

3.4 二叉树的最大深度

int maxDepth(TreeNode* root) {
    if (!root) return 0;
    return max(maxDepth(root->left), maxDepth(root->right)) + 1;
}

四、DFS vs BFS 对比

特性	DFS	BFS
数据结构	栈	队列
空间复杂度	O(h)，h为树高	O(w)，w为最大宽度
最短路径	不保证	保证（无权图）
应用场景	拓扑排序、连通性	最短路径、层序遍历
实现方式	递归/迭代	迭代