Depth-First Search in PHP

Posted on by

The Depth-First Search algorithm can be used to find a path between two points. I recently had to use it to draw a map in PHP. This is my implementation of a graph structure with DFS in PHP5. Download the source.

2 thoughts on “Depth-First Search in PHP”

  1. i have problem with your algorithm, i have list like
    $this->graph_arr = array();
    $n = new Node(“15″, array(“36″, “211″));
    array_push($this->graph_arr, $n);
    $n = new Node(“32″, array(“15″, “199″));
    array_push($this->graph_arr, $n);
    //$n = new Node(“36″, array(“49″, “50″,”32″,”486″,”542″,”328″,”561″,”1141″,”653″,”654″,”512″,”80″,”800″));
    $n = new Node(“36″, array(“32″,”49″, “80″,”328″,”486″,”512″,”542″,”561″,”653″,”654″,”800″,”1141″));
    array_push($this->graph_arr, $n);
    //$n = new Node(“49″, array(“1141″, “542″,”36″,”1153″));
    $n = new Node(“49″, array(“36″, “542″,”1141″,”1153″));
    array_push($this->graph_arr, $n);
    $n = new Node(“328″, array(“49″, “653″));
    array_push($this->graph_arr, $n);
    //$n = new Node(“542″, array(“1141″, “50″));
    $n = new Node(“542″, array(“50″, “1141″));
    array_push($this->graph_arr, $n);
    //$n = new Node(“653″, array(“654″, “50″));
    $n = new Node(“653″, array(“50″, “654″));
    array_push($this->graph_arr, $n);
    $n = new Node(“800″, array(“801″, “802″));
    array_push($this->graph_arr, $n);

    i have clalled in main php like
    $graph = new Graph();
    echo “”;
    $graph->printGraph($graph->getGraph());
    echo “———————————- ”;
    //$graph->getAdjacentNodes();
    //$graph->dfs(@$_GET['s'], @$_GET['f']);
    //$graph->dfs_recursive(@$_GET['s'], @$_GET['f']);
    //$graph->dfs_recursive(36,802);
    //$graph->dfs_recursive(36,50);
    //$graph->dfs_recursive(’36′,’50′);
    //$graph->dfs_recursive(’36′,’653′);
    $graph->dfs_recursive(32,542);
    $graph->printDfsSolution();

    but in line $finish_node_name = $this->getNode($finish_node_name);

    i bekomme empty $finish_node_name
    why!!

Leave a Reply