Example of breadth first algorithm on graph using queue

breadthFirstOnGraph.php

<?php

// Example of breadth first Algorithm

class Vertex
{
    /**
     * @var bool
     */
    private bool $isExplored = false;

    /**
     * @param int $value
     * @param array $connections
     */
    public function __construct(private int $value, private array $connections)
    {
    }

    /**
     * @return array
     */
    public function getConnections(): array
    {
        return $this->connections;
    }

    /**
     * @return int
     */
    public function getValue(): int
    {
        return $this->value;
    }

    /**
     * @return bool
     */
    public function isExplored(): bool
    {
        return $this->isExplored;
    }

    /**
     * @return $this
     */
    public function markExplored(): static
    {
        $this->isExplored = true;

        return $this;
    }
}

/**
 * @param Vertex $current
 * @param array $Vertexes
 * @param array $queue
 * @return array
 */
function BreadthFirstGraph(Vertex $current, array $Vertexes, array $queue = []): array
{
    if(! isset($queue[$current->getValue()])) {
        $queue[$current->getValue()] = $current;
    }

    $connections = $current->getConnections();

    $nearestVertexes = array_filter($Vertexes, function(Vertex $Vertex) use ($connections, $queue) {
        return in_array($Vertex->getValue(), $connections) && ! isset($queue[$Vertex->getValue()]);
    });

    if(! empty($nearestVertexes)) {
        foreach($nearestVertexes as $vertex) {
            $queue[$vertex->getValue()] = $vertex;
        }
    }

    $queue[$current->getValue()] = $current->markExplored();

    foreach($queue as $vertexInQueue) {
        if(! $vertexInQueue->isExplored()) {
            $queue = BreadthFirstGraph($vertexInQueue, $Vertexes, $queue);
        }
    }

    return $queue;
}

$nodeOne   = new Vertex(1, [4, 2]);
$nodeTwo   = new Vertex(2, [1, 3, 5, 8, 7]);
$nodeThree = new Vertex(3, [4, 2, 10, 9]);
$nodeFour  = new Vertex(4, [1, 3]);
$nodeFive  = new Vertex(5, [2, 8, 7, 6]);
$nodeSix   = new Vertex(6, [5]);
$nodeSeven = new Vertex(7, [5, 2, 8]);
$nodeEight = new Vertex(8, [2, 7, 5]);
$nodeNine  = new Vertex(9, [3]);
$nodeTen   = new Vertex(10, [3]);

BreadthFirstGraph($nodeEight, [$nodeOne, $nodeTwo, $nodeThree, $nodeFour, $nodeFive, $nodeSix, $nodeSeven, $nodeEight, $nodeNine, $nodeTen]);