数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法律学在 C++ 中使用 STL 的 BFS 进行竞赛编码？
广度优先搜索 (BFS) 遍历是一种算法，用于访问图的所有节点。在这个遍历算法中，先选择一个节点，然后依次访问所有相邻节点。完成所有相邻顶点后，它会进一步检查另一个顶点及其相邻顶点。
在竞技编码中，我们必须非常快速地解决问题。我们将使用 STL (C++ 标准库) 来实现这个算法，我们需要使用队列数据结构。所有相邻顶点都添加到队列中，当所有相邻顶点完成后，从队列中删除一个项目并再次遍历该顶点。
在图中，有时我们可能会遇到一些循环，因此我们将使用一个数组来标记一个节点是否已被访问。
Input : The Adjacency matrix of the graph. A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 0 1 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0 Output : BFS Traversal: B A D E C F
算法
bfs(vertices, start)
输入 − 顶点列表，以及起始顶点。
输出 − 如果图是连通的，则遍历所有节点。
Begin define an empty queue que at first mark all nodes status as unvisited add the start vertex into the que while que is not empty, do delete item from que and set to u display the vertex u for all vertices 1 adjacent with u, do if vertices[i] is unvisited, then mark vertices[i] as temporarily visited add v into the queue mark done mark u as completely visited done End
示例
#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
class node {
public:
int val;
int state; //status
};
int graph[NODE][NODE] = {
{0, 1, 1, 1, 0, 0},
{1, 0, 0, 1, 1, 0},
{1, 0, 0, 1, 0, 1},
{1, 1, 1, 0, 1, 1},
{0, 1, 0, 1, 0, 1},
{0, 0, 1, 1, 1, 0}
};
void bfs(node *vert, node s) {
node u;
int i, j;
queue<node> que;
for(i = 0; i<NODE; i++) {
vert[i].state = 0; //not visited
}
vert[s.val].state = 1;//visited
que.push(s); //insert starting node
while(!que.empty()) {
u = que.front(); //delete from queue and print
que.pop();
cout << char(u.val+'A') << " ";
for(i = 0; i<NODE; i++) {
if(graph[i][u.val]) {
//when the node is non-visited
if(vert[i].state == 0) {
vert[i].state = 1;
que.push(vert[i]);
}
}
}
u.state = 2;//completed for node u
}
}
int main() {
node vertices[NODE];
node start;
char s;
for(int i = 0; i<NODE; i++) {
vertices[i].val = i;
}
s = 'B';//starting vertex B
start.val = s-'A';
cout << "BFS Traversal: ";
bfs(vertices, start);
cout << endl;
}输出
BFS Traversal: B A D E C F
更新于: 30-Jul-2019
566 次浏览
广告