Выполнение явного стека в первом поиске глубины

Question

У меня есть особенно большой график, из-за чрезмерного объема памяти, который он использует, почти невозможно переходить с использованием рекурсии.

Ниже моя глубина первой функции, используя рекурсию:

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

Я хотел бы переписать эту функцию, так что не является рекурсивным. Я предполагаю, что мне нужно будет сделать какую-то очередь и вывести значения с помощью array_shift(), но в какой части функции, и как я уверен, что сохраненные в очереди вершины сохранены (чтобы поставить конечный путь на $this->stacks)?

Answer 1

Это не займет экспоненциальное пространство, число путей в дереве равно количеству листьев, каждый лист имеет только один путь от корня ..

Вот ДФС простой поиск произвольной двоичной дерево:

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

Что вам нужно найти все пути в дереве просто Разветвить & вилки, то есть всякий раз, когда вы ветви, каждая ветвь берет копию текущего пути .. вот 1-линия рекурсивной ветви & fork Я написал:

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