图的广度优先遍历算法的实现
（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。
阅读(4338) | 评论(0) | 转发(0) |
