Module Module1
    ' Depth first search - graph traversal

    ' Loads the global dictionary with data
    ' The graph structure should be treated as immutable, once loaded
    Sub loadGraphData(ByRef inGraph As Dictionary(Of String, List(Of String)))

        Dim theNeighbours As List(Of String)

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

        Dim outline As String
        Dim node As String
        Dim neighbours As List(Of String)

        For Each entry As KeyValuePair(Of String, List(Of String)) In inGraph
            node = entry.Key
            neighbours = entry.Value

            outline = String.Format("Node: {0}  Neighbours: {1}", node, String.Join(",", neighbours))
            Console.WriteLine(outline)
        Next

    End Sub
    Function dfs(ByVal inGraph As Dictionary(Of String, List(Of String)), ByVal inCurrentNode As String, ByRef inVisited As List(Of String)) As List(Of String)

        Dim neighbours As List(Of String)

        Console.WriteLine("Visit {0} and add to visited list", inCurrentNode)

        ' Add this node to the visited list
        inVisited.Add(inCurrentNode)
        Console.WriteLine(String.Format("    List of visited nodes: {0}", String.Join(",", inVisited)))

        neighbours = inGraph.Item(inCurrentNode)      ' Get the neighbours for this node

        For Each node In neighbours
            Console.WriteLine(String.Format("    Checking neighbour {0}", node))
            If Not inVisited.Contains(node) Then
                Console.WriteLine("        Push {0} onto the stack", inCurrentNode)
                dfs(inGraph, node, inVisited)
                Console.WriteLine("        Pop {0} off the stack", inCurrentNode)
            End If
        Next

        Console.WriteLine(String.Format("    All neighbours of {0} have been visited", inCurrentNode))
        Return (inVisited)

    End Function


    Sub Main()
        Dim eat As String
        Dim theGraph As New Dictionary(Of String, List(Of String))
        Dim visitedList As New List(Of String)
        Dim traversedOrder As New List(Of String)

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

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

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

    End Sub

End Module