Breadth-First-Search 在 PHP

Question

我的table结构是：

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) 搜索所有可能的树 children。

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

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

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

Answer 1

BFS并不是要得到所有的子节点，BFS是寻找从节点s到节点t的最短路径。 DFS 如何访问所有节点，这似乎更像是您正在尝试做的事情。还请记住，BFS 不会转到无法从节点 S 访问的节点。

BFS 成本为 O(E + V)（大多数情况） DFS 成本也是 O(E + V)

这意味着您使用 BFS 不会有任何附加值，我建议坚持使用 DFS，它对您的目的更有效。

Answer 2

我自己写了BFS搜索功能。我用了 PHP's 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里也添加了一个文件，欢迎提出建议和改进

Answer 3

您也可以使用两个标准数组来执行此操作：

class Node {
    protected int $value;
    protected ?Node $left;
    protected ?Node $right;

    public function __construct(int $value, ?Node $left = null, ?Node $right = null) {
        $this->value = $value;
        $this->left = $left;
        $this->right = $right;
    }
    
    public function breadth_first() {
        $level = [$this];
        while (count($level)) {
            $next_level = [];
            foreach ($level as $node) {
                yield $node->value;
                if ($node->left) array_push($next_level, $node->left);
                if ($node->right) array_push($next_level, $node->right);
            }
            $level = $next_level;
        }
    }
}

您可以这样称呼它：

$tree = new Node(1,
    new Node(2,
        new Node(4),
        new Node(5)
    ),
    new Node(3)
);

foreach($tree->breadth_first() as $value) {
    echo "$value\n";
}

Breadth-First-Search 在 PHP

Breadth-First-Search in PHP

php

tree

binary-tree

breadth-first-search