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);
}
}
}
}
}
}
上一篇: Python - 多继承中的super()与MRO
下一篇: POJ3984——迷宫问题