数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究图的广度优先搜索或 BFS
广度优先搜索 (BFS) 遍历是一种算法，用于访问给定图的所有节点。在这个遍历算法中，选择一个节点，然后逐个访问所有相邻节点。完成所有邻接顶点后，它会进一步检查另一个顶点并再次检查其邻接顶点。
要实现此算法，我们需要使用队列数据结构。所有相邻顶点都添加到队列中，当完成所有相邻顶点时，从队列中删除一个项目并再次开始遍历该顶点。
在图中，有时我们可能会得到一些循环，因此我们将使用一个数组来标记何时访问了一个节点或尚未访问。
输入 - 图的邻接矩阵。
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
输出 - BFS 遍历：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;
typedef struct node{
int val;
int state; //status
}node;
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
更新时间: 05-Aug-2019
2 千次观看
广告