分层搜索的过程，广度优先遍历需要使用一个队列以保持访问过的节点的顺序，以便按这个顺序来访问这些节点的邻接节点 。

• 广度优先遍历的步骤

* 1、访问初始节点v并标记节点v为已访问。
* 2、节点v入队列
* 3、当队列非空时，继续执行，否则算法结束
* 4、出队列，取得队头节点u
* 5、查找节点u的第一个邻接节点w
* 6、若节点u的邻接节点w不存在，则转到步骤3;否则循环执行以下三个 步骤：
    * 6.1 若节点w尚未被访问，则访问节点w并标记为已访问。
   * 6.2 节点w入队列
   * 6.3 查找节点u的继w邻接节点后的下一个邻接节点w，转到步骤6

private void bfs(boolean[] isvisited,int i) {
 int u;//表示队列的头节点对应的下标
 int w;//邻接节点w
 //队列，记录节点访问的顺序
 LinkedList queue = new LinkedList();
 //访问节点，输出节点信息
 System.out.println(getvelau(i)+"=>");
 //标记为已经访问
 isvisited[i]=true;
 //将节点加入队列中
 queue.addLast(i);
 
 while(!queue.isEmpty()) {
  //取出队列的头节点下标
  u=(Integer)queue.removeFirst();
  //得到第一个邻接节点的下标w
  w=getfirst(u);
  while(w!=-1) {//找到
   //是否访问过
   if(!isvisited[w]) {
    System.out.println(getvelau(w)+"=>");
    //标记已经被访问
    isvisited[w]=true;
    //入队
    queue.addLast(w);
   }
   //如果访问过，以u为前驱节点找w后面的下一个邻接点。
   w=getnext(u, w);
  }
 }
}
public void bfs() {
 for(int i=0;i<getbnum();i++) {
  if(!isvisited[i]) {
   bfs(isvisited,i);
  }
 }
}

分享到：

赞(1) 打赏