图的广度优先遍历

首页 » 算法 » 图的广度优先遍历

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

  • 广度优先遍历的步骤

* 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);
  }
 }
}

 

分享到:
赞(0) 打赏

评论 2

评论前必须登录!

 

  1. #1

    可以

    你哥4个月前 (05-26)
  2. #2

    我给你点赞了

    小蚯蚓4个月前 (05-26)

觉得文章有用就打赏一下弟弟吧

支付宝扫一扫打赏

微信扫一扫打赏

Vieu4.5主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。
正在播放:

作者想对您说:

累了就停下来听首歌吧

听完后会给您一个好心情

最后

等到您不容易

还希望您能多待一会儿

      00:00/00:00