In order to implement the traversal algorithms, you will need to make some adjustments to your Vertex and Graph classes.

You need to be able to get a hold of an unvisited neighbour for a specific vertex which means you need some way of establishing if a vertex has been visited or not.  A simple way to keep track of visited vertices is to add a ‘Visited’ property to your Vertex class.

Public Class Vertex
    Public Value As String
    Public Visited As Boolean
    Public Sub New(ByVal Value As String)
        Me.Value = Value
    End Sub
End Class

Make sure you understand

Here, the Visited property has been implemented simply as a public Boolean variable inside the Vertex class.  The Visited property has not been implemented as a property procedure because it is only intended for use by the Graph itself.

You will also need a method inside the graph class called something like ‘getAdjacentUnvisitedVertex’, or ‘getNextUnvisitedNeighbour’.

    Private Function getAdjacentUnvisitedVertex(ByVal v As Integer) As Integer
        Dim j As Integer
        For j = 0 To iNumberOfVertices - 1
            If adjacencyMatrix(v, j) >= 1 And vertices(j).Visited = False Then
                Return j
            End If
        Next
        Return -1
    End Function

Make sure you understand

Examine the definition of this method.  You can see that it has been implemented as a function with one input parameter; the integer id of a vertex whose next unvisited neighbour it is designed to retrieve.  You can also see that this function returns an Integer; the id of one of the unvisited neighbours.

Within the body of this method, each neighbour of the input vertex, v, is examined by scanning down the appropriate column of the 2 dimensional array (the adjacency matrix).  The Visited property of each neighbour is examined is tested to see if it is False.  The id of the first unvisited neighbour encountered is returned.  If no unvisited neighbours are found, a value of -1 is returned.

Depth first traversal

This requires a stack data structure to enable the algorithm to backtrack when a path has been exhausted. You can use VB.NET’s built in Stack class which has Push Pop and Peek operations.

 

    Public Sub DepthFirstTraversal()
        Dim Stack As New Stack
        vertices(0).Visited = True
        ShowVertex(0)
        Stack.Push(0)
        Dim v As Integer
        While (Stack.Count > 0)
            v = getAdjacentUnvisitedVertex(Stack.Peek)
            If v = -1 Then
                Stack.Pop()
            Else
                vertices(v).Visited = True
                ShowVertex(v)
                Stack.Push(v)
            End If
        End While
        Dim j As Integer
        For j = 0 To iNumberOfVertices - 1
            vertices(j).Visited = False
        Next
    End Sub

Make sure you understand

The DepthFirstTraversal method begins by instantiating a Stack object.  It sets the Visited property of the first vertex in the vertices array to True, then the first vertex is pushed onto the stack.

Then the main While loop begins.

The main loop runs until the stack is empty; the built in stack class has a Count property which is greater than zero if there are still some items on the stack.

The getAdjacentUnvisitedVertex method is called within the loop.  It is passed the id of the vertex on top of the stack.  The stack’s Peek method is used to get the id of this vertex because it takes a copy of the item on top of the stack without actually removing it.  If the value -1 is returned by getAdjacentUnvisitedVertex, it means that there are no unvisited neighbours of the current vertex, so the current vertex can be popped off the stack.  Otherwise a neighbour is indeed returned, it is marked as visited, and is pushed onto the top of the stack.  The While loop then continues.

The For loop at the end of this method marks all of the vertices as unvisited in readiness for the next time the graph is traversed.

Testing your code

You can use the following graph to test your traversal implementations.

Here is the code to set up its vertices and edges.

        g.AddVertex("A")
        g.AddVertex("B")
        g.AddVertex("C")
        g.AddVertex("D")
        g.AddVertex("E")
        g.AddVertex("F")
        g.AddVertex("G")
        g.AddVertex("H")
        g.AddVertex("I")
        g.AddEdge(0, 1, 3)
        g.AddEdge(0, 2, 2)
        g.AddEdge(0, 3, 4)
        g.AddEdge(1, 0, 3)
        g.AddEdge(1, 2, 1)
        g.AddEdge(1, 4, 2)
        g.AddEdge(2, 0, 2)
        g.AddEdge(2, 1, 1)
        g.AddEdge(2, 3, 4)
        g.AddEdge(2, 5, 2)
        g.AddEdge(2, 6, 3)
        g.AddEdge(3, 0, 4)
        g.AddEdge(3, 2, 4)
        g.AddEdge(3, 6, 2)
        g.AddEdge(4, 1, 2)
        g.AddEdge(5, 2, 2)
        g.AddEdge(5, 8, 5)
        g.AddEdge(6, 2, 3)
        g.AddEdge(6, 3, 2)
        g.AddEdge(6, 7, 3)
        g.AddEdge(7, 6, 3)
        g.AddEdge(8, 5, 5)

Breadth first traversal

Breadth first traversal will make use of the same getAdjacentUnvisitedVertex method and the fact that the Vertex class has a visited property.  The key difference is the use of a Queue.  VB.NET has a built in Queue class than can be employed.