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

```									```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)
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()

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

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