When exploring the world of algorithms and data structures, one of the first and most fascinating graph traversal techniques you’ll come across is Depth-First Search (DFS). It is a simple yet powerful algorithm used to explore nodes and edges in a graph or tree. In simple terms, DFS starts at a node and explores as far as possible along each branch before backtracking. It’s a bit like walking through a maze — you keep going forward until you hit a dead end, then backtrack to find another path.
with hands-on learning.
get the skills and confidence to land your next move.
Depth-First Search is widely used in real-world applications such as pathfinding, scheduling, web crawling, solving puzzles, and even in artificial intelligence for exploring possible moves in games. The idea behind DFS is both intuitive and elegant, making it a perfect topic for beginners learning about algorithms in Dart.
In this article, we’ll explore different ways to implement Depth-First Search in Dart. You’ll see recursive and iterative versions, as well as how to use DFS for both directed and undirected graphs. Each program comes with a clear explanation so you can understand not just how it works, but why it works that way.
Program 1: Simple Recursive DFS in Dart
This is the most common and easiest way to understand DFS. We use recursion to visit each node and explore all its connected neighbors.
void dfs(Map<int, List<int>> graph, int start, Set<int> visited) {
visited.add(start);
print(start);
for (var neighbor in graph[start]!) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
void main() {
Map<int, List<int>> graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0],
3: [1],
4: [1, 5],
5: [4]
};
Set<int> visited = {};
print("Depth First Search starting from node 0:");
dfs(graph, 0, visited);
}This recursive DFS function starts from a node, marks it as visited, and then explores all its neighbors. If a neighbor hasn’t been visited, it calls the DFS function again on that node. This process continues until all reachable nodes have been visited. For beginners, this is the best way to start learning DFS because the code structure mirrors the algorithm’s conceptual flow.
Program 2: Iterative DFS Using a Stack
Recursion is easy to understand, but it can cause stack overflow if the graph is large. In this version, we’ll implement DFS iteratively using an explicit stack data structure.
void dfsIterative(Map<int, List<int>> graph, int start) {
Set<int> visited = {};
List<int> stack = [start];
while (stack.isNotEmpty) {
int node = stack.removeLast();
if (!visited.contains(node)) {
print(node);
visited.add(node);
for (var neighbor in graph[node]!.reversed) {
if (!visited.contains(neighbor)) {
stack.add(neighbor);
}
}
}
}
}
void main() {
Map<int, List<int>> graph = {
0: [1, 2],
1: [3, 4],
2: [5],
3: [],
4: [5],
5: []
};
print("Iterative Depth First Search starting from node 0:");
dfsIterative(graph, 0);
}In this approach, instead of letting recursion handle the function calls, we manage our own stack. Each time we visit a node, we push its neighbors onto the stack if they haven’t been visited yet. This continues until the stack is empty. It’s a great way to understand how DFS works under the hood and avoids the recursion limit issue.
Program 3: DFS for Directed Graphs
So far, we’ve used undirected graphs. Let’s now apply DFS to a directed graph, where each edge has a direction. This is useful in problems like detecting cycles or finding paths in one-way road networks.
void dfsDirected(Map<int, List<int>> graph, int node, Set<int> visited) {
visited.add(node);
print(node);
for (var neighbor in graph[node]!) {
if (!visited.contains(neighbor)) {
dfsDirected(graph, neighbor, visited);
}
}
}
void main() {
Map<int, List<int>> directedGraph = {
0: [1],
1: [2, 3],
2: [3],
3: [4],
4: []
};
Set<int> visited = {};
print("DFS traversal of a Directed Graph starting from node 0:");
dfsDirected(directedGraph, 0, visited);
}This version works much like the previous one, except that the graph is directional. You only follow the direction of edges when traversing. It’s a simple adjustment but a very important concept when working with directed graphs.
Program 4: DFS Using Adjacency Matrix
Sometimes graphs are represented not as adjacency lists but as adjacency matrices. In this case, we’ll perform DFS using a 2D list to represent connections between nodes.
void dfsMatrix(List<List<int>> graph, int start, List<bool> visited) {
visited[start] = true;
print(start);
for (int i = 0; i < graph.length; i++) {
if (graph[start][i] == 1 && !visited[i]) {
dfsMatrix(graph, i, visited);
}
}
}
void main() {
List<List<int>> graph = [
[0, 1, 1, 0, 0],
[1, 0, 0, 1, 0],
[1, 0, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 0, 1, 1, 0]
];
List<bool> visited = List.filled(graph.length, false);
print("DFS traversal using Adjacency Matrix starting from node 0:");
dfsMatrix(graph, 0, visited);
}Here, the graph is stored as a matrix where graph[i][j] == 1 means there is a connection from node i to node j. DFS checks each node’s row and recursively visits connected nodes. This approach is especially helpful when dealing with dense graphs where most nodes are interconnected.
Program 5: DFS with User Input
In real-world applications, data isn’t hardcoded. This version allows users to input the graph structure and starting node, making the program interactive and flexible.
import 'dart:io';
void dfs(Map<int, List<int>> graph, int start, Set<int> visited) {
visited.add(start);
print(start);
for (var neighbor in graph[start]!) {
if (!visited.contains(neighbor)) {
dfs(graph, neighbor, visited);
}
}
}
void main() {
Map<int, List<int>> graph = {};
print("Enter number of nodes: ");
int n = int.parse(stdin.readLineSync()!);
for (int i = 0; i < n; i++) {
print("Enter neighbors of node $i (space-separated): ");
List<int> neighbors =
stdin.readLineSync()!.split(' ').map(int.parse).toList();
graph[i] = neighbors;
}
print("Enter starting node: ");
int start = int.parse(stdin.readLineSync()!);
Set<int> visited = {};
print("\nDFS traversal starting from node $start:");
dfs(graph, start, visited);
}This interactive DFS program accepts the number of nodes and neighbors for each node from the user. It then performs DFS starting from the chosen node. This version is practical for learning how to handle user input and build flexible programs in Dart.
Frequently Asked Questions (FAQ)
Below are some of the most common questions beginners ask when learning about Depth-First Search in Dart.
Q1: What is Depth-First Search (DFS)?
Depth-First Search is a graph traversal algorithm that explores as far as possible along each branch before backtracking.
Q2: What are the real-life applications of DFS?
DFS is used in pathfinding, solving mazes, detecting cycles in graphs, and analyzing network connections.
Q3: What’s the difference between DFS and BFS?
DFS goes deep into one path before exploring others, while BFS explores all neighbors at the current depth before moving deeper.
Q4: Can DFS be used on both directed and undirected graphs?
Yes, DFS works on both types of graphs. You just need to adjust the graph structure accordingly.
Q5: Is recursion always better than iteration in DFS?
Recursion is simpler to implement and understand, but iteration with a stack is safer for large graphs as it prevents stack overflow errors.
Conclusion
Depth-First Search is one of the most elegant and useful algorithms every programmer should learn. It helps you understand how to systematically explore data structures like graphs and trees. In this article, we explored multiple implementations of DFS in Dart — from simple recursive and iterative approaches to adjacency matrices and user-input versions.
Each program builds on the last, giving you a complete understanding of how DFS works in different contexts. As you practice these examples, try modifying them to fit new problems — perhaps adding path tracking or detecting cycles. The more you experiment, the more confident you’ll become in mastering algorithms like DFS in Dart.
