Как выполнить обход DFS и BFS на нециклическом c направленном графе PHP (2D-массив)

Question

Из того, что я узнал из Java коллекций / карт, карта может быть представлена ​​списком смежности, используя hashmap или связанный список. В PHP, чтобы создать список смежности, мне пришлось использовать 2D-массив. Мне трудно понять, как использовать массивы для выполнения BFS и DFS на графике, представленном прилегающим списком двумерного массива. Граф состоит из целых чисел, он направлен и не цикличен c

Кажется, что обход BFS работает на графе, который я тестировал, но DFS не хочет работать. В DFS я даже не смог получить результаты, потому что я попробовал рекурсивную итерацию и получил ошибку.

Как мне выполнить DFS (и, возможно, также BFS, если у меня есть неправильный) на графике, представленном двумерным массивом (прилежащий список) в PHP, я искал везде, о чем мог подумать но я не видел, чтобы это было сделано, чтобы я мог учиться на примерах, еще хуже, я очень плохо знаком с 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, который не хочу работать, ошибка = неустранимая ошибка: необработанная ошибка: вызов неопределенной функции executeDFS ()

    // 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, мой код может быть не очень хорошо оптимизирован.

Я просто собираюсь показать модификации из приведенного выше кода и объяснить несколько вещей, которые, я думаю, являются ключевыми для понимания обхода DFS в PHP. 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) это то же самое, что pop из стека и array_unshift($array,item) для pu sh в массив, где item - это то, что вы хотите вытолкнуть или pu sh.

Что касается ошибки в рекурсивной функции, вот что я обнаружил: когда вы делаете функцию рекурсивной И эта функция находится внутри класса, для которого вы намереваетесь создать объекты, вместо использования return $functionName(some value), используйте return $this->$functionName(some value), это устранило ошибку, о которой я упоминал в вопросе.

Я также хочу упомянуть, что результаты DFS не всегда будут одинаковыми в зависимости от алгоритма и, вероятно, используемого языка, но если его правильно обойти, все результаты будут правильными. Я заметил, что DFS, которые я получил от Java и от PHP, отличались, НО все они были частью возможных ордеров на решение / обход, которые я делал вручную на бумаге