Breadth-First-Search in PHP

Question

My table structure:

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

What I am doing is first retrieving all the records, and then looking for a tree for all possible children using the first depth search (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;
}

This function works fine and returns all the children of the node.

What I'm looking for is a way to get all the children of a node using BFS ?

Answer 1

I myself wrote a BFS search function. I used PHP SplQueue

global variable for storing an array of children.

Private $queue = [];

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

The call to traverseTree ()

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

Here $ id is the root node for which you want to get all the children.

gist, .

Answer 2

BFS , BFS node s node t. DFS, - , , , , . , BFS , node S.

BFS O (E + V) ( ) DFS O (E + V),

, BFS, DFS, .