3

根据我从 Java 集合/映射中学到的知识，映射可以使用 hashmap 或链表由邻接表表示。在 PHP 中，要创建邻接列表，我必须使用 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遍历，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>"; 
}

测试图表的代码：

        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]

4

1 回答 1

2

经过将近 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

关于递归函数中的错误，这是我发现的：当使函数成为递归函数并且该函数位于您打算为其创建对象的类中，而不是 using return $functionName(some value)、 usereturn $this->$functionName(some value)时，这消除了我在问题。

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

于 2020-04-28T00:32:57.970 回答