Chinaunix首页 | 论坛 | 博客
  • 博客访问: 186611
  • 博文数量: 19
  • 博客积分: 226
  • 博客等级: 二等列兵
  • 技术积分: 318
  • 用 户 组: 普通用户
  • 注册时间: 2012-07-23 09:09
文章分类

全部博文(19)

文章存档

2013年(12)

2012年(7)

分类: C/C++

2013-04-22 15:59:27

图的广度优先遍历算法的实现

(1)、准备
   需要一个标志数组a[length],其中length的大小为图的结点的个数,并初始化为0,表示初始时刻所有结点都未被访问过。需要一个队列的数据结构,用来辅助实现该算法。
(2)、步骤
   a、任选图中的一个结点作为起始点i,并令该节点的标志数组元素a[i]为1,表示已经访问过,同时让a[i]入队列。
  b、接下来将a[i]的所有邻接点入队,将邻接点的标志数组的值更改为1,表示已访问过,同时将a[i]出队列。
  c、访问队列的第一个元素,同时将该队列的未被访问到的邻接点入队,并将它们对应的标志数组值赋值为1,同时让队首元素出队。
  d、对队列重复上面的过程,直至队为空。
  e、这时检查标志数组,如果全部为1,说明遍历完成;如果遇到为0的元素,则将该元素作为第二次广搜的起始值,重复a、b、c、d。
  f、继续检查标志数组,转到e。
阅读(4378) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~