How to perform DFS and BFS traversal on a PHP directed non-cyclic graph (2D array)

Question

From what I learned from Java collections/maps, a map can be represented by an adjacency list using hashmap or linked list. In PHP, to create an adjacency list I had to use 2D array. I am having a hard time understanding how to make use of arrays in order to perform a BFS and DFS on a graph represented by a adj list of 2D array. The graph is made up of integers, it is directed and non cyclic

The BFS traversal seems to be working on the graph I tested it but the DFS does not want to work. In DFS, I could not even get the results because I tried recursive iteration and I got an error.

How do I perform a DFS (and possible also a BFS incase the one I have is wrong) on a graph represented by a 2D array (adj list) in PHP, I searched everywhere I could think of but have not seen it done so I could learn from examples, even worse I am very new to PHP. I want to store the order of traversal of both DFS and BFS so that I can use it to solve another problem. Your help is very much appreciated

My code is below:

class Graph {
//put your code here

private $vertexTotal;        // Total number of nodes in the graph   
private $map;               // The two dim array for key and value    
private $DFS_preOrderList;  // Variables for performDFS
private $visited;
private $stack;

private $q;         // Variables for performBFS
private $BFS_List;
private $visitedb; 

public function Graph($vertxTotal)           // constructor
{
    $this->vertexTotal = $vertxTotal;
    $this->map = array(array()); 

    // In this for loop, for every vertex, we create for it a list/array. 
    // The values of the vertices wii come at a later stage in a function 'addEdge'
    for ($i = 1; $i<=$vertxTotal; $i++ )
    {
        $this->map [$i] = array();        
    }       

    $this->DFS_preOrderList = array();
    $this->visited = array();
    $this->q = array();
    $this->BFS_List = array();
    $this->visitedb = array();
    $this->stack = array();
}
  // Adds egdes to the graph
public function addEdge($source, $destination)
{
   // Here we take 'source' and use it to find equivalent key value in map, once we identify it inside the map, 
   // we add  'destination' to its list         
   $this->map [$source][] = $destination;          
}

The BFS function (inside class graph):

  public function performBFS($nodeStart)
{ 
    $this->q [] = $nodeStart;           // add starting node to queue
    $this->visitedb []= $nodeStart;     // mark starting node as visited by adding it to the set
    $this->BFS_List []= $nodeStart;     // add the visited node to the performBFS array list

    while (!empty($this->q))                                   // repeat until u have visited all nodes
    {
        $nextVertex = array_shift($this->q);                     // test if working correctly or perhaps use array unset???                 
        foreach($this->map[$nextVertex] as $key => $edge) 
        {                                                      // get the map key and go through all its values (childrens)
            if (!array_search($edge,$this->visitedb))           // if the child/node has not been visited: 
            {
                $this->q [] = $edge;                        // add it to queue so it can be visited
                $this->visitedb [] = $edge;                 // once u have visited it, add it to visited set
                $this->BFS_List [] = $edge;                 // and add it to performBFS array list
            }
        }
    }
}

public function printBFS() // displays the BFS traversal order
{ 
    echo "<br><br>";
    echo "The BFS traversal for the graph is: ";
    echo "<br>";        
        foreach($this->BFS_List as $value) {
            echo  $value . ", ";
        }
    echo "<br><br>";
}

The DFS traversal that does not want to work, error = Fatal error: Uncaught Error: Call to undefined function performDFS()

    // Performs the DFS on the map's adjacency list
public function performDFS($nodeStart) 
{ 
  $this->DFS_preOrderList [] = $nodeStart;
  $this->visited [] = $nodeStart;
  $this->stack [] = $nodeStart; // equivalent of pushing into a stack or list which are both same as arrays

  foreach($this->map[$nodeStart] as $key => $edge)
  {
      if (!array_search($edge,$this->visited))
      {
        return performDFS($edge);  // recursive call
      }      
  }
}

public function printDFS() // suppose to print/display the DFS traversal order
{ 
    echo "<br><br>";
    echo "The DFS traversal for the graph is: ";
    echo "<br>";        
        foreach($this->DFS_preOrderList as $value) {
            echo  $value . ", ";
        }
    echo "<br><br>"; 
}

Code for testing the graph:

        echo "<br><br>";    

    $graph = new Graph(9);
    $graph->addEdge(1, 2);
    $graph->addEdge(2, 3);
    $graph->addEdge(2, 4);
    $graph->addEdge(3, 5);
    $graph->addEdge(3, 6);
    $graph->addEdge(4, 7);
    $graph->addEdge(7, 8);
    $graph->addEdge(7, 9);

//    $graph->printGraphAdjList();

    $graph->performBFS(1);
    $graph->printBFS();

    $graph->performDFS(1);
    $graph->printDFS();

For the given data in test code above, I did it in java and got these results which I would also like to get in php:

DFS traversal : [1, 2, 3, 5, 6, 4, 7, 8, 9] BFS traversal : [1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 1

After almost 2 full days, and I mean 2 full days, I finally figured out what was wrong and decided to answer my question incase someone else might need it someday. Since I am very very new to PHP, my code may not be well optimized though.

I am just going to show the modifications from the above code and explain a few things which i think are key to understanding DFS traversal in PHP. The BFS will be modified if after several tests with different data I find that it is not working correctly.

DFS traversal function:

     // Performs the DFS on the map's adjacency list
public function performDFS($nodeStart) 
{ 
// Here we push starting node to the stack    
//$this->stack [] = $nodeStart; // IS NOT equivalent to pushing into a stack
  array_unshift($this->stack, $nodeStart); //this is equivalent to push into stack
  // array_shift() => pop from stack

  while (!empty($this->stack))
   {
      $nextVertex = array_shift($this->stack); // pop next node to be visited
      if(!array_search($nextVertex,$this->visited)) // see if node is not visited
        {
            $this->visited [] = $nextVertex; // Mark the node as visited
            $this->DFS_preOrderList [] = $nextVertex;

            //Here we push all elements of a certain node to the stack
            $list = $this->map[$nextVertex];                
            foreach($list as $value) {
              array_unshift($this->stack, $value);
            }                
        }
    }    
} 

As explained in code comments, to use an array as a stack (which is needed for DFS), one has to use the in built functions of array_shif($array,item) which is same as pop from stack and array_unshift($array,item) for push into array, where item is the thing you want to pop or push.

Concerning the error in the recursive function, this is what I found: When making a function to be recursive AND that function is inside a class which you intend to create objects for, instead of using return $functionName(some value) , use return $this->$functionName(some value) , that removed the error I mentioned in the question.

I also want to mention that the results of DFS will not always be the same depending on the algorithm and probably language used, but if it is correctly traversed, all results will be correct. I noticed the DFS I got from Java and from PHP were different BUT were all part of the possible solution/traversal orders I did manually on paper