广度优先算法
程序员文章站
2022-05-21 11:21:59
...
伪代码
//广度优先算法,类似于二叉树的层次遍历
/*
利用队列实现搜索
首先访问起始顶点v,接着由v出发,依次访问v的各个未访问的邻接结点w1,w2,,,
然后依次访问w1,w2,wi这些所有没有被访问的结点
再从这些访问过的顶点出发,访问它们所有未被访问的结点,直至图中所有的顶点都被访问为止。
*/
bool visited[MAX_VERTEX_NUM];//访问标记数组
void BFSTraverse(Graph G) {
//对图G进行广度优先遍历
for (int i = 0; i < G.vexnum; ++i) {
visited[i] = false;//访问标记数组初始化
}
InitQueue(Q);//初始化一个辅助队列Q
for (int i = 0; i < G.vexnum; ++i) {//从0号结点开始遍历
if (!visited[i]) {//对于每个连通分量调用一次BFS
BFS(G, i);//vi未被访问过,从vi开始BFS
}
}
}
void BFS(Graph G, int v) {
//从顶点v出发,广度优先遍历图G
visit(v);//访问初始顶点v
visited[i] = true;//对v做已访问标记
Enqueue(Q, v);//顶点v入队列Q
while (!isEmpty(Q)) {
DeQueue(Q, v);//顶点v出队列
for (w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w)) {
//检查v所有的邻接点
if (!visited[w]) {//w是v尚未访问的邻接顶点
visit(w);
visited[w] = true;//对w做已访问标记
Enqueue(Q, w);//顶点w入队列
}
}
}
}
下一篇: 广度优先算法(BFS)