STL queue - 队列与 BFS

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 默认构造
    queue<int> q;
    
    // 使用自定义容器（必须支持 front(), back(), push_back(), pop_front()）
    queue<int, list<int>> q_list;
    queue<int, deque<int>> q_deque;
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<int> q;
    
    // 入队
    q.push(10);
    q.push(20);
    q.push(30);
    
    // 访问队首和队尾
    cout << "队首: " << q.front() << endl;  // 10
    cout << "队尾: " << q.back() << endl;   // 30
    
    // 出队
    q.pop();
    cout << "出队后队首: " << q.front() << endl;  // 20
    
    // 大小和判空
    cout << "队列大小: " << q.size() << endl;  // 2
    cout << "队列是否为空: " << (q.empty() ? "是" : "否") << endl;  // 否
    
    // 清空队列
    while (!q.empty())
    {
        q.pop();
    }
    cout << "清空后队列是否为空: " << (q.empty() ? "是" : "否") << endl;  // 是
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

void bfs(int start, const vector<vector<int>>& adj)
{
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    // 初始化
    q.push(start);
    visited[start] = true;
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << u << " ";  // 处理节点
        
        // 访问邻接点
        for (int v : adj[u])
        {
            if (!visited[v])
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 构建邻接表
    int n = 6;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0, 5};
    adj[3] = {1};
    adj[4] = {1};
    adj[5] = {2};
    
    cout << "BFS 遍历结果: ";
    bfs(0, adj);  // 0 1 2 3 4 5
    cout << endl;
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

vector<int> shortest_path(int start, int end, const vector<vector<int>>& adj)
{
    int n = adj.size();
    vector<int> dist(n, -1);
    vector<int> parent(n, -1);
    queue<int> q;
    
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        
        if (u == end)
        {
            break;  // 找到终点
        }
        
        for (int v : adj[u])
        {
            if (dist[v] == -1)
            {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    // 重建路径
    vector<int> path;
    if (dist[end] == -1)
    {
        return path;  // 无路径
    }
    
    for (int v = end; v != -1; v = parent[v])
    {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n = 6;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0, 5};
    adj[3] = {1};
    adj[4] = {1};
    adj[5] = {2};
    
    vector<int> path = shortest_path(0, 5, adj);
    cout << "最短路径: ";
    for (int v : path)
    {
        cout << v << " ";  // 0 2 5
    }
    cout << endl;
    
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

// 二叉树层序遍历
struct TreeNode
{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

vector<vector<int>> level_order(TreeNode* root)
{
    vector<vector<int>> result;
    if (!root)
    {
        return result;
    }
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty())
    {
        int level_size = q.size();
        vector<int> level;
        
        for (int i = 0; i < level_size; i++)
        {
            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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

// 多源 BFS 求最短距离
vector<vector<int>> multi_source_bfs(int n, int m, const vector<pair<int, int>>& sources)
{
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    
    // 初始化多个源点
    for (const auto& source : sources)
    {
        int x = source.first;
        int y = source.second;
        dist[x][y] = 0;
        q.emplace(x, y);
    }
    
    // 四个方向
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    while (!q.empty())
    {
        pair<int, int> front = q.front();
        int x = front.first;
        int y = front.second;
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }
    
    return dist;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

// 0-1 BFS 处理边权为 0 或 1 的图
vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj)
{
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;  // 使用双端队列
    
    dist[start] = 0;
    dq.push_front(start);
    
    while (!dq.empty())
    {
        int u = dq.front();
        dq.pop_front();
        
        for (const auto& edge : adj[u])
        {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (w == 0)
                {
                    dq.push_front(v);  // 权值为 0 放在队首
                }
                else
                {
                    dq.push_back(v);   // 权值为 1 放在队尾
                }
            }
        }
    }
    
    return dist;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    queue<pair<int, int>> q;
    q.emplace(1, 2);
    q.emplace(3, 4);
    
    while (!q.empty())
    {
        pair<int, int> front = q.front();
        int x = front.first;
        int y = front.second;
        cout << "x: " << x << ", y: " << y << endl;
        q.pop();
    }
    
    return 0;
}

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

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 可以通过 deque 初始化 queue
    deque<int> d = {1, 2, 3, 4, 5};
    queue<int> q(d);
    
    while (!q.empty())
    {
        cout << q.front() << " ";
        q.pop();
    }
    // 输出: 1 2 3 4 5
    
    return 0;
}

1
2
3
4
5
6
7
8
9

// 对于底层容器为 deque 的情况
queue<int> q;
// 无法直接 reserve，但可以通过 deque 预分配

// 更好的做法：如果知道大致大小，使用 deque 预分配
int expected_size = 100000;
deque<int> d;
d.reserve(expected_size);
queue<int> q(d);

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

// 错误示范：值传递
void process_queue(queue<int> q)  // 会拷贝整个队列
{
    // 处理 q
}

// 正确做法：使用引用
void process_queue(queue<int>& q)  // 引用传递，无拷贝
{
    // 处理 q
}

// 使用移动语义
queue<int> create_queue()
{
    queue<int> q;
    // 填充 q
    return q;  // 移动语义，无拷贝
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;

// 基本 BFS
void bfs(int start, const vector<vector<int>>& adj)
{
    int n = adj.size();
    vector<bool> visited(n, false);
    queue<int> q;
    
    q.push(start);
    visited[start] = true;
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        cout << u << " ";
        
        for (int v : adj[u])
        {
            if (!visited[v])
            {
                visited[v] = true;
                q.push(v);
            }
        }
    }
    cout << endl;
}

// BFS 求最短路径
vector<int> shortest_path(int start, int end, const vector<vector<int>>& adj)
{
    int n = adj.size();
    vector<int> dist(n, -1);
    vector<int> parent(n, -1);
    queue<int> q;
    
    q.push(start);
    dist[start] = 0;
    
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        
        if (u == end)
        {
            break;
        }
        
        for (int v : adj[u])
        {
            if (dist[v] == -1)
            {
                dist[v] = dist[u] + 1;
                parent[v] = u;
                q.push(v);
            }
        }
    }
    
    vector<int> path;
    if (dist[end] == -1)
    {
        return path;
    }
    
    for (int v = end; v != -1; v = parent[v])
    {
        path.push_back(v);
    }
    reverse(path.begin(), path.end());
    return path;
}

// 多源 BFS
vector<vector<int>> multi_source_bfs(int n, int m, const vector<pair<int, int>>& sources)
{
    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;
    
    for (const auto& source : sources)
    {
        int x = source.first;
        int y = source.second;
        dist[x][y] = 0;
        q.emplace(x, y);
    }
    
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};
    
    while (!q.empty())
    {
        pair<int, int> front = q.front();
        int x = front.first;
        int y = front.second;
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && dist[nx][ny] == -1)
            {
                dist[nx][ny] = dist[x][y] + 1;
                q.emplace(nx, ny);
            }
        }
    }
    
    return dist;
}

// 0-1 BFS
vector<int> zero_one_bfs(int start, const vector<vector<pair<int, int>>>& adj)
{
    int n = adj.size();
    vector<int> dist(n, INT_MAX);
    deque<int> dq;
    
    dist[start] = 0;
    dq.push_front(start);
    
    while (!dq.empty())
    {
        int u = dq.front();
        dq.pop_front();
        
        for (const auto& edge : adj[u])
        {
            int v = edge.first;
            int w = edge.second;
            if (dist[v] > dist[u] + w)
            {
                dist[v] = dist[u] + w;
                if (w == 0)
                {
                    dq.push_front(v);
                }
                else
                {
                    dq.push_back(v);
                }
            }
        }
    }
    
    return dist;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    // 测试基本 BFS
    int n = 6;
    vector<vector<int>> adj(n);
    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0, 5};
    adj[3] = {1};
    adj[4] = {1};
    adj[5] = {2};
    
    cout << "BFS 遍历: ";
    bfs(0, adj);
    
    // 测试最短路径
    vector<int> path = shortest_path(0, 5, adj);
    cout << "最短路径: ";
    for (int v : path)
    {
        cout << v << " ";
    }
    cout << endl;
    
    // 测试多源 BFS
    int rows = 3, cols = 3;
    vector<pair<int, int>> sources = {{0, 0}, {2, 2}};
    vector<vector<int>> dist = multi_source_bfs(rows, cols, sources);
    cout << "多源 BFS 距离矩阵: " << endl;
    for (int i = 0; i < rows; i++)
    {
        for (int j = 0; j < cols; j++)
        {
            cout << dist[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}