VB .NET Program to Implement Depth-First Search
By Coder Scratchpad on in Visual Basic
When working with graphs, one of the most fundamental tasks is traversing all nodes efficiently. Depth-First Search (DFS) is a classic algorithm used to explore a graph by going as deep as possible along each branch before backtracking. It is widely used in pathfinding, solving puzzles, detecting cycles, and analyzing networks. Learning DFS not only introduces you to graph algorithms but also strengthens your understanding of recursion and iterative thinking.
DFS matters because it helps programmers navigate complex data structures in an organized way. Unlike simple linear searches in arrays, DFS works with networks of nodes, such as social connections, maps, or even game levels. For beginners, mastering DFS opens the door to advanced topics like graph theory, algorithms for shortest paths, and problem-solving strategies in programming competitions.
Program 1: Recursive Depth-First Search on a Graph
This program demonstrates a basic recursive DFS on a predefined graph represented as an adjacency list. It visits all nodes reachable from a starting node.
Module Module1
Sub DFS(node As Integer, adj()() As Integer, visited() As Boolean)
visited(node) = True
Console.Write(node & " ")
For Each neighbor In adj(node)
If Not visited(neighbor) Then
DFS(neighbor, adj, visited)
End If
Next
End Sub
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3, 4}
adj(2) = New Integer() {0}
adj(3) = New Integer() {1}
adj(4) = New Integer() {1}
Dim visited(n - 1) As Boolean
Console.WriteLine("DFS starting from node 0:")
DFS(0, adj, visited)
Console.ReadLine()
End Sub
End Module
Module Module1
Sub DFS(node As Integer, adj()() As Integer, visited() As Boolean)
visited(node) = True
Console.Write(node & " ")
For Each neighbor In adj(node)
If Not visited(neighbor) Then
DFS(neighbor, adj, visited)
End If
Next
End Sub
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3, 4}
adj(2) = New Integer() {0}
adj(3) = New Integer() {1}
adj(4) = New Integer() {1}
Dim visited(n - 1) As Boolean
Console.WriteLine("DFS starting from node 0:")
DFS(0, adj, visited)
Console.ReadLine()
End Sub
End Module
This program starts at node 0 and recursively explores each connected node. The visited array ensures nodes are not revisited, preventing infinite loops. Beginners can see recursion in action, understanding how DFS dives deep before backtracking.
Program 2: Iterative Depth-First Search Using a Stack
This version shows an iterative approach using a stack instead of recursion, which can be useful when dealing with very large graphs to avoid stack overflow.
Module Module1
Sub DFSIterative(start As Integer, adj()() As Integer)
Dim n As Integer = adj.Length
Dim visited(n - 1) As Boolean
Dim stack As New Stack(Of Integer)
stack.Push(start)
While stack.Count > 0
Dim node As Integer = stack.Pop()
If Not visited(node) Then
visited(node) = True
Console.Write(node & " ")
For Each neighbor In adj(node)
If Not visited(neighbor) Then
stack.Push(neighbor)
End If
Next
End If
End While
End Sub
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3, 4}
adj(2) = New Integer() {0}
adj(3) = New Integer() {1}
adj(4) = New Integer() {1}
Console.WriteLine("Iterative DFS starting from node 0:")
DFSIterative(0, adj)
Console.ReadLine()
End Sub
End Module
Module Module1
Sub DFSIterative(start As Integer, adj()() As Integer)
Dim n As Integer = adj.Length
Dim visited(n - 1) As Boolean
Dim stack As New Stack(Of Integer)
stack.Push(start)
While stack.Count > 0
Dim node As Integer = stack.Pop()
If Not visited(node) Then
visited(node) = True
Console.Write(node & " ")
For Each neighbor In adj(node)
If Not visited(neighbor) Then
stack.Push(neighbor)
End If
Next
End If
End While
End Sub
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3, 4}
adj(2) = New Integer() {0}
adj(3) = New Integer() {1}
adj(4) = New Integer() {1}
Console.WriteLine("Iterative DFS starting from node 0:")
DFSIterative(0, adj)
Console.ReadLine()
End Sub
End Module
Instead of recursion, this program uses a stack to manage nodes. It demonstrates how DFS can be implemented iteratively. Beginners can understand that recursion is just a stack in disguise, making the algorithm flexible for large datasets.
Program 3: DFS for Detecting Cycles in a Graph
This program uses DFS to check if a graph contains a cycle, which is a common graph-related problem.
Module Module1
Function DFSDetectCycle(node As Integer, parent As Integer, adj()() As Integer, visited() As Boolean) As Boolean
visited(node) = True
For Each neighbor In adj(node)
If Not visited(neighbor) Then
If DFSDetectCycle(neighbor, node, adj, visited) Then
Return True
End If
ElseIf neighbor <> parent Then
Return True
End If
Next
Return False
End Function
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3}
adj(2) = New Integer() {0, 4}
adj(3) = New Integer() {1}
adj(4) = New Integer() {2}
Dim visited(n - 1) As Boolean
Dim hasCycle As Boolean = DFSDetectCycle(0, -1, adj, visited)
If hasCycle Then
Console.WriteLine("Graph contains a cycle.")
Else
Console.WriteLine("Graph does not contain a cycle.")
End If
Console.ReadLine()
End Sub
End Module
Module Module1
Function DFSDetectCycle(node As Integer, parent As Integer, adj()() As Integer, visited() As Boolean) As Boolean
visited(node) = True
For Each neighbor In adj(node)
If Not visited(neighbor) Then
If DFSDetectCycle(neighbor, node, adj, visited) Then
Return True
End If
ElseIf neighbor <> parent Then
Return True
End If
Next
Return False
End Function
Sub Main()
Dim n As Integer = 5
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1, 2}
adj(1) = New Integer() {0, 3}
adj(2) = New Integer() {0, 4}
adj(3) = New Integer() {1}
adj(4) = New Integer() {2}
Dim visited(n - 1) As Boolean
Dim hasCycle As Boolean = DFSDetectCycle(0, -1, adj, visited)
If hasCycle Then
Console.WriteLine("Graph contains a cycle.")
Else
Console.WriteLine("Graph does not contain a cycle.")
End If
Console.ReadLine()
End Sub
End Module
By tracking the parent node, the program detects back edges, which indicate a cycle. This shows DFS can solve graph analysis problems, not just traversal. Beginners can see practical applications of DFS.
Program 4: DFS for Counting Connected Components
This program counts connected components in a graph, showing how DFS explores disconnected subgraphs.
Module Module1
Sub DFS(node As Integer, adj()() As Integer, visited() As Boolean)
visited(node) = True
For Each neighbor In adj(node)
If Not visited(neighbor) Then
DFS(neighbor, adj, visited)
End If
Next
End Sub
Sub Main()
Dim n As Integer = 6
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1}
adj(1) = New Integer() {0}
adj(2) = New Integer() {3}
adj(3) = New Integer() {2}
adj(4) = New Integer() {}
adj(5) = New Integer() {}
Dim visited(n - 1) As Boolean
Dim count As Integer = 0
For i As Integer = 0 To n - 1
If Not visited(i) Then
DFS(i, adj, visited)
count += 1
End If
Next
Console.WriteLine("Number of connected components: " & count)
Console.ReadLine()
End Sub
End Module
Module Module1
Sub DFS(node As Integer, adj()() As Integer, visited() As Boolean)
visited(node) = True
For Each neighbor In adj(node)
If Not visited(neighbor) Then
DFS(neighbor, adj, visited)
End If
Next
End Sub
Sub Main()
Dim n As Integer = 6
Dim adj(n - 1)() As Integer
adj(0) = New Integer() {1}
adj(1) = New Integer() {0}
adj(2) = New Integer() {3}
adj(3) = New Integer() {2}
adj(4) = New Integer() {}
adj(5) = New Integer() {}
Dim visited(n - 1) As Boolean
Dim count As Integer = 0
For i As Integer = 0 To n - 1
If Not visited(i) Then
DFS(i, adj, visited)
count += 1
End If
Next
Console.WriteLine("Number of connected components: " & count)
Console.ReadLine()
End Sub
End Module
DFS is called on each unvisited node, counting disconnected groups. Beginners can see how DFS explores every node in a connected component, making it ideal for network analysis.
Program 5: DFS on a Grid (Maze Traversal)
This program applies DFS to a 2D grid, which is common in pathfinding and games.
Module Module1
Dim rows As Integer = 4
Dim cols As Integer = 4
Dim grid(,) As Integer = {
{0, 1, 0, 0},
{0, 1, 0, 1},
{0, 0, 0, 1},
{1, 1, 0, 0}
}
Dim visited(3, 3) As Boolean
Sub DFS(x As Integer, y As Integer)
If x < 0 Or x >= rows Or y < 0 Or y >= cols Then Return
If grid(x, y) = 1 Or visited(x, y) Then Return
visited(x, y) = True
Console.Write("(" & x & "," & y & ") ")
DFS(x + 1, y)
DFS(x - 1, y)
DFS(x, y + 1)
DFS(x, y - 1)
End Sub
Sub Main()
Console.WriteLine("DFS traversal of grid starting at (0,0):")
DFS(0, 0)
Console.ReadLine()
End Sub
End Module
Module Module1
Dim rows As Integer = 4
Dim cols As Integer = 4
Dim grid(,) As Integer = {
{0, 1, 0, 0},
{0, 1, 0, 1},
{0, 0, 0, 1},
{1, 1, 0, 0}
}
Dim visited(3, 3) As Boolean
Sub DFS(x As Integer, y As Integer)
If x < 0 Or x >= rows Or y < 0 Or y >= cols Then Return
If grid(x, y) = 1 Or visited(x, y) Then Return
visited(x, y) = True
Console.Write("(" & x & "," & y & ") ")
DFS(x + 1, y)
DFS(x - 1, y)
DFS(x, y + 1)
DFS(x, y - 1)
End Sub
Sub Main()
Console.WriteLine("DFS traversal of grid starting at (0,0):")
DFS(0, 0)
Console.ReadLine()
End Sub
End Module
DFS explores all reachable cells in the grid. This demonstrates its usefulness for mazes, maps, and 2D pathfinding, making it relatable for game development and real-world applications.
Frequently Asked Questions (FAQ)
Here are some common questions beginners ask about Depth-First Search:
Q1: What is Depth-First Search used for?
DFS is used for graph traversal, cycle detection, pathfinding, and exploring connected components.
Q2: Can DFS be implemented iteratively?
Yes, using a stack instead of recursion to manage nodes.
Q3: How does DFS differ from Breadth-First Search?
DFS goes deep into one branch before backtracking, while BFS explores all neighbors level by level.
Q4: Can DFS handle disconnected graphs?
Yes, calling DFS on unvisited nodes allows it to cover all components.
Q5: Is DFS suitable for 2D grids or mazes?
Absolutely, it is commonly used in maze traversal, game maps, and similar problems.
Conclusion
Depth-First Search is a powerful and versatile algorithm for exploring graphs and grids. By learning recursive, iterative, cycle detection, connected components, and grid traversal versions, beginners can grasp how DFS applies to real-world problems. Practicing DFS helps programmers think algorithmically and solve complex problems efficiently, making it an essential skill in computer science and VB .NET programming.