Breadth First Traversal

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.

• C#
• VB.Net
• C
• C++

									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)
	adjacencyMatrix(start, [end]) = 1
	adjacencyMatrix([end], start) = 1
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)
		unvisitedVertex = GetAdjacentUnvisitedVertex(arrVertices, adjacencyMatrix, tempVertex)

		While unvisitedVertex <> -1
			arrVertices(unvisitedVertex).Visited = True
			DisplayVertex(arrVertices, unvisitedVertex)
			Insert(queue, unvisitedVertex)
			unvisitedVertex = GetAdjacentUnvisitedVertex(arrVertices, adjacencyMatrix, tempVertex)
		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
		adjacencyMatrix(i, j) = 0
	Next
Next

AddVertex(arrVertices, "S"c)
AddVertex(arrVertices, "A"c)
AddVertex(arrVertices, "B"c)
AddVertex(arrVertices, "C"c)
AddVertex(arrVertices, "D"c)

AddEdge(adjacencyMatrix, 0, 1)
AddEdge(adjacencyMatrix, 0, 2)
AddEdge(adjacencyMatrix, 0, 3)
AddEdge(adjacencyMatrix, 1, 4)
AddEdge(adjacencyMatrix, 2, 4)
AddEdge(adjacencyMatrix, 3, 4)

Console.Write("Breadth First Search: ")
BreadthFirstSearch(arrVertices, adjacencyMatrix, queue)
								

Output

									Breadth First Search: S A B C D