Understanding depth first search code

[Duckinite]

Hi,

I’m trying to get to grips with this Depth First Search algorithm I found here. Unfortunately as there are no comments and since I am still new to vba and programming in general, I can't follow what's going on.

At the moment, I'm only somewhat familiar with If statements, some variables and simple For and Do while loops.

If it's not too much to ask, could someone outline what I need to learn before I can understand it or better yet add comments to the code so that a beginner like myself can understand?

Thanks

 

[wideboydixon]

Hi and welcome to the forum. As an interesting exercise, I simplified the code somewhat and added liberal comments. The implementation below is a recursive one based on the Wikipedia article:

Option Explicit

' This keeps track of the nodes we've visited
Public visited As String
Public Sub Main()

Dim node As Long
Dim g0, g1, g2, g3, g4, g5, g6, g7, g8
Dim graph

g0 = Array(3, 6) ' 0 is connected to 3, 6
g1 = Array(3, 4, 5, 6) ' 1 is connected to 3, 4, 5, 6
g2 = Array(8) ' 2 is connected to 8
g3 = Array(0, 1, 5) ' 3 is connected to 0, 1, 5
g4 = Array(1, 6) ' 4 is connected to 1, 6
g5 = Array(1, 3) ' 5 is connected to 1, 3
g6 = Array(0, 1, 4) ' 6 is connected to 0, 1, 4
g7 = Array() ' 7 is isolated
g8 = Array(2) ' 8 is connnected to 2

' This is the graph of all nodes
graph = Array(g0, g1, g2, g3, g4, g5, g6, g7, g8)

' We haven't visited any nodes yet
visited = "|"

' Look at each node in the graph
For node = LBound(graph) To UBound(graph)
    ' Check we haven't already visited this node
    If InStr(1, visited, "|" & node & "|") = 0 Then
        ' Not visited yet so visit this node and all connected nodes
        DFS graph, node
        
        ' That's the end of this group - print a delimiter
        Debug.Print "----"
    End If
Next node

End Sub
Private Sub DFS(ByVal graph As Variant, ByVal node As Long)

' This will go through all connected nodes for this node
Dim connectedNode

' Visit this node - print out the node number add it to the list of visited nodes
Debug.Print node
visited = visited & node & "|"

' Work through all nodes that are connected to this one
For Each connectedNode In graph(node)
    ' Have we already visited this node?
    If InStr(1, visited, "|" & connectedNode & "|") = 0 Then
        ' Not visited yet - let's do so recursively
        DFS graph, CLng(connectedNode)
    End If
Next connectedNode

End Sub

WBD