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

基于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;elsecout << "无法到达终点" << 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 friendsif (depth > 0) {candidates[friendId]++;}}}}// Filter out existing friendsfor (int existingFriend : adjList[userId]) {candidates.erase(existingFriend);}// Sort by common friends countvector<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