Implementierung eines expliziten Stacks in einer Tiefe erste Suche

Question

Ich habe eine besonders große Grafik, die es nahezu unmöglich macht, mit Rekursion zu traversieren, da der Speicher zu groß ist.

Unten ist meine depth-first-Funktion, mit Rekursion:

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

Ich mag würde diese Funktion neu zu schreiben, so dass es nicht-rekursiv ist. Ich nehme an, dass ich eine Art Queue machen muss und Werte unter Verwendung von array_shift() absetzen muss, aber in welchem ​​Teil der Funktion, und wie stelle ich sicher, dass die eingereihten Scheitelpunkte erhalten bleiben (um den letzten Pfad auf $this->stacks zu setzen)? jedes Blatt hat nur 1 Weg von der Wurzel ..

Hier ist eine DFS einfache Suche nach einem beliebigen binären

Answer 1

Es exponentiellem Raum nicht nehmen, die Anzahl der Pfade in einem Baum auf der Anzahl der Blätter gleich ist, Baum:

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

Was Sie alle Pfade in einem Baum finden, müssen einfach & Fork branch ist, was bedeutet, wenn Sie Zweig, jeder Zweig .. hier eine Kopie des aktuellen Pfad nimmt, ist ein 1-zeiliges rekursive Verzweigung & Gabel schrieb ich:

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