Implementation of an explicit stack in a depth first search

algorithm, depth-first-search, graph, php, recursion

Solution

It doesn't take exponential space, number of paths in a tree is equal to number of leaves, every leaf has only 1 path from the root ..

Here is a DFS simple search for an arbitrary binary tree:

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

What you need to find all paths in a tree is simply Branch & Fork, meaning whenever you branch, each branch takes a copy of the current path .. here is a 1-line recursive branch & fork I wrote:

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

Problem

I have a particularly large graph, making it nearly impossible to traverse using recursion because of the excessive amount of memory it uses. Below is my depth-first function, using recursion: ``` 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; } ``` I would like to rewrite this function so it is non-recursive. I assume I will need to make a queue of some sort, and pop off values using `array_shift()` but in which part of the function, and how do I make sure the queued vertices are preserved (to put the final pathway on `$this->stacks`)?

Original source