PHP implementation of "depth-first search" on the graph data structure As I am a totally self-taught 'person writing code', I decided to learn algorithms with one online course that taught them using Java for demonstrative purposes. The first topic I covered is the graph data structure and API.

I undertook to rewrite Java examples into PHP for training purposes. I would be really grateful if you could review this code and point to its biggest shortcoming. 

It was not always possible to reproduce certain behaviours and data structure that are found in Java so I had to resort to some workarounds.

Here is the code with explanations:

/**
* Bag stores all vertices adjacent to a given vertex.
* It's here to imitate Java's 'Bag' data structure
*/
class Bag implements IteratorAggregate
{
    public $vs = array();

    public function getIterator()
    {
        return new ArrayIterator($this-&gt;vs);
    }
}


-

class Graph
{

    private $V;

    /* Adjacent vertices */
    private $adj = array();

    /**
    * @param int $V The total number of vertices in the graph
    */
    public function __construct($V)
    {
        $this-&gt;V = $V;
        for ($v = 0; $v &lt; $V; $v++) {
            $this-&gt;adj[$v] = new Bag;
        }
    }

    /**
    * Throw all adjacent vertices of a given vertex into this vertex' Bag.
    * This will create 'edges' - connection between vertices.
    * 
    * @param int $v Vertex to connect
    * @param int $w Vertex to connect
    */
    public function addEdge($v, $w)
    {
        $this-&gt;adj[$v]-&gt;vs[] = $w;
        $this-&gt;adj[$w]-&gt;vs[] = $v;
    }

    /**
    * @return Bag All ajacent vertices of a given vertex
    */
    public function returnBag($v)
    {
        return $this-&gt;adj[$v];
    }

    public function returnAllVertices()
    {
        return $this-&gt;adj;
    }

}


-

class DepthFirstPath
{
    private $marked = array();

    /* This array stores parent-link representation  of a tree rooted at $s (source) */
    private $edgeTo = array();

    private $s;

    /**
    * @param Graph $G An instance of the graph
    * @param int $s Source vertex to start the recursive traversal from
    */
    public function __construct(Graph $G, $s)
    {
        $allVertices = $G-&gt;returnAllVertices();

        /* Set all verices in the graph as unvisited/unmarked */
        foreach($allVertices as $key =&gt; $value) {
            $this-&gt;marked[$key] = false;
            foreach($value-&gt;vs as $v) {
                $this-&gt;marked[$v] = false;
            }
        }

        $this-&gt;s = $s;      
        $this-&gt;dfs($G, $s);

    }

    /**
    * 'Depth-first search'
    *
    * A recursive function that will visit all adjacent vertices of each vertex
    * and mark each of them as 'visited'
    */
    private function dfs(Graph $G, $v)
    {
        $this-&gt;marked[$v] = true;
        $adjToV = $G-&gt;returnBag($v);
        foreach($adjToV as $w) {
            if ( ! $this-&gt;marked[$w] ) {
                $this-&gt;dfs($G, $w);
                $this-&gt;edgeTo[$w] = $v;
            }
        }
    }

    public function hasPathTo($v)   
    {
        return $this-&gt;marked[$v];
    }

    /**
    * Find a path from the source to a given vertex
    */
    public function pathTo($v)
    {
        if ( ! $this-&gt;hasPathTo($v)) {
            return null;
        }

        $path = new \SplStack;
        for ($x = $v; $x != $this-&gt;s; $x = $this-&gt;edgeTo[$x]) {
            $path-&gt;push($x);
        }
        $path-&gt;push($this-&gt;s);
        return $path;
    }
}


This is how the client might use it (feel free to copy, paste and try it):

$graph = new Graph(10);
$graph-&gt;addEdge(1,2);
$graph-&gt;addEdge(2,3);
$graph-&gt;addEdge(3,4);
$graph-&gt;addEdge(1,6);
$graph-&gt;addEdge(8,9);

$path = new DepthFirstPath($graph, 1);
$path-&gt;pathTo(4);


What have I done wrong, what could I improve, what rules have I violated ?
It's totally unnecessary to have a Bag class if all you do is reach through to its only field.

Generally, all your classes should either have multiple fields or engage in some kind of non-trivial validation or data-hiding to justify the necessity for a class.