7

私は特に大きなグラフを持っており、メモリを大量に使用するため、再帰を使用してトラバースすることはほとんど不可能です。

以下は、再帰を使用した深さ優先関数です。

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でしょうか?

4

1 に答える 1

1

指数空間を必要とせず、ツリー内のパスの数は葉の数に等しく、すべての葉にはルートからのパスが 1 つしかありません..

以下は、任意の二分木に対する DFS 単純検索です。

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

ツリー内のすべてのパスを見つけるために必要なのは、単純に Branch & Fork です。つまり、分岐するたびに、各ブランチが現在のパスのコピーを取得します。ここに、私が書いた 1 行の再帰的ブランチ & フォークを示します。

// 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);
}
于 2013-04-06T04:50:59.863 に答える