PHP 中的广度优先搜索

Question

我的表结构是：

id    name           parent   lft  rgt
1     abc              0       2    3
2     def              1       4    5
3     geh              1       6    7
4     ijk              2       8    9
5     lmn              2       10   11

我正在做的是首先获取所有记录，然后使用深度优先搜索（DFS）为所有可能的孩子搜索树。

public function fetchRecursive($src_arr, $currentId, $parentFound = false)
{
    $cats = array();
    foreach ($src_arr as $row) {
        if ((!$parentFound && $row['id'] == $currentId) || $row['parent'] == $currentId) {
            $rowData = array();
            foreach ($row as $k => $v)
                $rowData[$k] = $v;
            $cats[] = $rowData;
            if ($row['parent'] == $currentId) {
                $cats = array_merge($cats, $this->fetchRecursive($src_arr, $row['id'], true));
            }
        }
    }
    return $cats;
}

此函数工作正常并返回节点的所有子节点。

我正在寻找的是一种使用 BFS获取节点的所有子节点的方法？

Answer 1

我自己写了BFS搜索功能。我使用了PHP 的 SplQueue

存储子数组的全局变量。

Private $queue = [];

BFS 函数

public function traverseTree($rootNode, $dummyQueue) 
{
    if($rootNode->lft != 0) {
        $dummyQueue->enqueue($rootNode->lft);
    }
    if($rootNode->rgt != 0) {
        $dummyQueue->enqueue($rootNode->rgt);
    }
    if(!($dummyQueue->isEmpty())){
        $nextId = $dummyQueue->dequeue();
        $nextNode = //get next node information using $nextId
        array_push($this->queue, $nextNode);
        $this->traverseTree($nextNode, $dummyQueue);
    }
}

调用 traverseTree() 函数

$dummyQueue = new \SplQueue();
$this->traverseTree($id, $dummyQueue);

这里 $id 是您要获取其所有子节点的根节点。

我还在gist中添加了一个文件，欢迎提出建议和改进。