C++STL实现图的深度与广度优先遍历（BFS&DFS）

里克贝斯

发布于 2021-05-21 15:45:00

1.8K00

代码可运行

文章被收录于专栏：图灵技术域图灵技术域

运行总次数：0

代码可运行

C语言数据结构图的基本操作及遍历（存储结构为邻接矩阵）请查看：https://cloud.tencent.com/developer/article/1827604

邻接表的存储结构遍历请看

https://www.omegaxyz.com/2017/05/16/graphofds/

下面给出C++STL实现图的深度与广度优先遍历（BFS&DFS）

其中BFS需要用栈，DFS需要用队列

下面算法所用的图为：

代码：

C++

//Author: Xu Yi
//www.omegaxyz.com

#include<iostream>
#include<stack>
#include<queue>
#include<cstring>
#define MAX 100

using namespace std;

stack<int> BFS_Stack;
queue<int> DFS_Queue;
int G[MAX][MAX];
int visit[MAX];
int V,E;

void BFS(int s){
    cout<<"BFS"<<endl;
    int i,j,node;
    memset(visit,0,sizeof(visit));
    BFS_Stack.push(s);
    while(!BFS_Stack.empty()){
        node=BFS_Stack.top();
        BFS_Stack.pop();
        if(visit[node])continue;
        visit[node]=1;
        cout<<node<<"-->";
        for(i=0;i<V;i++){
            if(G[node][i])BFS_Stack.push(i);
        }
    }
    cout<<"NULL"<<endl;
}

void DFS(int s){
    cout<<"DFS"<<endl;
    int i,j,node;
    memset(visit,0,sizeof(visit));
    DFS_Queue.push(s);

    while(!DFS_Queue.empty()){
        node=DFS_Queue.front();
        DFS_Queue.pop();
        if(visit[node])continue;
        visit[node]=1;
        cout<<node<<"-->";
        for(i=0;i<V;i++)
            if(G[i][node])DFS_Queue.push(i);
        for(j=0;j<V;j++)
            if(G[node][j])DFS_Queue.push(j);
    }
    cout<<"NULL"<<endl;
}


////////////////////////////////
int main()
{
    memset(visit,0,sizeof(visit));
    memset(predecessor,0,sizeof(predecessor));
    memset(G,0,sizeof(G));
    G[0][1]=1;
    G[1][2]=1;
    G[1][3]=1;
    G[3][5]=1;
    G[3][4]=1;
    G[3][7]=1;
    G[4][6]=1;
    G[7][4]=1;
    V=8;
    BFS(0);
    DFS(0);
    cout<<endl;
    return 0;
}

结果: