搜索与回溯

搜索算法简介

搜索算法在数据结构中查找特定元素。算法的选择取决于数据是否已排序、数据结构类型和性能要求。

线性搜索

线性搜索按顺序检查每个元素，直到找到目标或到达列表末尾。时间复杂度：O(n)，适用于已排序和未排序的数据。

线性搜索实现

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

int linearSearch(const vector<int>& arr, int target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1; // Not found
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    int target = 22;
    
    int result = linearSearch(arr, target);
    
    if (result != -1) {
        cout << "Element " << target << " found at index " << result << endl;
    } else {
        cout << "Element " << target << " not found" << endl;
    }
    
    return 0;
}

线性搜索遍历每个元素直到找到目标。

二分搜索

二分搜索通过重复将搜索区间减半来处理已排序的数组。时间复杂度：O(log n)，对于大型数据集比线性搜索快得多。

二分搜索实现

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

int binarySearch(const vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (arr[mid] == target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // Not found
}

int main() {
    vector<int> arr = {11, 12, 22, 25, 34, 64, 90};
    int target = 25;
    
    int result = binarySearch(arr, target);
    
    if (result != -1) {
        cout << "Element " << target << " found at index " << result << endl;
    } else {
        cout << "Element " << target << " not found" << endl;
    }
    
    return 0;
}

二分搜索在每一步都将数组分成两半，排除剩余元素的一半。

深度优先搜索 (DFS)

DFS沿着每个分支尽可能深入探索，然后回溯。用于树/图遍历、迷宫求解和查找连通分量。

DFS 实现

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;
    
public:
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }
    
    // Recursive DFS
    void DFSUtil(int v, vector<bool>& visited) {
        visited[v] = true;
        cout << v << " ";
        
        for (int neighbor : adj[v]) {
            if (!visited[neighbor]) {
                DFSUtil(neighbor, visited);
            }
        }
    }
    
    void DFS(int start) {
        vector<bool> visited(V, false);
        cout << "DFS traversal starting from vertex " << start << ": ";
        DFSUtil(start, visited);
        cout << endl;
    }
    
    // Iterative DFS using stack
    void DFSIterative(int start) {
        vector<bool> visited(V, false);
        stack<int> stk;
        
        stk.push(start);
        cout << "Iterative DFS: ";
        
        while (!stk.empty()) {
            int v = stk.top();
            stk.pop();
            
            if (!visited[v]) {
                visited[v] = true;
                cout << v << " ";
                
                // Add neighbors to stack (in reverse order)
                for (int i = adj[v].size() - 1; i >= 0; i--) {
                    if (!visited[adj[v][i]]) {
                        stk.push(adj[v][i]);
                    }
                }
            }
        }
        cout << endl;
    }
};

int main() {
    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);
    
    g.DFS(0);
    g.DFSIterative(0);
    
    return 0;
}

DFS可以通过递归或使用栈迭代实现。

广度优先搜索 (BFS)

BFS在移动到下一个深度级别之前探索当前深度的所有邻居。非常适合在无权图中查找最短路径。

BFS 实现

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

class Graph {
private:
    int V;
    vector<vector<int>> adj;
    
public:
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }
    
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        cout << "BFS traversal starting from vertex " << start << ": ";
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            cout << v << " ";
            
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
    
    // Find shortest path using BFS
    void shortestPath(int start, int target) {
        vector<bool> visited(V, false);
        vector<int> parent(V, -1);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int v = q.front();
            q.pop();
            
            if (v == target) {
                // Reconstruct path
                vector<int> path;
                int current = target;
                while (current != -1) {
                    path.push_back(current);
                    current = parent[current];
                }
                
                cout << "Shortest path from " << start << " to " << target << ": ";
                for (int i = path.size() - 1; i >= 0; i--) {
                    cout << path[i];
                    if (i > 0) cout << " -> ";
                }
                cout << endl;
                return;
            }
            
            for (int neighbor : adj[v]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    parent[neighbor] = v;
                    q.push(neighbor);
                }
            }
        }
        
        cout << "No path found from " << start << " to " << target << endl;
    }
};

int main() {
    Graph g(7);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 6);
    g.addEdge(3, 6);
    
    g.BFS(0);
    g.shortestPath(0, 6);
    
    return 0;
}

BFS使用队列逐层探索节点，保证在无权图中找到最短路径。