깊이 우선 검색에서 명시 적 스택 구현

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

그것은 나무에 경로의 수는 잎의 수와 같다 지수 공간을 고려하지 않습니다, 모든 잎은 뿌리에서 단 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; 
} 

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