BFS使用STL进行竞争编码-yiteyi-C++库

基于STL的BFS的简单实现队列和矢量在STL中。邻接列表使用向量的向量表示。

null

In BFS, we start with a node.
1) Create a queue and enqueue source into it. 
   Mark source as visited.
2) While queue is not empty, do following
    a) Dequeue a vertex from queue. Let this 
       be f.
    b) Print f
    c) Enqueue all not yet visited adjacent
       of f and mark them visited.

下面是从源顶点1开始的BFS示例。请注意，一个图可能有多个BFS（即使来自特定顶点）。

BFS using STL for competitive coding

有关BFS的更多详细信息，请参阅这篇帖子 . 这里的代码经过简化，可以用于竞争性编码。

CPP

                         // A Quick implementation of BFS using                       
                         // vectors and queue                       
                         #include <bits/stdc++.h>                       
                         #define pb push_back                       
                                   
                         using                                     namespace                                     std;                       
                                   
                         vector<                                     bool                                     > v;                       
                         vector<vector<                                     int                                     > > g;                       
                                   
                         void                                     edge(                                     int                                     a,                                     int                                     b)                       
                         {                       
                                                 g[a].pb(b);                       
                                   
                                                 // for undirected graph add this line                       
                                                 // g[b].pb(a);                       
                         }                       
                                   
                         void                                     bfs(                                     int                                     u)                       
                         {                       
                                                 queue<                                     int                                     > q;                       
                                   
                                                 q.push(u);                       
                                                 v[u] =                                     true                                     ;                       
                                   
                                                 while                                     (!q.empty()) {                       
                                   
                                                 int                                     f = q.front();                       
                                                 q.pop();                       
                                   
                                                 cout << f <<                                     " "                                     ;                       
                                   
                                                 // Enqueue all adjacent of f and mark them visited                       
                                                 for                                     (                                     auto                                     i = g[f].begin(); i != g[f].end(); i++) {                       
                                                 if                                     (!v[*i]) {                       
                                                 q.push(*i);                       
                                                 v[*i] =                                     true                                     ;                       
                                                 }                       
                                                 }                       
                                                 }                       
                         }                       
                                   
                         // Driver code                       
                         int                                     main()                       
                         {                       
                                                 int                                     n, e;                       
                                                 cin >> n >> e;                       
                                   
                                                 v.assign(n,                                     false                                     );                       
                                                 g.assign(n, vector<                                     int                                     >());                       
                                   
                                                 int                                     a, b;                       
                                                 for                                     (                                     int                                     i = 0; i < e; i++) {                       
                                                 cin >> a >> b;                       
                                                 edge(a, b);                       
                                                 }                       
                                   
                                                 for                                     (                                     int                                     i = 0; i < n; i++) {                       
                                                 if                                     (!v[i])                       
                                                 bfs(i);                       
                                                 }                       
                                   
                                                 return                                     0;                       
                         }                       

Input:
8 10
0 1
0 2
0 3
0 4
1 5
2 5
3 6
4 6
5 7
6 7

Output:
0 1 2 3 4 5 6 7

本文由 尼希尔·马亨德兰 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章