Depth First Search (DFS) is a fundamental graph traversal algorithm that explores as far as possible along each branch before backtracking. It is commonly used for traversing or searching tree or graph data structures. In this blog post, we will dive into the concept of DFS and provide a code example in Swift to illustrate its implementation.
Understanding Depth First Search
The main idea behind DFS is to start at a given node and explore as far as possible along each branch before backtracking. It follows a specific order of traversal, usually going deep into the graph before exploring sibling nodes.
The DFS algorithm can be implemented using either a recursive approach or an iterative approach with a stack data structure. In the recursive approach, the algorithm starts at a given node, marks it as visited, and then recursively visits all its unvisited neighbors. If all the neighbors have been visited, the algorithm backtracks to the previous node.
Implementing DFS in Swift
Let’s see how we can implement the DFS algorithm in Swift. We’ll use an adjacency list representation of a graph and perform a recursive DFS traversal.
class Graph {
var adjacencyList: [Int: [Int]] = [:]
func addEdge(_ source: Int, _ destination: Int) {
adjacencyList[source, default: []].append(destination)
adjacencyList[destination, default: []].append(source)
}
func dfs(_ startNode: Int) {
var visited: Set<Int> = []
dfsHelper(startNode, &visited)
}
private func dfsHelper(_ node: Int, _ visited: inout Set<Int>) {
visited.insert(node)
print("Visited node: \(node)")
guard let neighbors = adjacencyList[node] else { return }
for neighbor in neighbors {
if !visited.contains(neighbor) {
dfsHelper(neighbor, &visited)
}
}
}
}In this code, we define a Graph class that represents an undirected graph using an adjacency list. The addEdge method adds an edge between two nodes in the graph.
The dfs method is the entry point for the DFS traversal. It takes a starting node as input and initializes a visited set to keep track of visited nodes. It then calls the dfsHelper method to perform the recursive DFS traversal.
The dfsHelper method is a recursive helper function that takes a node and the visited set as parameters. It marks the current node as visited, prints the visited node, and then recursively visits all its unvisited neighbors.
Let’s see how we can use the DFS implementation:
let graph = Graph()
graph.addEdge(0, 1)
graph.addEdge(0, 2)
graph.addEdge(1, 2)
graph.addEdge(2, 0)
graph.addEdge(2, 3)
graph.addEdge(3, 3)
print("DFS traversal starting from node 2:")
graph.dfs(2)In this example, we create a Graph instance and add some edges to it. We then call the dfs method, passing the starting node as an argument. The DFS traversal will start from node 2 and explore the graph, printing the visited nodes in the order of traversal.
The output will be:
DFS traversal starting from node 2:
Visited node: 2
Visited node: 0
Visited node: 1
Visited node: 3Problems
Problem 1: Binary Tree Inorder Traversal
Leetcode: 94. Binary Tree Inorder Traversal
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
dfsHelper(root, &result)
return result
}
private func dfsHelper(_ node: TreeNode?, _ result: inout Array<Int>) {
// Base case: reach end of the tree
guard let node else { return }
dfsHelper(node.left, &result)
result.append(node.val)
dfsHelper(node.right, &result)
}
// Test Case 1
let root = TreeNode(1)
let node2 = TreeNode(2)
root.right = node2
let node3 = TreeNode(3)
node2.left = node3
print(inorderTraversal(root)) // [1, 3, 2]Problem 2: Same Tree
Leetcode: 100. Same Tree
class TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) {
self.val = val
self.left = nil
self.right = nil
}
}
func inorderTraversal(_ root: TreeNode?) -> [Int] {
var result = [Int]()
dfsHelper(root, &result)
return result
}
private func dfsHelper(_ node: TreeNode?, _ result: inout Array<Int>) {
// Base case: reach end of the tree
guard let node else { return }
dfsHelper(node.left, &result)
result.append(node.val)
dfsHelper(node.right, &result)
}
// Test Case 1
let root1 = TreeNode(1)
let node12 = TreeNode(2)
root1.right = node12
let node13 = TreeNode(3)
node12.left = node13
print(inorderTraversal(root1)) // [1, 3, 2]
// Test Case 2
let root2 = TreeNode(1)
let node22 = TreeNode(2)
let node23 = TreeNode(3)
let node24 = TreeNode(4)
let node25 = TreeNode(5)
let node26 = TreeNode(6)
let node27 = TreeNode(7)
root2.left = node22
root2.right = node23
node22.left = node24
node22.right = node25
node23.left = node26
node23.right = node27
print(inorderTraversal(root2)) //[4, 2, 5, 1, 6, 3, 7]