数据结构搜索算法之广度优先搜索 (BFS)

数据结构搜索算法之广度优先搜索 (BFS)

数据结构搜索算法之广度优先搜索 (BFS)

数据结构搜索算法之广度优先搜索 (BFS)

数据结构搜索算法之广度优先搜索 (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);//进队列

    }

  }

}