Module Module1
    ' Breadth first search

    Class NodeClass
        ' This class defines the items associated with each node of the graph
        ' The graph, itself, will be stored as a dictionary with a key and this structure as data
        Public theNeighbours As List(Of String)
        Public theColour As String

        Public Sub New(ByVal inColour As String, ByVal inNeighbours As List(Of String))
            ' Constructor
            theColour = inColour
            theNeighbours = inNeighbours
        End Sub
    End Class
    ' Loads the global dictionary with data
    Sub loadGraphData(ByRef inGraph As Dictionary(Of String, NodeClass))

        Dim newNeighbours As List(Of String)
        Dim newNode As NodeClass

        newNeighbours = New List(Of String) From {"B", "D", "E"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("A", newNode)
        newNeighbours = New List(Of String) From {"A", "D", "C"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("B", newNode)
        newNeighbours = New List(Of String) From {"B", "G"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("C", newNode)
        newNeighbours = New List(Of String) From {"A", "B", "E", "F"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("D", newNode)
        newNeighbours = New List(Of String) From {"A", "D"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("E", newNode)
        newNeighbours = New List(Of String) From {"D"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("F", newNode)
        newNeighbours = New List(Of String) From {"C"}
        newNode = New NodeClass("white", newNeighbours)
        inGraph.Add("G", newNode)
    End Sub
    Sub displayGraph(ByVal inGraph As Dictionary(Of String, NodeClass))

        Dim outline As String
        Dim nodeName As String
        Dim theInfo As NodeClass

        For Each entry As KeyValuePair(Of String, NodeClass) In inGraph
            nodeName = entry.Key
            theInfo = entry.Value

            outline = String.Format("Node: {0}  Colour: {1}  Neighbours: {2}", nodeName, theInfo.theColour, String.Join(",", theInfo.theNeighbours))
            Console.WriteLine(outline)
        Next

    End Sub
    Function bfs(ByVal inNode As String, ByRef inGraph As Dictionary(Of String, NodeClass)) As List(Of String)

        Dim theQueue As New Queue(Of String)
        Dim visitedNodes As New List(Of String)
        Dim currentNode As String
        Dim theEntry As NodeClass

        theQueue.Enqueue(inNode)       ' A node to be examined

        ' Unitl all the nodes have been looked at
        While (theQueue.Count > 0)
            ' Print the contents of the current queue
            Console.WriteLine(String.Format("Queue is now: {0}", String.Join(",", theQueue)))
            Console.WriteLine("")

            currentNode = theQueue.Dequeue()
            Console.WriteLine(String.Format("Visiting {0} - setting it to black", currentNode))

            ' In order to change the colour from white to black, we have to point to the
            ' item field in the dictionary for the required node.  Then, point to the
            ' colour field.  This can be updated directly because we're using the 
            ' pass parameters by Reference, which means we're dealing directly with
            ' the addresses in memory, not copies of the memory content
            inGraph.Item(currentNode).theColour = "black"

            ' Insert this node into the visited list
            visitedNodes.Add(currentNode)

            ' Now, we have to explore each of this node's neighbours
            For Each node In inGraph.Item(currentNode).theNeighbours
                Console.WriteLine(String.Format("    checking neighbour {0} - colour is {1}", node, inGraph.Item(currentNode).theColour))

                If (inGraph.Item(node).theColour = "white") Then
                    Console.WriteLine(String.Format("    appending neighbour {0} to queue - setting it to grey", node))
                    theQueue.Enqueue(node)
                    inGraph.Item(node).theColour = "grey"
                End If
            Next
        End While
        Return (visitedNodes)
    End Function
    Sub Main()
        Dim eat As String
        Dim theGraph As New Dictionary(Of String, NodeClass)
        Dim visitedList As List(Of String)


        loadGraphData(theGraph)
        Console.WriteLine("Original Graph Definition")
        displayGraph(theGraph)

        visitedList = bfs("A", theGraph)
        Console.WriteLine("Nodes visited in this order: {0}", String.Join(",", visitedList))

        Console.WriteLine("Any key to continue")
        eat = Console.ReadLine()

    End Sub

End Module