bfs廣度優先搜索算法

What you will learn?

您將學到什么？

How to implement Breath first search of a graph?

如何實現圖的呼吸優先搜索？

Breadth First Search is a level-wise vertex traversal process. Like a tree all the graphs have vertex but graphs have cycle so in searching to avoid the coming of the same vertex we prefer BFS

Algorithm:

To implement the BFS we use queue and array data structure.

There are two cases in the algorithm:

1. Whenever we visit a vertex we mark it visited and push its adjacent non-visited vertices into the queue and pop the current vertex from the queue.

2. If all the adjacent vertices are visited then only pop the current vertex from the queue.

Consider this graph,

According to our algorithm, the traversal continues like,

Hence all the vertices are visited then only pop operation is performed and queue will be empty finally.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;
//	Make a pair between vertex x and vertex y 
void addedge(list<int> *ls,int x,int y){
ls[x].push_back(y);
ls[y].push_back(x);
return;
} 
//Breath First Search of a Graph
void BFS(list<int>*ls,int num,int x){
bool *visit= new bool[num];
for(int i=0;i<num;i++){
visit[i]=false;
}
queue<int> q;
q.push(x);
while(!q.empty()){
int s=q.front();
q.pop();
if(!visit[s]){
visit[s]=true;
cout<<s<<" ";
list<int>::iterator it;
for(it=ls[s].begin();it!=ls[s].end();it++){
q.push(*it);
}
}
}
}
// Print the Adjacency List
void print(list<int> *ls,int num){
list<int>::iterator it;
for(int i=0;i<6;i++){
cout<<i<<"-->";
for(it=ls[i].begin();it!=ls[i].end();it++){
cout<<*it<<"-->";
}
cout<<endl;
}
}
int main(){
int num=6;
cout<<"Enter the no. of vertices : 6\n";
list<int> *ls=new list<int>[num];
addedge(ls,0,2);
addedge(ls,2,3);
addedge(ls,3,4);
addedge(ls,4,5);
addedge(ls,2,5);
addedge(ls,1,4);
addedge(ls,3,0);
cout<<"Print of adjacency list:"<<endl;
print(ls,6);
cout<<"BFS"<<endl;
BFS(ls,6,0);
return 0;
}

Output

廣度優先搜索是一個逐層的頂點遍歷過程。 像一棵樹一樣，所有圖都具有頂點，但是圖卻具有循環，因此為了避免出現相同的頂點，我們選擇了BFS

算法：

為了實現BFS，我們使用隊列和數組數據結構。

該算法有兩種情況：

1. 每當我們訪問頂點時，都會將其標記為已訪問，并將其相鄰的未訪問頂點推入隊列，然后從隊列中彈出當前頂點。

2. 如果訪問了所有相鄰的頂點，則僅從隊列中彈出當前頂點。

考慮一下這張圖，

根據我們的算法，遍歷繼續像

因此，所有頂點都將被訪問，然后僅執行彈出操作，并且隊列最終將為空。

C ++實現：

 # include  < bits/stdc++.h >
using namespace std ;
//	Make a pair between vertex x and vertex y 
void addedge ( list < int > * ls , int x , int y ) {
ls [ x ] . push_back ( y ) ;
ls [ y ] . push_back ( x ) ;
return ;
} 
//Breath First Search of a Graph
void BFS ( list < int > * ls , int num , int x ) {
bool * visit = new bool [ num ] ;
for ( int i = 0 ; i < num ; i + + ) {
visit [ i ] = false ;
}
queue < int > q ;
q . push ( x ) ;
while ( ! q . empty ( ) ) {
int s = q . front ( ) ;
q . pop ( ) ;
if ( ! visit [ s ] ) {
visit [ s ] = true ;
cout < < s < < "   " ;
list < int > :: iterator it ;
for ( it = ls [ s ] . begin ( ) ; it ! = ls [ s ] . end ( ) ; it + + ) {
q . push ( * it ) ;
}
}
}
}
// Print the Adjacency List
void print ( list < int > * ls , int num ) {
list < int > :: iterator it ;
for ( int i = 0 ; i < 6 ; i + + ) {
cout < < i < < " --> " ;
for ( it = ls [ i ] . begin ( ) ; it ! = ls [ i ] . end ( ) ; it + + ) {
cout < < * it < < " --> " ;
}
cout < < endl ;
}
}
int main ( ) {
int num = 6 ;
cout < < " Enter the no. of vertices : 6 \n " ;
list < int > * ls = new list < int > [ num ] ;
addedge ( ls , 0 , 2 ) ;
addedge ( ls , 2 , 3 ) ;
addedge ( ls , 3 , 4 ) ;
addedge ( ls , 4 , 5 ) ;
addedge ( ls , 2 , 5 ) ;
addedge ( ls , 1 , 4 ) ;
addedge ( ls , 3 , 0 ) ;
cout < < " Print of adjacency list: " < < endl ;
print ( ls , 6 ) ;
cout < < " BFS " < < endl ;
BFS ( ls , 6 , 0 ) ;
return 0 ;
}

輸出量

翻譯自: https://www.includehelp.com/data-structure-tutorial/breadth-first-search-bfs-of-a-graph.aspx

bfs廣度優先搜索算法