<?php
class Walker {
    public $graph, $path;

    public function __construct($graph) {
        $this->graph = $graph;
        $this->path = [];
    }

    public function DepthRec($node) { //РЕКУРРЕНТНЫЙ ОБХОД ВГЛУБИНУ
        $this->path[$node] = true;
        foreach ($this->graph->getEdges($node) as $node2 => $length)
            if (!$this->path[$node2])
                $this->DepthRec($node2);
    }

    public function DepthIter($node) { //ИТЕРАТИВНЫЙ АЛГОРИТМ ОБХОДА ГРАФА ВГЛУБИНУ
        $path = [];
        $stack = new Stack();
        $stack->put($node);
        while ($stack->last != null) {
            $curr = $stack->get();
            $path[$curr] = true;
            foreach ($this->graph->getEdges($curr) as $node2 => $length)
                if (!$path[$node2] && !$stack->contains($node2))
                    $stack->put($node2);
        }
        return $path;
    }

    function waves($node) { //ИТЕРАТИВНЫЙ АЛГОРИТМ ОБХОДА ГРАФА В ШИРИНУ
        $path = [];
        $wayToNode = [];
        $queue = new Queue();
        $queue->put($node);
        $wayToNode[$node] = 0;
        while ($queue->first != null) {
            $curr = $queue->get();
            $path[$curr] = true;
            foreach ($this->graph->getEdges($curr) as $node2 => $length)
                if (!$path[$node2] && !$queue->contains($node2)) {
                    $queue->put($node2);
                    if (!$wayToNode[$node2])
                        $wayToNode[$node2] = $wayToNode[$curr] + 1;
                }
        }
        return $wayToNode;
    }

    function shortestWay($node1, $node2) {
        $ways = $this->waves($node2);
        $nodes = $node1;
        $shortestWay[] = $node1;
        for ($i = 0; $i < $ways[$node1]; $i++) {
            foreach ($this->graph->getEdges($nodes) as $k => $v)
                if ($ways[$k] == $ways[$node1] - 1 - $i) {
                    $shortestWay[] = $k;
                    $nodes = $k;
                    break;
                }
        }
        return $shortestWay;
    }
}