Implementazione di uno stack esplicito in una prima ricerca di profondità

Question

Ho un grafico particolarmente grande, che rende quasi impossibile attraversare l'utilizzo della ricorsione a causa dell'eccessiva quantità di memoria che utilizza.

Qui di seguito è la mia funzione in profondità, utilizzando la ricorsione:

public function find_all_paths($start, $path) 
{ 
    $path[] = $start; 
    if (count($path)==25) /* Only want a path of maximum 25 vertices*/ { 
     $this->stacks[] = $path; 
     return $path; 

    } 
    $paths = array(); 

    for($i = 0; $i < count($this->graph[$start])-1; $i++) { 
     if (!in_array($this->graph[$start][$i], $path)) { 
    $paths[] = $this->find_all_paths($this->graph[$start][$i], $path); 

     } 
    } 


    return $paths; 
} 

vorrei riscrivere questa funzione in modo che non è ricorsiva. Presumo che dovrò fare una coda di qualche tipo e inserire i valori usando array_shift() ma in quale parte della funzione, e come posso assicurarmi che i vertici in coda siano preservati (per inserire il percorso finale su $this->stacks)?

Answer 1

Non ci vuole spazio esponenziale, il numero di percorsi in un albero è pari al numero di foglie, ogni foglia ha solo 1 percorso dalla radice ..

Ecco un DFS semplice ricerca di un binario arbitrario albero:

// DFS: Parent-Left-Right 
public function dfs_search ($head, $key) 
{ 
    var $stack = array($head); 
    var $solution = array(); 

    while (count($stack) > 0) 
    { 
     $node = array_pop($stack); 

     if ($node.val == $key) 
     { 
      $solution[] = $node; 
     } 

     if ($node.left != null) 
     { 
      array_push($stack, $node.left); 
     } 

     if ($node.right != null) 
     { 
      array_push($stack, $node.right); 
     } 
    } 

    return $solution; 
} 

Quello che è necessario trovare tutti i percorsi in un albero è semplicemente branch & forcella, il che significa ogni volta che si ramo, ogni ramo prende una copia del percorso attuale .. ecco un ramo ricorsivo 1-line & fork ho scritto:

// Branch & Fork 
public function dfs_branchFork ($node, $path) 
{ 
    return array($path) 
     +($node.right!=null?dfs_branchFork($node.right, $path+array($node)):null) 
     +($node.left!=null?dfs_branchFork($node.left, $path+array($node)):null); 
}