PHP 7 Data Structures and Algorithms

Breadth first search

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 ...