C++ BFS实例：从入门到实战

发布于：2025-08-15 ⋅ 阅读:(12) ⋅ 点赞:(0)

基于C++的BFS（广度优先搜索）实例

以下是基于C++的BFS（广度优先搜索）实例，涵盖常见应用场景，包括图遍历、最短路径、矩阵搜索等。每个例子均包含核心代码片段和关键思路说明。

基本BFS框架模板

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

void bfs(vector<vector<int>>& graph, int start) {
    queue<int> q;
    unordered_set<int> visited;
    q.push(start);
    visited.insert(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int neighbor : graph[current]) {
            if (visited.find(neighbor) == visited.end()) {
                visited.insert(neighbor);
                q.push(neighbor);
            }
        }
    }
}

无权图最短路径

vector<int> shortestPath(vector<vector<int>>& graph, int start) {
    vector<int> distance(graph.size(), -1);
    queue<int> q;
    distance[start] = 0;
    q.push(start);

    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int neighbor : graph[current]) {
            if (distance[neighbor] == -1) {
                distance[neighbor] = distance[current] + 1;
                q.push(neighbor);
            }
        }
    }
    return distance;
}

矩阵中的最短路径（障碍物处理）

int shortestPathMatrix(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> end) {
    if (grid[start.first][start.second] == 1) return -1;
    int m = grid.size(), n = grid[0].size();
    queue<pair<int, int>> q;
    vector<vector<int>> dirs = {
  
  {-1,0}, {1,0}, {0,-1}, {0,1}};
    grid[start.first][start.second] = 1;
    q.push(start);
    int steps = 0;

    while (!q.empty()) {
        int size = q.size();
        while (size--) {
            auto [x, y] = q.front();
            q.pop();
            if (x == end.first && y == end.second) return steps;
            for (auto& dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                    grid[nx][ny] = 1;
                    q.push({nx, ny});
                }
            }
        }
        steps++;
    }
    return -1;
}

岛屿数量计数

int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); ++i) {
        for (int j = 0; j < grid[0].size(); ++j) {
            if (grid[i][j] == '1') {
                count++;
                queue<pair<int, int>> q;
                q.push({i, j});
                grid[i][j] = '0';
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (auto& dir : vector<pair<int, int>>{
  
  {-1,0}, {1,0}, {0,-1}, {0,1}}) {
                        int nx = x + dir.first, ny = y + dir.second;
                        if (nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1') {
                            grid[nx][ny] = '0';
                            q.push({nx, ny});
                        }
                    }
                }
            }
        }
    }
    return count;
}

层次遍历二叉树

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> result;
    if (!root) return result;
    queue<TreeNode*> q;
    q.push(root);
    while (!q.empty()) {
        int size = q.size();
        vector<int> level;
        while (size--) {
            TreeNode* node = q.front();
            q.pop();
            level.push_back(node->val);
            if (node->left) q.push(node->left);
            if (node->right) q.push(node->right);
        }
        result.push_back(level);
    }
    return result;
}

    所有示例均遵循BFS核心原则：使用队列维护待访问节点，按层扩展避免重复访问。实际应用中需根据问题调整节点表示方式和终止条件。

    广度优先搜索（BFS） 

    是一种图遍历算法，按层级逐步扩展节点，常用于解决最短路径问题或连通性问题。

    以下是一个简单的 BFS 示例，用于在迷宫中寻找从起点到终点的最短路径。

    #include <iostream>

#include <queue>

using namespace std;



const int N = 5; // 定义迷宫大小

int maze[N][N] = {

{0, 1, 0, 0, 0},

{0, 1, 0, 1, 0},

{0, 0, 0, 1, 0},

{1, 1, 1, 1, 0},

{0, 0, 0, 1, 3} // 3 表示终点

};

