一个图的遍历问题

设计数据库的存储形式存储帝都的地铁站信息，并求出从一个地点上车在不出站并且不重复的情况下最多能经过多少站，并把乘坐的站信息列出来。

很早以前在看书的时候里面有专门的章节介绍了图的遍历，当时里面的图的信息存储方式用的是二维数组。比如一共有5个点，数组大小是5*5,array[1][2] 的值如果不为规定的正无穷则表示这1和2两点之间不能直接连通，否则表示从点1到点2之间的距离为array[1][2]，表示有向图的时候a[2][1]为正无穷,这样的表示非常直观，运算上也方便缺点是在图的顶点数比较多，但是连接数不多的时候会造成空间浪费，可以参考使用邻接表优化。

数据库中存储图的连接信息可以如下设计
id表示一条连通记录，from表示起始站的id，end表示终止点的id

      private $stations = [
        ['id' => 1, 'from' => 1, 'end' => 2],
        ['id' => 2, 'from' => 2, 'end' => 3],
        ['id' => 3, 'from' => 3, 'end' => 4],
        ['id' => 4, 'from' => 4, 'end' => 5],
        ['id' => 5, 'from' => 5, 'end' => 3],
        ['id' => 6, 'from' => 2, 'end' => 5],
        ['id' => 7, 'from' => 3, 'end' => 1],
        ['id' => 8, 'from' => 1, 'end' => 5],
    ];

可以将数据库的信息读取出来后再根据需要转换为二维数组或者邻接表的形式，也可以直接用。二维数组直接把起始点id和终止点id作为下标就能得到站点的连接信息，这里就是需要遍历而已。实现起来也很简单，就是图的深度优先遍历。

<?php
/*/**
 * Created by PhpStorm.
 * User: guodong
 * Date: 18/6/28
 * Time: 下午10:43
 */

class Station
{

    private $stations = [
//        ['id' => 1, 'from' => 1, 'end' => 2],
//        ['id' => 2, 'from' => 2, 'end' => 3],
//        ['id' => 3, 'from' => 3, 'end' => 4],
//        ['id' => 4, 'from' => 4, 'end' => 5],
//        ['id' => 5, 'from' => 5, 'end' => 3],
//        ['id' => 6, 'from' => 2, 'end' => 5],
//        ['id' => 7, 'from' => 3, 'end' => 1],
//        ['id' => 8, 'from' => 1, 'end' => 5],
        ['id' => 1, 'from' => 1, 'end' => 2],
        ['id' => 2, 'from' => 2, 'end' => 3],
        ['id' => 3, 'from' => 3, 'end' => 4],
        ['id' => 4, 'from' => 1, 'end' => 5],
        ['id' => 5, 'from' => 5, 'end' => 6],
        ['id' => 6, 'from' => 1, 'end' => 7],
        ['id' => 7, 'from' => 1, 'end' => 8],
        ['id' => 8, 'from' => 1, 'end' => 11],
        ['id' => 9, 'from' => 4, 'end' => 5],
    ];

    //深度优先搜索使用 getMaxStations
    public $visit = [];
    public $curMaxLength = 0;
    public $allRoutes = [];
    //广地优先搜索使用
    public $queue = [];
    public $book = [];

    //换成次数 leastTrans
    public $transTimes = 9999999;
    public $book2 = [];


    //求一点开始，在不出站的情况下可以不重复的坐最多多少站地铁,需要把所有的都存下来 （图的深度优先搜索遍历）
    //深度优先遍历
    function getMaxStations($startId = 5)
    {
        foreach ($this->stations as $station) {
            $flag = 0 ;
            if ($station['from'] == $startId && !isset($this->visit[$station['end']])) {
                $flag = 1;
                $this->visit[$station['end']] = 1;
                $this->getMaxStations($station['end']);
                unset($this->visit[$station['end']]);
            }
            if ($flag == 0) {
                $route = implode(",",array_keys($this->visit));
                if (!in_array($route, $this->allRoutes) && $route){
                    $this->allRoutes[] = $route;
                }
            }
        }
    }

    /*
     * 图的广度优先搜索
     */
    public function bfs($startId = 1)
    {
        array_push($this->queue, $startId);
        $this->book[] = $startId;
        //队列不为空
        while (!empty($this->queue)) {
            $startId = array_shift($this->queue);
            print $startId; //打印访问的节点
            foreach ($this->stations as $station) {
                if ($station['from'] == $startId && !in_array($station['end'], $this->book)) {
                    $this->book[] = $station['end'];
                    array_push($this->queue, $station['end']);
                }
            }

        }
    }

    /**
     * 求任意两点间的最少换成次数和细节
     * @param $startId
     * @param $endId
     */
    public function leastTrans($startId, $endId, $curTimes = 0)
    {

        //当前转战的次数大于已经记录的转战次数则放弃继续深度搜索
        if ($curTimes > $this->transTimes) {
            return;
        }
        if ($startId == $endId) {
            $this->transTimes = count($this->book2);
            print_r($this->book2);
        }
        //book2用来存储是否已经访问
        foreach ($this->stations as $station) {
            if ($station['from'] == $startId && !in_array($station['end'], $this->book2)) {
                array_push($this->book2, $station['end']);
                $this->leastTrans($station['end'], $endId, $curTimes + 1);
                array_pop($this->book2);

            }
        }
    }
}

$tool = new Station();
////
////$tool->leastTrans(1, 5);
////print_r($tool->transTimes);
//
$tool->getMaxStations(1);
print_r($tool->allRoutes);
$all = usort($tool->allRoutes,function ($val1,$val2){
   return strlen($val1) < strlen($val2);
});

print_r($tool->allRoutes);