Depth First Search Fast AF

Depth First Search (DFS) is a common algorithm used to traverse and search through graphs or tree structures. It involves starting at a root node and exploring as far as possible down each branch before backtracking and exploring the next branch.

In this tutorial, we will implement DFS in Swift and walk through the steps of how it works.

First, let’s create a simple graph structure to use for our example. We will use an adjacency list representation, which is a common way to represent graphs in code. An adjacency list is simply a list of all the nodes in the graph, and each node has a list of its neighboring nodes.

struct Node {
  let value: String
  var neighbors: [Node]
}

let a = Node(value: "A", neighbors: [])
let b = Node(value: "B", neighbors: [])
let c = Node(value: "C", neighbors: [])
let d = Node(value: "D", neighbors: [])
let e = Node(value: "E", neighbors: [])

a.neighbors = [b, c]
b.neighbors = [a, d, e]
c.neighbors = [a, e]
d.neighbors = [b]
e.neighbors = [b, c]

Now that we have our graph set up, let’s define a function to perform the DFS. We will pass in the root node and a target value we are searching for.

func depthFirstSearch(root: Node, target: String) -> Bool {
  // Create a set to keep track of visited nodes
  var visited = Set<Node>()
  
  // Create a stack to store nodes that need to be explored
  var stack = [Node]()
  
  // Add the root node to the stack
  stack.append(root)
  
  // While there are still nodes in the stack
  while !stack.isEmpty {
    // Pop the top node off the stack
    let current = stack.popLast()!
    
    // If the current node is the target, return true
    if current.value == target {
      return true
    }
    
    // Mark the current node as visited
    visited.insert(current)
    
    // Loop through all the neighbors of the current node
    for neighbor in current.neighbors {
      // If the neighbor has not been visited, add it to the stack
      if !visited.contains(neighbor) {
        stack.append(neighbor)
      }
    }
  }
  
  // If the target was not found, return false
  return false
}

Let’s walk through how this code works. We start by creating a set to keep track of the nodes we have visited and a stack to store the nodes we need to explore. We add the root node to the stack and enter a while loop.

Inside the loop, we pop the top node off the stack and check if it is the target. If it is, we return true. If not, we mark the node as visited and loop through all of its neighbors. If a neighbor has not been visited, we add it to the stack.

If the loop ends and the target was not found, we return false.

Now let’s test our DFS function.

let result = depthFirstSearch(root: a, target: "E")
print(result) // Output: true

In this example, we start at the root node “A” and explore all its neighbors before moving on to the next branch. We eventually find the target node “E” and return true.

It’s important to note that DFS is not always the most efficient way to search through a graph or tree. It can take a long time to explore deep branches before backtracking and exploring other branches. In cases where the target is more likely to be found closer to the root, a Breadth First Search (BFS) may be a better choice.

For more information on DFS and other graph traversal algorithms, check out the following resources:

• Wikipedia — Depth First Search
• GeeksforGeeks — Depth First Search
• TutorialsPoint — Depth First Search

I hope this tutorial has helped you understand how to implement depth first search in Swift and how it works. Happy coding!