дерево — Поиск в ширину в переполнении стека

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 ?

4

binary-tree breadth-first-search php tree

Решение

Другие решения

BFS не предназначена для получения всех дочерних узлов, BFS находит кратчайший путь от узла s к узлу t.
DFS, однако, посещает все узлы, что больше похоже на то, что вы пытаетесь сделать.
Также имейте в виду, что BFS не пойдет на узлы, которые недоступны с узла S.

Стоимость BFS — O (E + V) (в большинстве случаев)
Стоимость DFS также O (E + V)

это означает, что вы не будете использовать добавленную стоимость, используя вместо этого BFS, я предлагаю придерживаться DFS, которая более эффективна для ваших целей.

-2

Источник

Accepted Answer

Я сам написал функцию поиска 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 — это корневой узел, для которого вы хотите получить все дочерние элементы.

Я также добавил файл в суть, предложения и улучшения приветствуются.

1