We are now going to implement a BFS for a graph. Considering the following undirected graph, first, we need to represent the graph in a matrix or list. For the sake of simplicity, we will use the adjacency matrix for the graph representation:

The preceding adjacency graph has six vertices, and the vertices are labeled from 1 to 6 (no 0). Since our vertices are numbered, we can use those as array indexes for faster access. We will can construct the graph like this:

$graph = []; 
$visited = []; 
$vertexCount = 6; 

for($i = 1;$i<=$vertexCount;$i++) { 
    $graph[$i] = array_fill(1, $vertexCount, 0); 
    $visited[$i] = 0; 
} 

Here, we have two arrays, one for representing the actual graph and the other one for keeping track of the visited nodes. We want to make sure that we do not visit a node multiple times as it might end up in an infinite loop. Since our graph has six vertices, we kept $vertexCount as 6. We then initialize the graph array as a two-dimensional array with an initial value of 0. We will start the index from 1 for the array. We also set each vertex as not visited by assigning each vertex to 0 in the $visited array. Now, we will add the edges in our graph representation. Since the graph is undirected, we need to set two properties for each edge. In other words, we need to set bidirectional edge values for edges between the vertex labeled 1 and 2 since both share an edge between them. Here is the code for the full representation of the earlier graph:

$graph[1][2] = $graph[2][1] = 1; 
$graph[1][5] = $graph[5][1] = 1; 
$graph[5][2] = $graph[2][5] = 1; 
$graph[5][4] = $graph[4][5] = 1; 
$graph[4][3] = $graph[3][4] = 1; 
$graph[3][2] = $graph[2][3] = 1; 
$graph[6][4] = $graph[4][6] = 1; 

So, we have represented the graph using an adjacency matrix. Now, let's define the BFS algorithm for the matrix:

function BFS(array &$graph, int $start, array $visited): SplQueue { 
    $queue = new SplQueue;
    $path = new SplQueue;

    $queue->enqueue($start);
    $visited[$start] = 1;

    while (!$queue->isEmpty()) { 
      $node = $queue->dequeue();
      $path->enqueue($node);
      foreach ($graph[$node] as $key => $vertex) { 
          if (!$visited[$key] && $vertex == 1) { 
          $visited[$key] = 1;
          $queue->enqueue($key);
          }
      }
    }

    return $path;
}

Our implemented BFS function takes three arguments: the actual graph, the starting vertex, and the empty visited array. We could have avoided the third argument and written the initialization inside the BFS function. At the end of the day, we can choose either of the ways to accomplish this. Inside our function implementation, we have two queues: one to keep the nodes that we need to visit and another one for the order of the visited nodes, or the path of the search. At the end of the function, we return the path queue.

Inside the function, we first add the starting node to the queue. Then, we start from that node to visit its adjacent nodes. If the node is not visited and has a connection to the current node, we add it to our queue for visiting. We also mark the current node as visited and add it to our path. Now, we will call our BFS function with our constructed graph matrix and a visiting node. Here is the program to execute the BFS functionality:

$path = BFS($graph, 1, $visited); 

while (!$path->isEmpty()) { 
    echo $path->dequeue()."	"; 
} 

As we can see from the preceding code snippet, we start the search from node 1. The output will look like this:

    1       2       5       3       4       6

If we had 5 as the starting node by changing the second argument of the BFS function call from 1 to 5, then the output would have been the following:

    5       1       2       4       3       6