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

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

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

基本BFS框架模板

#include #include #include using namespace std;void bfs(vector<vector>& graph, int start) { queue q; unordered_set 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 shortestPath(vector<vector>& graph, int start) { vector distance(graph.size(), -1); queue 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>& grid, pair start, pair end) { if (grid[start.first][start.second] == 1) return -1; int m = grid.size(), n = grid[0].size(); queue<pair> q; vector<vector> 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 = 0 && ny < n && grid[nx][ny] == 0) {  grid[nx][ny] = 1;  q.push({nx, ny}); } } } steps++; } return -1;}

岛屿数量计数

int numIslands(vector<vector>& 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> q; q.push({i, j}); grid[i][j] = \'0\'; while (!q.empty()) {  auto [x, y] = q.front();  q.pop();  for (auto& dir : vector<pair>{ {-1,0}, {1,0}, {0,-1}, {0,1}}) { int nx = x + dir.first, ny = y + dir.second; if (nx >= 0 && nx = 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> levelOrder(TreeNode* root) { vector<vector> result; if (!root) return result; queue q; q.push(root); while (!q.empty()) { int size = q.size(); vector 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#includeusing namespacestd;const intN = 5;// 定义迷宫大小intmaze[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 表示终点};intdirections[4][2] = { {1, 0}, {-1, 0}, {0, -1}, {0, 1}};// 四个方向structNode {intx, y, steps;};intBFS(intstartX,intstartY) {queue q;q.push({startX, startY, 0});maze[startX][startY] = 2;// 标记起点已访问while(!q.empty()) {Node current = q.front();q.pop();for(autodir : directions) {intnewX = current.x + dir[0];intnewY = current.y + dir[1];if(newX >= 0 && newX = 0 && newY < N && maze[newX][newY] != 1 && maze[newX][newY] != 2) {if(maze[newX][newY] == 3)returncurrent.steps + 1;// 到达终点q.push({newX, newY, current.steps + 1});maze[newX][newY] = 2;// 标记已访问}}}return-1;// 无法到达终点}intmain() {intresult = BFS(0, 0);if(result != -1)cout <<\"最短路径步数: \"<< result << endl;elsecout <<\"无法到达终点\"<< endl;return0;}

注意事项:

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

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

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

三度好友推荐算法

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

实例代码结构

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

#include #include #include #include #include #include using namespace std;class SocialGraph {private: unordered_map<int, unordered_set> adjList;public: void addUser(int userId) { adjList[userId] = unordered_set(); } void addFriendship(int user1, int user2) { adjList[user1].insert(user2); adjList[user2].insert(user1); } vector recommendFriends(int userId, int maxDepth = 3) { unordered_set visited; unordered_map candidates; // {candidateId: commonFriends} queue<pair> 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> sorted(candidates.begin(), candidates.end()); sort(sorted.begin(), sorted.end(), [](const pair& a, const pair& b) { return a.second > b.second; }); vector 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 testUsers = {1, 4, 7, 10, 15}; for (int userId : testUsers) { vector 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> recommendFriendsWithWeight(int userId) { auto candidates = recommendFriends(userId); unordered_map weighted; for (int candidate : candidates) { // 计算共同好友数 auto& userFriends = adjList[userId]; auto& candidateFriends = adjList[candidate]; vector 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> 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 #include #include #include using namespace std;int ladderLength(string beginWord, string endWord, vector& wordList) { unordered_set dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; queue 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& wordList) { unordered_set dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; unordered_set 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 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 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& wordList) { unordered_set dict(wordList.begin(), wordList.end()); if (!dict.count(endWord)) return 0; unordered_map<string, vector> adj; queue 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

免费商用字体下载