如何在PHP有向非循环图（2D数组）上执行DFS和BFS遍历

Question

[从我从Java集合/地图中学到的知识，可以使用哈希表或链表通过邻接表表示地图。在PHP中，要创建邻接表，我必须使用2D数组。我很难理解如何利用数组，以便在由2D数组的adj列表表示的图形上执行BFS和DFS。该图由整数组成，它是有向的和非循环的

BFS遍历似乎在我测试过的图形上起作用，但DFS不想起作用。在DFS中，我什至无法获得结果，因为我尝试了递归迭代并且出现了错误。

我如何在PHP中由2D数组（adj列表）表示的图上执行DFS（如果我有一个错误的话，还可能要有BFS，我搜索了我能想到但到没见过的所有地方因此我可以从示例中学习，更糟糕的是，我对PHP还是很陌生。我想存储DFS和BFS的遍历顺序，以便可以使用它来解决另一个问题。非常感谢您的帮助

我的代码在下面：

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;          
}

BFS函数（内部类图）：

  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>";
}

不想运行的DFS遍历，错误=致命错误：未捕获错误：调用未定义的函数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>"; 
}

用于测试图形的代码：

        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();

对于上面测试代码中的给定数据，我在Java中进行了处理，并获得了这些结果，这些结果我也想在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

经过将近2天的时间，我的意思是2天的时间，我终于弄清楚出了什么问题，并决定回答我的问题，以防某天某人可能需要它。由于我是PHP的新手，因此请发表评论并提出改进或替代建议，我的代码可能没有得到很好的优化，如果您认为它有助于解决问题，请他人投票，以便其他人可以轻松地找到它。

我将展示上述代码的修改，并解释一些我认为对理解PHP中的DFS遍历至关重要的事情。如果在使用不同数据进行多次测试后发现BFS无法正常工作，则将修改BFS。

DFS遍历功能：

     // 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);
            }                
        }
    }    
} 

如代码注释中所述，要将数组用作堆栈（DFS需要此数组），必须使用内置函数array_shif($array,item)，该函数与从堆栈中弹出，而array_unshift($array,item)则用于推入数组，其中item是您要弹出或推送的内容。

关于递归函数中的错误，这是我发现的：当使函数具有递归性并且该函数位于要为其创建对象的类中时，可以使用return $functionName(some value)代替使用return $this->$functionName(some value)，而该错误消除了我在问题中提到的错误。

我还想提到，DFS的结果并不总是相同的，这取决于算法和所使用的语言，但是如果正确遍历DFS，则所有结果都是正确的。我注意到我从Java和PHP获得的DFS是不同的，但它们都是我在纸上手动完成的可能解决方案/遍历命令的一部分