欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

BFS广度优先算法

程序员文章站 2022-05-21 11:25:31
...

用BFS广度优先算法遍历整个图(用邻接矩阵表示图)

BFS核心代码:

#include<iostream>
#include<string>
#include<queue>
using namespace std;


struct Graph1 //使用邻接矩阵来构造图
{
    int v;  //图的顶点数
    int e;    //图的边数
    int ** arc;  //邻接矩阵
    int kind;    //0,为有向图,1,为无向图
    string * info; //表示每个顶点的信息

};

void BFS (Graph1 g, int begin) 
{
    bool * visit;
    queue<int>  q;
    visit = new bool[g.v];
    int i;
    for (i = 0; i < g.v; i++) 
        visit[i] = false;
    cout << "BFS遍历:" << endl;
    for (int v = 0; v < g.v; v++) 
{
        if (!visit[(begin-1 + v) % g.v])
        {
            cout << g.info[(begin - 1 + v) % g.v] << " ";
            visit[(begin - 1 + v) % g.v] = true;
            q.push((begin - 1 + v) % g.v);//初始化queue
            while (!q.empty())
            {
                int u = q.front();
                q.pop();
                for (int j = 0; j < g.v; j++) {
                    if (g.arc[u][j] == 0 || g.arc[u][j] == INT_MAX) { //如果两个顶点之间没有边
                        continue;
                    }
                    else if (!visit[j] ) //先访问所有和u相连的顶点,
{                       
cout << g.info[j] << " ";
                        visit[j] = true;
                        q.push(j);
                    }
                }
            }
        }
    }
}


相关标签: bfs 遍历 c++