在queue中用结束标识来节约队列空间。也可以用vector来实现队列,用[left,right]控制队列。
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n, m, c; 4 vector<int> graph[1005]; 5 vector<bool> visited(1005, false); 6 vector<int> level(1005, 0); 7 queue<int> q; 8 void bfs(int l) { 9 if (q.empty()) { 10 return; 11 } 12 q.push(-1); //加入结束标识 13 while(!q.empty() && q.front() != -1) { 14 int p = q.front(); 15 level[p] = l; 16 q.pop(); 17 //得到下一批访问节点 18 for (int i : graph[p]) { 19 if (!visited[i]) { 20 q.push(i); 21 visited[i] = true; 22 } 23 } 24 } 25 q.pop(); //弹出结束标识-1 26 bfs(l + 1); 27 } 28 int main() { 29 cin >> n >> m >> c; 30 int x, y; 31 while (m --) { 32 cin >> x >> y; 33 graph[x].push_back(y); 34 graph[y].push_back(x); 35 } 36 q.push(c); 37 visited[c] = true; 38 bfs(0); 39 for (int i = 1; i <= n; ++ i) { 40 cout << level[i] << endl; 41 } 42 }
标签:bfs,int,简化版,BFS,vector,graph,push,visited,计蒜客 From: https://www.cnblogs.com/coderhrz/p/18526210