int directions[4][2] = {
  
  {1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // 四个方向



struct Node {

int x, y, steps;

};



int BFS(int startX, int startY) {

queue<Node> q;

q.push({startX, startY, 0});

maze[startX][startY] = 2; // 标记起点已访问



while (!q.empty()) {

Node current = q.front();

q.pop();



for (auto dir : directions) {

int newX = current.x + dir[0];

int newY = current.y + dir[1];



if (newX >= 0 && newX < N && newY >= 0 && newY < N && maze[newX][newY] != 1 && maze[newX][newY] != 2) {

if (maze[newX][newY] == 3) return current.steps + 1; // 到达终点

q.push({newX, newY, current.steps + 1});

maze[newX][newY] = 2; // 标记已访问

}

}

}

return -1; // 无法到达终点

}



int main() {

int result = BFS(0, 0);

if (result != -1)

cout << "最短路径步数: " << result << endl;

else

cout << "无法到达终点" << endl;

return 0;

}

    注意事项:

    • 队列 用于保证节点按层级顺序处理。

    • 方向数组 简化了移动逻辑。

    • 如果迷宫较大，需注意 空间复杂度。

    三度好友推荐算法

    三度好友推荐基于社交网络的“朋友的朋友”概念，通过分析用户的三层社交关系（一度：直接好友；二度：好友的好友；三度：好友的好友的好友）生成推荐列表。算法通常结合共同好友数、互动频率等权重排序。

    实例代码结构

    以下是一个基于邻接表实现的C++示例，包含数据结构和核心算法：

    #include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

class SocialGraph {
private:
    unordered_map<int, unordered_set<int>> adjList;

public:
    void addUser(int userId) {
        adjList[userId] = unordered_set<int>();
    }

    void addFriendship(int user1, int user2) {
        adjList[user1].insert(user2);
        adjList[user2].insert(user1);
    }

    vector<int> recommendFriends(int userId, int maxDepth = 3) {
        unordered_set<int> visited;
        unordered_map<int, int> candidates; // {candidateId: commonFriends}

        queue<pair<int, int>> q; // {currentUser, currentDepth}
        q.push({userId, 0});
        visited.insert(userId);

        while (!q.empty()) {
            auto [currentUser, depth] = q.front();
            q.pop();

            if (depth >= maxDepth) continue;

            for (int friendId : adjList[currentUser]) {
                if (visited.find(friendId) == visited.end()) {
                    visited.insert(friendId);
                    q.push({friendId, depth + 1});

                    // Only count candidates beyond immediate friends
                    if (depth > 0) {
                        candidates[friendId]++;
                    }
                }
            }
        }

        // Filter out existing friends
        for (int existingFriend : adjList[userId]) {
            candidates.erase(existingFriend);
        }

        // Sort by common friends count
        vector<pair<int, int>> sorted(candidates.begin(), candidates.end());
        sort(sorted.begin(), sorted.end(),
            [](const pair<int, int>& a, const pair<int, int>& b) {
                return a.second > b.second;
            });

        vector<int> result;
        for (auto& [candidate, _] : sorted) {
            result.push_back(candidate);
        }

        return result;
    }
};

    测试用例示例

    int main() {
    SocialGraph graph;

    // 添加用户
    for (int i = 1; i <= 20; ++i) {
        graph.addUser(i);
    }

    // 建立好友关系（模拟社交网络）
    graph.addFriendship(1, 2);
    graph.addFriendship(1, 3);
    graph.addFriendship(2, 4);
    graph.addFriendship(2, 5);
    graph.addFriendship(3, 6);
    graph.addFriendship(4, 7);
    graph.addFriendship(4, 8);
    graph.addFriendship(5, 9);
    graph.addFriendship(6, 10);
    graph.addFriendship(7, 11);
    graph.addFriendship(8, 12);
    graph.addFriendship(9, 13);
    graph.addFriendship(10, 14);
    graph.addFriendship(11, 15);
    graph.addFriendship(12, 16);
    graph.addFriendship(13, 17);
    graph.addFriendship(14, 18);
    graph.addFriendship(15, 19);
    graph.addFriendship(16, 20);

    // 测试不同用户的好友推荐
    vector<int> testUsers = {1, 4, 7, 10, 15};
    for (int userId : testUsers) {
        vector<int> recommendations = graph.recommendFriends(userId);
        cout << "User " << userId << " recommendations: ";
        for (int id : recommendations) {
            cout << id << " ";
        }
        cout << endl;
    }

    return 0;
}

    算法优化方向

    1. 权重增强
      引入互动频率权重公式：
      $$score = \alpha \cdot commonFriends + \beta \cdot interactionFrequency$$
      其中$\alpha$和$\beta$为可调参数。

    2. 实时更新
      使用增量计算维护推荐列表，避免全量重算。

    3. 并行化
      对大规模图采用BSP（Bulk Synchronous Parallel）模型并行处理。

    4. 存储优化
      使用压缩稀疏行（CSR）格式存储邻接表，减少内存占用。

    典型输出示例

    User 1 recommendations: 4 5 6 7 8 9 10 
User 4 recommendations: 1 5 6 11 12 13 14 
User 7 recommendations: 2 8 15 16 17 18 
User 10 recommendations: 3 6 14 18 19 20 
User 15 recommendations: 7 11 19 20

    扩展功能实现

    // 添加带权重的推荐
vector<pair<int, double>> recommendFriendsWithWeight(int userId) {
    auto candidates = recommendFriends(userId);
    unordered_map<int, double> weighted;

    for (int candidate : candidates) {
        // 计算共同好友数
        auto& userFriends = adjList[userId];
        auto& candidateFriends = adjList[candidate];
        vector<int> common;
        set_intersection(userFriends.begin(), userFriends.end(),
                        candidateFriends.begin(), candidateFriends.end(),
                        back_inserter(common));
        
        // 简单加权：共同好友数 × 0.5 + 随机互动因子
        weighted[candidate] = common.size() * 0.5 + (rand() % 10) * 0.1;
    }

    vector<pair<int, double>> result(weighted.begin(), weighted.end());
    sort(result.begin(), result.end(),
        [](auto& a, auto& b) { return a.second > b.second; });
    
    return result;
}

    C++ 单词接龙最短转换序列实例

    单词接龙（Word Ladder）问题要求找到从一个单词到另一个单词的最短转换序列，每次只能改变一个字母，且所有中间单词必须存在于给定的字典中。以下是基于C++的实现示例，使用广度优先搜索（BFS）算法解决。

    示例1: 基础BFS实现

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

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;
    queue<string> q;
    q.push(beginWord);
    int ladder = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            string word = q.front();
            q.pop();
            if (word == endWord) return ladder;
            for (int j = 0; j < word.size(); ++j) {
                char c = word[j];
                for (int k = 0; k < 26; ++k) {
                    word[j] = 'a' + k;
                    if (dict.count(word)) {
                        q.push(word);
                        dict.erase(word);
                    }
                }
                word[j] = c;
            }
        }
        ladder++;
    }
    return 0;
}

    示例2: 双向BFS优化

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;
    unordered_set<string> head, tail, *phead, *ptail;
    head.insert(beginWord);
    tail.insert(endWord);
    int ladder = 2;
    while (!head.empty() && !tail.empty()) {
        if (head.size() < tail.size()) {
            phead = &head;
            ptail = &tail;
        } else {
            phead = &tail;
            ptail = &head;
        }
        unordered_set<string> temp;
        for (auto it = phead->begin(); it != phead->end(); ++it) {
            string word = *it;
            for (int i = 0; i < word.size(); ++i) {
                char c = word[i];
                for (int j = 0; j < 26; ++j) {
                    word[i] = 'a' + j;
                    if (ptail->count(word)) return ladder;
                    if (dict.count(word)) {
                        temp.insert(word);
                        dict.erase(word);
                    }
                }
                word[i] = c;
            }
        }
        ladder++;
        phead->swap(temp);
    }
    return 0;
}

    示例3: 使用预处理和邻接表

    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;
    unordered_map<string, vector<string>> adj;
    queue<string> q;
    q.push(beginWord);
    int ladder = 1;
    while (!q.empty()) {
        int size = q.size();
        for (int i = 0; i < size; ++i) {
            string word = q.front();
            q.pop();
            if (word == endWord) return ladder;
            for (int j = 0; j < word.size(); ++j) {
                string pattern = word.substr(0, j) + "*" + word.substr(j + 1);
                for (auto& neighbor : adj[pattern]) {
                    if (dict.count(neighbor)) {
                        q.push(neighbor);
                        dict.erase(neighbor);
                    }
                }
            }
        }
        ladder++;
    }
    return 0;
}

    示例4: 使用优先级队列

    struct Nod

    网站公告

    今日签到

    点亮在社区的每一天
    去签到

    热门文章

    最新发布