Breadth first traversal, also known as breadth first search or BFS, is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key') and explores the neighbor nodes first, before moving to the next level neighbors.

```									```Public Structure Vertex
Public Label As Char
Public Visited As Boolean
End Structure

Private Shared _rear As Integer = -1
Private Shared _front As Integer = 0
Private Shared _queueItemCount As Integer = 0
Private Shared _vertexCount As Integer = 0

Private Shared Sub Insert(queue As Integer(), data As Integer)
_rear += 1
queue(_rear) = data
_queueItemCount += 1
End Sub

Private Shared Function RemoveData(queue As Integer()) As Integer
_queueItemCount -= 1
Dim retVal = queue(_front)
_front += 1
Return retVal
End Function

Private Shared Function IsQueueEmpty() As Boolean
Return _queueItemCount = 0
End Function

Public Shared Sub AddVertex(arrVertices As Vertex(), label As Char)
Dim vertex As New Vertex()
vertex.Label = label
vertex.Visited = False
arrVertices(_vertexCount) = vertex
_vertexCount += 1
End Sub

Public Shared Sub AddEdge(adjacencyMatrix As Integer(,), start As Integer, [end] As Integer)
End Sub

Private Shared Sub DisplayVertex(arrVertices As Vertex(), vertexIndex As Integer)
Console.Write(arrVertices(vertexIndex).Label & " ")
End Sub

Private Shared Function GetAdjacentUnvisitedVertex(arrVertices As Vertex(), adjacencyMatrix As Integer(,), vertexIndex As Integer) As Integer
Dim i As Integer

For i = 0 To _vertexCount - 1
If adjacencyMatrix(vertexIndex, i) = 1 AndAlso arrVertices(i).Visited = False Then
Return i
End If
Next

Return -1
End Function

Public Shared Sub BreadthFirstSearch(arrVertices As Vertex(), adjacencyMatrix As Integer(,), queue As Integer())
Dim i As Integer
arrVertices(0).Visited = True
DisplayVertex(arrVertices, 0)
Insert(queue, 0)
Dim unvisitedVertex As Integer

While Not IsQueueEmpty()
Dim tempVertex As Integer = RemoveData(queue)

While unvisitedVertex <> -1
arrVertices(unvisitedVertex).Visited = True
DisplayVertex(arrVertices, unvisitedVertex)
Insert(queue, unvisitedVertex)
End While
End While

For i = 0 To _vertexCount - 1
arrVertices(i).Visited = False
Next
End Sub```
```

### Example

```									```Dim max As Integer = 5
Dim queue As Integer() = New Integer(max - 1) {}
Dim arrVertices As Vertex() = New Vertex(max - 1) {}
Dim adjacencyMatrix As Integer(,) = New Integer(max - 1, max - 1) {}

For i As Integer = 0 To max - 1
For j As Integer = 0 To max - 1
Next
Next

```									`Breadth First Search: S A B C D`