Depth First Traversal

Depth first traversal, also known as depth first search or DFS, is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.

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

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

Private Shared _top As Integer = -1
Private Shared _vertexCount As Integer = 0

Private Shared Sub Push(stack As Integer(), item As Integer)
	_top += 1
	stack(_top) = item
End Sub

Private Shared Function Pop(stack As Integer()) As Integer
	Dim retVal = stack(_top)
	_top -= 1
	Return retVal
End Function

Private Shared Function Peek(stack As Integer()) As Integer
	Return stack(_top)
End Function

Private Shared Function IsStackEmpty() As Boolean
	Return _top = -1
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
	For i As Integer = 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 DepthFirstSearch(arrVertices As Vertex(), adjacencyMatrix As Integer(,), stack As Integer())
	arrVertices(0).Visited = True
	DisplayVertex(arrVertices, 0)
	Push(stack, 0)

	While Not IsStackEmpty()
		Dim unvisitedVertex As Integer = GetAdjacentUnvisitedVertex(arrVertices, adjacencyMatrix, Peek(stack))

		If unvisitedVertex = -1 Then
			Pop(stack)
		Else
			arrVertices(unvisitedVertex).Visited = True
			DisplayVertex(arrVertices, unvisitedVertex)
			Push(stack, unvisitedVertex)
		End If
	End While

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

Example

									Dim max As Integer = 5
Dim stack 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("Depth First Search: ")
DepthFirstSearch(arrVertices, adjacencyMatrix, stack)
								

Output

									Depth First Search: S A D B C