深度优先算法DFS

与BFS的区别就是一个是取先放的array_shift，一个是取后放的array_pop

<?php 

//DFS，深度优先算法
/*

例子中的图

        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 DFS($graph, $s){//$s为开始的点
    $stack = [];
    $in = [];
    $in[$s] = 1;
    array_push($stack, $s);
    while(count($stack) > 0){
        $vertex = array_pop($stack);//消耗最后面的点，先进后出
        $nodes = $graph[$vertex];
        foreach($nodes as $w){
            if(!isset($in[$w])){//没有插入过
                array_push($stack, $w);
                $in[$w] = 1;
            }
        }
        echo $vertex;
    }
}

DFS($graph, 'E');