41. Depth-First Search Challenges

Written by Vincent Ngo

Challenge 1: BFS or DFS

For each of the following two examples, which traversal (depth-first or breadth-first) is better for discovering if a path exists between the two nodes? Explain why.

• Path from A to F.
• Path from A to G.

Challenge 2: Recursive DFS

In this chapter, you went over an iterative implementation of depth-first search. Now write a recursive implementation.

Challenge 3: Detect a cycle

Add a method to Graph to detect if a directed graph has a cycle.

Solutions

Solution to Challenge 1

• Path from A to F: Use depth-first because the path you are looking for is deeper in the graph.
• Path from A to G: Use breadth-first because the path you are looking for is near the root.

Solution to Challenge 2

In the depth-first search chapter, you learned how to implement the algorithm iteratively. Let’s take a look at how you would implement it recursively.

extension Graph where Element: Hashable {

  func depthFirstSearch(from start: Vertex<Element>)
                        -> [Vertex<Element>] {
    var visited: [Vertex<Element>] = [] // 1
    var pushed: Set<Vertex<Element>> = [] // 2
    depthFirstSearch(from: start, // 3
                     visited: &visited,
                     pushed: &pushed)
    return visited
  }
}

1. visited keeps track of the vertices visited in order.
2. pushed keeps tracks of which vertices have been visited.
3. Perform depth-first search recursively by calling a helper function.

The helper function looks like this:

func depthFirstSearch(from source: Vertex<Element>,
                      visited: inout [Vertex<Element>],
                      pushed: inout Set<Vertex<Element>>) {
  pushed.insert(source) // 1
  visited.append(source)

  let neighbors = edges(from: source)
  for edge in neighbors { // 2
    if !pushed.contains(edge.destination) {
      depthFirstSearch(from: edge.destination, // 3
                       visited: &visited,
                       pushed: &pushed)
    }
  }
}

1. Insert the source vertex into the queue, and mark it as visited.
2. For every neighboring edge.
3. As long as the adjacent vertex has not been visited yet, continue to dive deeper down the branch recursively.

Overall the time complexity for depth-first search is O(V + E).

Solution to Challenge 3

A graph has a cycle when a path of edges and vertices leads back to the same source.

extension Graph where Element: Hashable {

  func hasCycle(from source: Vertex<Element>) -> Bool  {
    var pushed: Set<Vertex<Element>> = [] // 1
    return hasCycle(from: source, pushed: &pushed) // 2
  }
}

1. pushed is used to keep track of all the vertices visited.
2. Recursively check to see if there is a cycle in the graph by calling a helper function.

The helper function looks like this:

func hasCycle(from source: Vertex<Element>,
              pushed: inout Set<Vertex<Element>>) -> Bool {
  pushed.insert(source) // 1

  let neighbors = edges(from: source) // 2
  for edge in neighbors {
    if !pushed.contains(edge.destination) &&
       hasCycle(from: edge.destination, pushed: &pushed) { // 3
      return true
    } else if pushed.contains(edge.destination) { // 4
      return true
    }
  }
  pushed.remove(source) // 5
  return false // 6
}

1. To initiate the algorithm, first insert the source vertex.
2. For every neighboring edge.
3. If the adjacent vertex has not been visited before, recursively dive deeper down a branch to check for a cycle.
4. If the adjacent vertex has been visited before, you have found a cycle.
5. Remove the source vertex so you can continue to find other paths with a potential cycle.
6. No cycle has been found.

You are essentially performing a depth-first graph traversal by recursively diving down one path till you find a cycle and back-tracking by popping off the stack to find another path. The time-complexity is O(V + E).