Implementing Breadth-first search in PHP

BFS search order of nodes in a graph

In my previous articles I have covered some aspects of searching for a path between nodes in a graph.

In my case the graph represents a data center with network devices and network cables connecting them.

The operation staff needs to know the route between their devices and all the cables along this route for maintenance and inventory purposes.

I already showed how the route can be represented using a Sankey graph or how we can extract the cables data using PHP and Laravel from the system database.

In this article I will reveal my implementation of Breadth-first search that I use to explore the path between the given network devices.

According to it’s Wikipedia page “Breadth-first search (BFS) is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth prior to moving on to the nodes at the next depth level. Extra memory, usually a queue, is needed to keep track of the child nodes that were encountered but not yet explored”.

My implementation slightly changes this in a way that the tree root is the start device and the node that satisfies a given property (the search subject) is my end device.

Apart from this I tried to implement my version of BFS as close to the recommended pseudo code as possible.

I created a Graph class in PHP that not only represents the data structure but also contains a breadthFirstSearch() method.

The class can be instantiated with the following constructor:

public function __construct(protected array $graph = []) {
    $this->explored = $this->markAllNodesAsUnExplored();
}

It takes a graph and sets all nodes to unexplored and stores this state in a private property.

Once we have constructed our Graph object we can call it’s breadthFirstSearch() method.

We need to provide the root node (start or origin network device) and the destination device as well.

public function breadthFirstSearch(int $origin, int $destination) {

    $this->origin = $origin;
    $this->destination = $destination;

    $q = new SplQueue();

    $q->enqueue($origin);
    $this->setAsExplored($origin);

    $this->setParent(vertex: $origin, parent: $origin);

    while (!$q->isEmpty() && $q->bottom() != $destination) {
        $currentVertex = $q->dequeue();
        foreach ($this->adjacentEdges($currentVertex) as $vertex) {
            if (!$this->isExplored($vertex)) {
                $q->enqueue($vertex);
                $this->setAsExplored($vertex);
                $this->setParent(vertex: $vertex, parent: $currentVertex);
            }
        }
    }

    $this->setRoute($this->extractRoute());

    return $this;

}

The algorithm is pretty straightforward:

• we set the origin node as explored, put it in a queue and we set it’s parent node (in our case it’s parent is itself),
• we loop through all adjacent nodes (or vertexes to adhere the nomenclature of graph theory),
• for each adjacent node if it is not yet explored then we put it in our SplQueue (set to FIFO mode), set the node to explored and also registering it’s parent,
• we continue the above process until our queue in not empty

Once we have been through the search process we extract the route between the origin and destination nodes (if any was explored) using the extractRoute method:

private function extractRoute(array $parents = []): array {

    $p = $parents ?: $this->parents;
    $route = [];

    if (isset($p[$this->destination])) {
        $route[] = $this->destination;
        $vertex = $p[$this->destination];
        while ($vertex !== $this->origin) {
            $route[] = $vertex;
            $vertex = $p[$vertex];
        }
        $route[] = $this->origin;
    }

    return array_reverse($route);

}

This basically walks backwards from our destination using it’s parent node until we reach the origin node and store this information in our class route property.

The reason I selected BFS because breadth-first search always guarantees to find a solution node if one exists.

Considering that the datacenter does not have an infinite number of nodes (network devices) or edges between them (network cables) it’s worst time performance is also acceptable to me.

The time complexity of the BFS algorithm can be expressed as

, since every vertex and every edge will be explored in the worst case.