Depth-First Search in PHP

2 Replies

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. farka

    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