BFS和DFS用例

BFS、树遍历

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

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

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if (!root) return result;
        queue<TreeNode*> q;
        q.push(root);

        while (!q.empty()) {
            int levelSize = q.size();
            vector<int> currentLevel;
            for (int i = 0; i < levelSize; ++i) {
                TreeNode* node = q.front();
                q.pop();
                currentLevel.push_back(node->val);
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            result.push_back(currentLevel);
        }
        return result;
    }
};

int main() {
    // 构建示例二叉树
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(9);
    root->right = new TreeNode(20);
    root->right->left = new TreeNode(15);
    root->right->right = new TreeNode(7);

    Solution sol;
    vector<vector<int>> traversal = sol.levelOrder(root);
    for (const auto& level : traversal) {
        for (int val : level) {
            cout << val << " ";
        }
        cout << endl;
    }

    // 释放内存
    delete root->right->left;
    delete root->right->right;
    delete root->left;
    delete root;

    return 0;
}

BFS、图遍历

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

// 图的 BFS 遍历函数
void BFS(vector<vector<int>>& graph, int start) {
    int n = graph.size();
    // 标记顶点是否被访问过
    vector<bool> visited(n, false);
    // 创建队列
    queue<int> q;

    // 将起始顶点加入队列并标记为已访问
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        // 取出队列头部顶点
        int vertex = q.front();
        q.pop();

        // 访问该顶点
        cout << vertex << " ";

        // 遍历该顶点的所有邻接顶点
        for (int neighbor : graph[vertex]) {
            if (!visited[neighbor]) {
                // 如果邻接顶点未被访问过，加入队列并标记为已访问
                q.push(neighbor);
                visited[neighbor] = true;
            }
        }
    }
}

int main() {
    // 图的邻接表表示
    vector<vector<int>> graph = {
        {1, 2},  // 顶点 0 的邻接顶点为 1 和 2
        {0, 3},  // 顶点 1 的邻接顶点为 0 和 3
        {0, 3},  // 顶点 2 的邻接顶点为 0 和 3
        {1, 2}   // 顶点 3 的邻接顶点为 1 和 2
    };

    // 从顶点 0 开始进行 BFS 遍历
    cout << "BFS traversal starting from vertex 0: ";
    BFS(graph, 0);
    cout << endl;

    return 0;
}