A simple Graph implementation with a DFS and BFS traversal algorithms.

Graph.php

<?php

class GraphNode {

    public $data;
    public $adiacent_nodes;

    public function __construct($data, $adiacent_nodes)
    {
        $this->data = $data;
        $this->adiacent_nodes = $adiacent_nodes;

    }

    public function getData()
    {
        return $this->data;
    }

    public function getAdiacentNodes()
    {
        return $this->adiacent_nodes;
    }

}


class Node {

    public $data;
    public $next;

    public function __construct($data)
    {
        $this->data = $data;
        $this->next = NULL;

    }

    public function getData()
    {
        return $this->data;
    }


}


class Stack {

    private $top;

    public function __construct()
    {
        $this->top = NULL;
    }

    public function push($data) {

        $new = new Node($data);
        $new->next = $this->top;
        $this->top = &$new;

    }

    public function pop() {

        if($this->isEmpty()) throw new Exception("Stack is empty");
        $top = $this->top;
        $this->top = $this->top->next;
        return $top->getData();

    }

    public function peek() {

        if($this->isEmpty()) throw new Exception("Stack is empty");
        return $this->top->getData();
    }

    public function isEmpty() {
        return $this->top == NULL;
    }


}

class Queue {

    private $head;
    private $tail;

    public function __construct()
    {
        $this->head = $this->tail = NULL;
    }

    public function isEmpty() {
        return $this->head == NULL;
    }

    public function enqueue($data) {

        $new = new Node($data);
        if($this->tail == NULL) {
            $this->head = &$new;
        }
        else {
            $this->tail->next = &$new;
        }
        $this->tail = &$new;
    }

    public function dequeue() {
        if($this->isEmpty()) throw new Exception("Queue is empty");
        $head = $this->head;
        $this->head = $this->head->next;
        return $head->getData();
    }

}

class Graph {

    private $root;
    private $nodes;

    public function __construct($root, $adiacence_list)
    {

        $this->nodes = array();

        foreach ($adiacence_list as $node => $adicent_nodes) {
            if(!isset($this->nodes[$node])) {
                $new_node = new GraphNode($node, $adicent_nodes);
                $this->nodes[$node] = $new_node;
            }
        }

        $this->root = &$this->nodes[$root];

    }

    public function BFS() {

        $queue = new Queue();
        $queue->enqueue($this->root->getData());

        $visited = array();
        $out=array();

        $out[]= $this->root->getData();

        while (!$queue->isEmpty()) {

            $current = $this->nodes[$queue->dequeue()];
            foreach ($current->adiacent_nodes as $adiacent_node) {
                if(!isset($visited[$adiacent_node])) {
                    $visited[$adiacent_node] = true;
                    $queue->enqueue($this->nodes[$adiacent_node]->getData());
                    $out[] = $adiacent_node;
                }
            }
            $visited[$current->getData()] = true;

        }
        return $out;

    }

    public function DFS() {

        $stack = new Stack();
        $stack->push($this->root->getData());

        $visited = array();


        $out=array();
        $out[]= $this->root->getData();

        while(!$stack->isEmpty()) {

            $current = $this->nodes[$stack->peek()];
            $visited[$stack->peek()] = true;

            foreach ($current->adiacent_nodes as $adiacent_node) {
                if(!isset($visited[$adiacent_node])) {
                    $stack->push($adiacent_node);
                    $visited[$adiacent_node] = true;
                    $out[]= $adiacent_node;
                    break;
                }
                else {
                    $stack->pop();

                }

            }

        }

        return $out;

    }


}




$adiacence_list = array(

    'a' => array('b','c'),
    'b' => array('a','d'),
    'c' => array('e','f'),
    'd' => array('b'),
    'e' => array('c'),
    'f' => array('c')
);

$g = new Graph('a',$adiacence_list);
var_dump( $g->DFS() );