算法学习--广度优先遍历和深度优先遍历

一、广度优先遍历 (BFS）

广度优先遍历顾名思义就是优先搜索横向范围内的数据，直到找到目标节点为止，用于求解最短路径问题。
算法思想：从起点开始，将起点的所有子节点添加进一个队列中（已经遍历过的节点不可重复添加），然后依次类推，将子节点的子节点也加入队列中，当队列为空时或者找到目标节点时算法结束。

如上图，求A到G的最短距离（默认每个边的权值为1），并输出
广度优先遍历的求解步骤：

1. 将起点A放入到队列S中，S={A}，用Depth表示距离，默认值为0
2. 从队列S中取出第一个元素，因为队列有先进先出（FIFO）原则，所以我们可以得到节点A，然后将节点A的所有子节点添加到队列S中，此时S={B,C},此时队列S中的节点都为同级节点，所以Depth = Depth+1,即Depth = 1
3. 重复第2步操作，此时S={C,D,E}，此时因为队列S中的节点不都是同级节点，所以Depth的值保持不变，
4. 重复第2步操作，此时S={D,E,F}，此时队列S中同时存在B节点和D节点的子节点，但是因为节点B和节点D是同级节点，所以他们的子节点也是同级节点，即此时队列S中的节点都为同级节点，所以Depth = Depth+1,即Depth = 2
5. 此时我们从队列中取出的元素为D，D节点的子元素有节点B和E，因为节点B已经遍历过，并且已经出了队列，而节点E当前正在队列中，所以不需要重复添加，即S={E,F}，虽然此时队列S中的节点为同级节点，但是在步骤4中我们已经对节点E和节点F的同级节点进行过一次累加，所以此时Depth不需要改变
6. 重复第2步操作,此时出队列的为节点E，节点E的子元素有节点B,D,F,G,这四个子节点中除了节点G还没有遍历过，并且不再队列S中，所以只需要将节点G加入队列S即可，S={F,G}，此时队列S中的节点不都是同级节点，所以Depth不变
7. 再次从队列中取出一个元素，即元素F，节点F的所有子节点都已经遍历过，所以不需要改变队列S，即S={G}，此时队列S中的元素为同级元素，所以Depth = Depth+1,即Depth = 3
8. 再次从队列中取出一个元素，即元素G，节点G的子节点只有节点E，但是E已经别遍历过了，所以不能添加进队列S，即S={}，当S为空时，算法结束。
   注：Depth应该在什么时候累加，什么时候不累加呢？可以采用两种方法判断:
   方法一：标记法就是在队列S中添加一个特殊的标记位，当从队列中取出的元素为标记位时Depth加累加一次。
   以上图为例：节点A的子元素有节点B和C，所以当节点B和节点C进入队列后，应该在其后添加一个标记位（以@为标记），S={B,C,@},当节点B出队列后，S={C,@,D,E};
   节点C出队列后，S={@,D,E,F};
   当再次从队列中取出元素时，我们发现该元素时标记位@，所以此时Depth = Depth + 1,并且更新S={D,E,F,@},所以当取出的元素为标记位时，应该做两步操作，第一步是给Depth加1，第二步给队列中添加新的标记位。
   方法二：计数法使用两个变量Count1和Count2，分别统计队列S中当前节点的同级的子节点个数（Count1）和当前节点的同级的子节点的同级的子节点个数（Count2）.当Count1 = 0，Count2 != 0时，Depth = Depth+1.
   已上图为例：节点A的同级子节点有节点B和节点C，所以Count1 = 2，Count2 = 0，
   节点B出队列后，Count1 = 1，Count2 =2，因为节点B有两个子节点D和E，所以Count2 =2，因为节点B出队列了，所以Count1 = 1；
   节点C出队列后，Count1 = 0，Count2 =3，此时**因为Count1=0，表示存在一级的元素已经全部出了队列，所以Depth = Depth+1.并且Count1 = Count2,Count2 = 0;**以此类推就可计算出A到G的最短距离。

算法实现：
首先将上图转换为邻接矩阵(1：相连；0：不相连）：

JAVA代码实现

static int[][] source;

	public static void main(String[] args) {
   
		source = new int[][] {
    
		{
    0, 0, 0, 0, 0, 0, 0, 0 }, 
		{
    0, 0, 1, 1, 0, 
1
2
3
4
5
6
7
8
9