Breadth-First Search Graph Implementation in PHP

Overview

This implementation demonstrates a breadth-first search (BFS) traversal of a graph data structure in PHP. The graph is represented using a node-based architecture where each node contains a value and connections to other nodes.

Core Components

GraphNode Class

class GraphNode {
    public int|float|string $data;
    public array $edges;
}

• Each node stores a value ($data) and an array of connections ($edges)
• Type declarations ensure data integrity
• $edges contains references to other GraphNode instances

BFS Implementation

function breadthFirstSearch(GraphNode $startingNode): void

The algorithm:

1. Maintains a queue of nodes to visit
2. Uses SplObjectStorage to track visited nodes
3. Processes nodes in FIFO order using array_pop() and array_unshift()
4. Visits each node exactly once

Key Features

• Type safety through PHP type declarations
• Object-based visited tracking via SplObjectStorage
• Queue-based traversal using native PHP array functions
• Memory efficient as each node is processed only once

Complexity

• Time: O(V + E) where V is vertices and E is edges
• Space: O(V) for queue and visited storage

This implementation is particularly useful for traversing graph structures like social networks, web crawlers, or any connected data where level-by-level exploration is needed.

Complete Implementation

<?php

class GraphNode {
    public int|float|string $data;
    /** @var GraphNode[] */
    public array $edges;

    public function __construct(int|float|string $data) {
        $this->data = $data;
        $this->edges = [];
    }
}

function visit(GraphNode $node): void {
    echo $node->data . "\n";
}

function breadthFirstSearch(GraphNode $startingNode): void {
    $bfsQueue = [$startingNode];
    $visitedNodes = new \SplObjectStorage();
    $visitedNodes->attach($startingNode);

    while (!empty($bfsQueue)) {
        $node = array_pop($bfsQueue);
        visit($node);

        foreach ($node->edges as $childNode) {
            if (!$visitedNodes->contains($childNode)) {
                array_unshift($bfsQueue, $childNode);
                $visitedNodes->attach($childNode);
            }
        }
    }
}

// Example usage
$startingNode = new GraphNode(0);
$startingNode->edges = [
    new GraphNode(1),
    new GraphNode(2),
    new GraphNode(3)
];

$startingNode->edges[0]->edges = [
    new GraphNode(5),
    new GraphNode(6)
];

$startingNode->edges[1]->edges = [
    new GraphNode(7),
    new GraphNode(8)
];

$startingNode->edges[0]->edges[0]->edges = [
    new GraphNode(9)
];

breadthFirstSearch($startingNode);