<?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;
    }

    public function waves($node) { //ИТЕРАТИВНЫЙ АЛГОРИТМ ОБХОДА ГРАФА В ШИРИНУ
        $path = [];
        $queue = new Queue();
        $queue->put($node);
        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);
        }
        return $path;
    }
}