while(!que.empty())
时间: 2023-12-19 12:07:41 浏览: 39
This is a condition used in a loop that runs until a queue (represented by the variable name "que") is empty. The exclamation mark before the que.empty() method is a logical operator that means "not". So, the loop will continue to run as long as the queue is not empty. Once the queue becomes empty, the loop will terminate.
相关问题
优化下列代码void bfs(int s) { //邻接表存储图,访问点 s queue<int> que; visited[s] = true; // 将起点 s 标记并放到队列 que.push(s); while (!que.empty()) { // int now = que.front(); printf("%d ", now); for (Edge* p = head[now]; p != NULL; p = p->next) { // 广度优先遍历邻接点 if (!visited[p->to]) { que.push(p->to); // 找到未被访问过的邻接点加入队列,并标记 visited[p->to] = true; } } } } // 假设全局变量已经定义好了 int main() { memset(visited, false, sizeof(visited)); // 如果是有向图,必须用循环才能保证所有的结点都遍历到 // 如果是连通的无向图,从任一结点开始即可 for (int i = 1; i <= n; ++i) { if (!visited[i]) { bfs(i); } } return 0; }
这段代码是广度优先搜索遍历一个图的算法实现,其中使用了邻接表存储图的结构。对于优化,可以考虑以下几点:
1. 使用bool数组代替visited数组
在代码中,visited数组用于标记每个节点是否被访问过,可以将其改为bool类型的数组,这样可以节省空间并提高效率。
2. 将标记放在节点入队时处理
在当前代码中,每次处理节点时都要进行访问标记的操作,可以在节点入队时进行标记,这样可以避免重复操作。
3. 将邻接点遍历改为迭代器
在当前代码中,邻接点的遍历使用了指针的方式,可以考虑使用迭代器的方式,这样可以提高代码的可读性和可维护性。
优化后的代码如下:
```cpp
void bfs(int s) {
queue<int> que;
vector<bool> visited(n + 1, false); // 使用bool数组代替visited数组
visited[s] = true;
que.push(s);
while (!que.empty()) {
int now = que.front();
printf("%d ", now);
que.pop(); // 出队操作
for (auto p = head[now]; p != NULL; p = p->next) { // 使用迭代器遍历邻接点
if (!visited[p->to]) {
visited[p->to] = true;
que.push(p->to); // 入队操作时进行标记
}
}
}
}
int main() {
// 如果是有向图,必须用循环才能保证所有的结点都遍历到
// 如果是连通的无向图,从任一结点开始即可
for (int i = 1; i <= n; ++i) {
bfs(i);
}
return 0;
}
```
#include <iostream>#include <cstring>#include <queue>#define N 2005#define INF 1e18using namespace std;typedef long long ll;typedef pair<ll, int> P;int n, m, s, t;bool vis[N];ll dist[N];vector<P> G[N];void dijkstra(int s) { priority_queue<P, vector<P>, greater<P> > que; memset(vis, false, sizeof(vis)); fill(dist, dist + N, INF); dist[s] = 0; que.push(P(0, s)); while(!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if(vis[v]) continue; vis[v] = true; for(int i = 0; i < G[v].size(); i++) { int u = G[v][i].second; ll d = G[v][i].first; if(dist[u] > dist[v] + d) { dist[u] = dist[v] + d; que.push(P(dist[u], u)); } } }}int main() { cin >> n >> m >> s >> t; for(int i = 0; i < m; i++) { int a, b; ll c; cin >> a >> b >> c; G[a].push_back(P(c, b)); G[b].push_back(P(c, a)); } dijkstra(s); cout << dist[t] << endl; return 0;}不使用queue的STL实现这个代码
以下是不使用 STL 的 queue 实现的代码,使用手写堆来代替 queue,原理是相同的:
```cpp
#include <iostream>
#include <cstring>
#define N 2005
#define INF 1e18
using namespace std;
typedef long long ll;
typedef pair<ll, int> P;
int n, m, s, t;
bool vis[N];
ll dist[N];
P heap[N];
int heap_size = 0;
int idx[N];
void push(P x) {
int i = ++heap_size;
while(i != 1 && heap[i / 2].first > x.first) {
heap[i] = heap[i / 2];
idx[heap[i].second] = i;
i /= 2;
}
heap[i] = x;
idx[x.second] = i;
}
void pop() {
P x = heap[heap_size--];
int i = 1, j = 2;
while(j <= heap_size) {
if(j < heap_size && heap[j].first > heap[j + 1].first) j++;
if(heap[j].first >= x.first) break;
heap[i] = heap[j];
idx[heap[i].second] = i;
i = j; j *= 2;
}
heap[i] = x;
idx[x.second] = i;
}
void up(P x) {
int i = idx[x.second];
while(i != 1 && heap[i / 2].first > x.first) {
heap[i] = heap[i / 2];
idx[heap[i].second] = i;
i /= 2;
}
heap[i] = x;
idx[x.second] = i;
}
void dijkstra(int s) {
memset(vis, false, sizeof(vis));
fill(dist, dist + N, INF);
dist[s] = 0; push(P(0, s));
while(heap_size > 0) {
P p = heap[1]; pop();
int v = p.second;
if(vis[v]) continue;
vis[v] = true;
for(int i = 0; i < G[v].size(); i++) {
int u = G[v][i].second;
ll d = G[v][i].first;
if(dist[u] > dist[v] + d) {
dist[u] = dist[v] + d;
if(idx[u] == 0) push(P(dist[u], u));
else up(P(dist[u], u));
}
}
}
}
int main() {
cin >> n >> m >> s >> t;
for(int i = 0; i < m; i++) {
int a, b; ll c;
cin >> a >> b >> c;
G[a].push_back(P(c, b));
G[b].push_back(P(c, a));
}
dijkstra(s);
cout << dist[t] << endl;
return 0;
}
```
这个代码相比前面的代码更加底层,可读性稍差,但是也实现了相同的算法。