数据结构搜索算法之广度优先搜索 (BFS)
BFS思路(伪代码):
BFS(G,s){
//初始化图(标记):颜色、父节点、距离
for(each vertex u∈V[G]-s){
color[u]=WHITE;
parent[u]=null;
d[u]=∞;
}
//初始化源节点s
color=GRAY;
parent[s]=null;
d[s]=0;
Que=φ;
enqueue(Que,s);//把s加到队尾
for(each vertex v∈Adj[u]){//把u所有未被搜索的下级节点加到Que
if(color==WHITE){
color=GRAY;
parent[v]=u;
d[v]=d[u]+1;
enqueue(v);//进队列
}
}
}