C++中的广度优先搜索

Posted on by

Breath First Search是一种用于图数据结构的图遍历技术。它逐级进行。图是树状的数据结构。为了避免在遍历图的过程中访问节点，我们使用BFS。

在这个算法中，假设我们从节点 x 开始，然后我们将访问 x 的邻居，然后访问 x 的邻居的邻居，依此类推。

算法

为了使用BFS遍历图，我们使用队列来存储节点和数组数据结构来区分未访问的节点。

  • 1 . 创建空队列并将未访问的顶点推送到它。
  • 2 . 除非队列为空，否则请执行以下操作。
    • 2.1从队列中弹出元素
    • 2.2将弹出节点的未访问的相邻节点推入队列。

考虑这张图

根据我们的算法

因此访问了所有顶点，然后执行唯一的弹出操作，然后队列将为空。

#include <bits/stdc++.h>
 
using namespace std;
 
void connect_edges(list<int>,int ,int );
void BFS(list<int>*,int);
 
void connect_edges(list<int> *lst,int X,int Y){
    //for the undirected graph we have to make a link of X-->Y and Y-->X
    lst[X].push_back(Y);
    lst[Y].push_back(X);
    return;
}
 
void BFS(list<int>*lst,int count,int X){
    //created a boolean array to find out the unvisited nodes
    bool *visited= new bool[count];
    for(int i=0;i<count;i++){
        visited[i]=false;
    }
    queue<int> q;
    q.push(X);
    while(!q.empty()){
        int ele=q.front();
        q.pop();
        //take one element from the queue and check the element is
        //unvisited or not
        if(!visited[ele]){
            visited[ele]=true;
            //print the unvisited nodes
            cout<<ele<<" ";
            list<int>::iterator it;
            for(it=lst[ele].begin();it!=lst[ele].end();it++){
                q.push(*it);
            }
        }
    }
}
// Print the Adjacency List
void print(list<int> *lst,int count){
    list<int>::iterator it;
    for(int i=0;i<count;i++){
        cout<<i<<"-->";
        for(it=lst[i].begin();it!=lst[i].end();it++){
            cout<<*it<<"-->";
        }
        cout<<endl;
    }
}
 
int main(){
    int count;
    cout<<"Enter the no. of vertices : ";
    cin>>count;
    cout<<endl;
    list<int> *lst=new list<int>[count];
    connect_edges(lst,0,1);
    connect_edges(lst,0,2);
    connect_edges(lst,2,4);
    connect_edges(lst,3,2);
    connect_edges(lst,4,5);
    connect_edges(lst,3,5);
    connect_edges(lst,1,3);
    connect_edges(lst,5,0);
    cout<<"Adjacency matrix: "<<endl;
    print(lst,count);
    cout<<"BFS : "<<endl;
    BFS(lst,count,0);
 
    return 0;
}

输出：

Adjacency matrix:
0–>1–>2–>5
1–>0–>3
2–>0–>4–>3
3–>2–>5–>1
4–>2–>5
5–>4–>3–>0
BFS :
0 1 2 5 3 4

这就是 C++ 中广度优先搜索的全部内容。

推荐阅读：