广度优先算法BFS

广度优先算法原理就是一个队列，先取一个初始点，然后找出所有临界的点放入队列，等上一层的消耗完了，就会消耗下一层的，以此类推。

<?php 

//BFS，广度优先算法
/*

例子中的图

        B   *****   D   *****  F
      * *         * *
   *    *        *  *
A       *      *    *
   *    *    *      *
     *  *  *        *
        c   *****   E

*/

//列出每个点的临界点
$graph = [
    'A' => ['B', 'C'],
    'B' => ['A', 'C', 'D'],
    'C' => ['A', 'B', 'D', 'E'],
    'D' => ['B', 'C', 'E', 'F'],
    'E' => ['C', 'D'],
    'F' => ['D'],
];

//广度优先是队列
function BFS($graph, $s){//$s为开始的点
    $queue = [];
    $in = [];
    $in[$s] = 1;
    array_push($queue, $s);
    while(count($queue) > 0){
        $vertex = array_shift($queue);//消耗最前面的点，队列先进先出
        $nodes = $graph[$vertex];
        foreach($nodes as $w){
            if(!isset($in[$w])){//没有插入过
                array_push($queue, $w);
                $in[$w] = 1;
            }
        }
        echo $vertex;
    }
}

BFS($graph, 'A');//A为起点触发

扩展1
leetcode 102中，有计算二叉树的层序遍历，这个图也可以来计算下每层的元素
具体思路：以A为起点，每层的目标是这样的： A | BC | DE | F ，需要知道是否是每层的最后一个，是的话下次层就加1。

那么如何知道当前元素所在层的最后一个元素是什么呢？
比如当前在x层，其实在x-1层就知道x层的最后一个是什么了。原因是在x-1层的最后一个时，queue里的最后一个肯定是x层的最后一个元素。所以就可以有一个每层的元素对于当前层最后一个的关系（见下面的希望得到例子），当到达每层的最后一个元素时，就可以缓存住下层的最后一个元素tmp，在遍历x+1层的时候，已经有了x+1层的最后一个元素，直接重复上述逻辑判断。
希望得到:
B C //B时最后一个是C。1个动作，放入元素
C C //C时最后一个是C。3个动作，放入元素、层加1、得到下层的最后一个元素
D E
E E
F F

代码见：

function BFS($graph, $s){//$s为开始的点
    $queue = [];
    $in[$s] = 1;
    $result = [];
    array_push($queue, $s);
    $flag = 1;
    $lastValue = '';
    while(count($queue) > 0){
        $vertex = array_shift($queue);//消耗最前面的点，队列先进先出
        $nodes = $graph[$vertex];
        if($flag){
            $lastValue = end($nodes);//初始化的下一层的最后一个元素
        }
        if(isset($tmp)){//当到达每一层的最后一个时候，需要知道下一层的最后一个是多少
            $lastValue = $tmp;
        }
        foreach($nodes as $w){
            if(!isset($in[$w])){//没有插入过
                array_push($queue, $w);
                $in[$w] = 1;
            }
        }
        if($vertex == $lastValue){
            //跑当前层的时候，知道当前层的最后一个是多少（因为肯定在上层已经计算出来了），
            //所以当vertex等于那个值的时候（说明是最后一个了），又可以计算下一层的最后一个了
            $flag = 1;
            $tmp = end($queue);
        }else{
            $flag = 0;
        }
        
        if($vertex == $s){
            $result[0][] = $vertex;
            $j++;
        }elseif($vertex == $lastValue){
            $result[$j][] = $vertex;
            $j++;
        }elseif($vertex != $lastValue){
            $result[$j][] = $vertex;
        }
        echo $vertex.$lastValue."<br>";
    }
    return $result;
}