PHP 数组中的迭代加深深度优先搜索

Question

是否可以在 PHP 中使用级别数组实现 IDDFS 算法？

假设有以下树：

    A
   / \
  B   C
 / \   \  
D   E   F

调用getNodes(A)结果为 Array(B, C)，同样也getNodes(B)为 Array(D, E)。我已经编写了 getNodes 函数，将其与 BFS 算法一起使用，不幸的是它太慢了。

代码格式的表单注释：

function bfs($start,$target){
    $dist = 0; 

    if(empty($queue)){
        $queue = array(); 
    }; 

    if(empty($checked)){
        $checked = array();
    }; 

    array_push($queue, $start); 
    while(!empty($queue)):
        $dist = $dist + 1;
        $newqueue = array();

        foreach($queue as $node){
            if(!in_array($node,$checked)){
                array_push($checked,$node);
                $nodes=getNodes($node);
                if(checkNode($nodes,$target)){
                    return $dist;
                }else{
                    $newqueue=$nodes;
                }
            } 
            $queue = $newqueue; 
        } 
    endwhile;

    return false;
}

Answer 1

从递归的角度来看，执行此操作的函数可能如下所示：

<?php

function getNode($needle, $target) {

    $res = null;
    foreach($target as $key=>$val) {

        if($key === $needle) {
            $res = $target[$key];
            break;
        }
        elseif(is_array($target[$key]))
            $res = getNode($needle, $target[$key]);
    }
    return $res;
}

测试用：

$arr = array(
    'a' => array(
        'b' => array(
            'water'
        ),
        'c' => array(
            'earth'
        )
    )
);

var_dump(getNode('a', $arr));