跳转至

22 Depth-First Search

In the previous chapter, you looked at breadth-first search (BFS), in which you had to explore every neighbor of a vertex before going to the next level. In this chapter, you’ll look at depth-first search (DFS), another algorithm for traversing or searching a graph.

There are a lot of applications for DFS:

  • Topological sorting.
  • Detecting a cycle.
  • Pathfinding, such as in maze puzzles.
  • Finding connected components in a sparse graph.

To perform a DFS, you start with a given source vertex and attempt to explore a branch as far as possible until you reach the end. At this point, you backtrackand explore the next available branch until you find what you’re looking for or until you’ve visited all the vertices.

How Depth-First Search Works

The following example will take you through a depth-first search. The graph below is the same as the one in the previous chapter so you can see the difference between BFS and DFS.

DCHGFEBA

BFS used a queue to visit neighboring vertices first. However, DFS will use a stack to keep track of the levels you move through. The stack’s last-in-first-out approach helps with backtracking. Every push on the stack means that you move one level deeper. You can pop to return to a previous level if you reach a dead end.

As in the previous chapter, you choose A as a starting vertex and add it to the stack:

AStackHDBEAFGC

As long as the stack isn’t empty, you visit the top vertex on the stack and push the first neighboring vertex that has yet to be visited. In this case, you visit Aand push B:

ABStackHDBEAFGC

Remember that the order in which the edges were added influences the result of a search. In this case, the first edge added to A was to B, so B is pushed first.

You visit B and push E because A is already visited:

ABEStackHDBEAFGC

Every time you push onto the stack, you advance farther down a branch. Instead of visiting every adjacent vertex, you continue down a path until you reach the end. After that you backtrack.

Next, visit E and push F.

ABEFStackHDBEAFGC

Again, the only reason you chose F instead of H is that F happened to be added first when the graph was created for this particular example. You can’t see that from the diagram, but when you get to the code later on, you’ll be able to observe the edge addition order.

Now visit F and push G:

ABEFGStackHDBEAFGC

Then visit G and push C:

ABEFGCStackHDBEAFGC

The next vertex to visit is C. It has neighbors [A, F, G], but all of these have already been visited. You’ve reached a dead end, so it’s time to backtrack by popping C off the stack:

CABEFGStackHDBEAFGC

This brings you back to G. It has neighbors [F, C], but both of these have been visited. Another dead end, so pop G:

GCABEFStackHDBEAFGC

F also has no unvisited neighbors remaining, so pop F:

CGFABEStackHDBEAFGC

Now you’re back at E. Its neighbor H is still unvisited, so you push H on the stack:

CGFABEHStackHDBEAFGC

Visiting H results in another dead end, so pop H:

CGFHABEStackHDBEAFGC

E doesn’t have any available neighbors either, so pop it:

CGFHEABStackHDBEAFGC

The same is true for B, so pop B:

CGFHEBAStackHDBEAFGC

This brings you all the way back to A, whose neighbor D still needs to be visited, so you push D on the stack:

CGFHEBADStackHDBEAFGC

Visiting D results in another dead end, so pop D:

CGFHEBDAStackHDBEAFGC

You’re back at A, but this time, there are no available neighbors to push, so you pop A. The stack is now empty and DFS is complete!

CGFHEBDAStackHDBEAFGC

When exploring the vertices, you can construct a tree-like structure, showing the branches you’ve visited. You can see how deep DFS went compared to BFS:

Breadth-First SearchAHBDCEFGHABEDFGCDepth-First Search

Implementation

Open up the starter project for this chapter. The lib folder contains an implementation of a graph as well as a stack, both of which you’ll use to implement DFS.

Creating an Extension

Create a new file in lib called depth_first_search.dart. Add the following:

import 'stack.dart';
import 'graph.dart';

extension DepthFirstSearch<E> on Graph<E> {
  List<Vertex<E>> depthFirstSearch(Vertex<E> source) {
    final stack = Stack<Vertex<E>>();
    final pushed = <Vertex<E>>{};
    final visited = <Vertex<E>>[];

    stack.push(source);
    pushed.add(source);
    visited.add(source);

    // more to come

    return visited;
  }
}

Here, you’ve defined an extension method depthFirstSearch, which takes in a starting vertex and returns a list of vertices in the order they were visited. It uses three data structures:

  1. stack is used to store your path through the graph.
  2. pushed is a set that remembers which vertices have been pushed before so that you don’t visit the same vertex twice. Using Set ensures fast O(1) lookup.
  3. visited is a list that stores the order in which the vertices were visited.

To initialize the algorithm, you add the source vertex to all three.

Traversing Vertices

Next, complete the method by replacing the // more to come comment with the following:

// 1
outerLoop:
while (stack.isNotEmpty) {
  final vertex = stack.peek;
  // 2
  final neighbors = edges(vertex);
  // 3
  for (final edge in neighbors) {
    if (!pushed.contains(edge.destination)) {
      stack.push(edge.destination);
      pushed.add(edge.destination);
      visited.add(edge.destination);
      // 4
      continue outerLoop;
    }
  }
  // 5
  stack.pop();
}

Here’s what’s going on:

  1. You continue to check the top of the stack for a vertex until the stack is empty. You’ve labeled this loop outerLoop so that you have a way to continue to the next vertex, even from within a nested for loop.
  2. You find all the neighboring edges for the current vertex.
  3. Here, you loop through every edge connected to the current vertex and check if the neighboring vertex has been seen. If not, you push it onto the stack and add it to the visited list. It may seem a bit premature to mark this vertex as visited since you haven’t peeked at it yet. However, vertices are visited in the order in which they’re added to the stack, so it results in the correct order.
  4. Now that you’ve found a neighbor to visit, you continue to outerLoop and peek at the newly pushed neighbor.
  5. If the current vertex didn’t have any unvisited neighbors, you know you’ve reached a dead end and can pop it off the stack.

Once the stack is empty, the DFS algorithm is complete! All you have to do is return the visited vertices in the order you visited them.

Testing it Out

To try out your code, open bin/starter.dart and replace the contents of the file with the following code:

import 'package:starter/graph.dart';
import 'package:starter/depth_first_search.dart';

void main() {
  final graph = AdjacencyList<String>();

  final a = graph.createVertex('A');
  final b = graph.createVertex('B');
  final c = graph.createVertex('C');
  final d = graph.createVertex('D');
  final e = graph.createVertex('E');
  final f = graph.createVertex('F');
  final g = graph.createVertex('G');
  final h = graph.createVertex('H');

  graph.addEdge(a, b, weight: 1);
  graph.addEdge(a, c, weight: 1);
  graph.addEdge(a, d, weight: 1);
  graph.addEdge(b, e, weight: 1);
  graph.addEdge(c, g, weight: 1);
  graph.addEdge(e, f, weight: 1);
  graph.addEdge(e, h, weight: 1);
  graph.addEdge(f, g, weight: 1);
  graph.addEdge(f, c, weight: 1);
}

This creates a graph with the edges added in an order that results in the DFS path that you saw in the diagrams above.

Perform the depth-first search by adding the following two lines at the bottom of main:

final vertices = graph.depthFirstSearch(a);
vertices.forEach(print);

Run that and observe the order in which DFS visited the indices:

A
B
E
F
G
C
H
D

Performance

DFS will visit every single vertex at least once. This process has a time complexity of O(V).

When traversing a graph in DFS, you have to check all neighboring vertices to find one available to visit. The time complexity of this is O(E) because you have to visit every edge in the graph in the worst case.

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

The space complexity of depth-first search is O(V) since you have to store all the vertices in three separate data structures: stack, pushed and visited.

Cycles

A depth-first search is also useful for finding whether a graph contains cycles. A graph is said to have a cycle when a path of edges and vertices leads back to the same source.

For example, in the directed graph below, if you start at A, you can go to B, then to C, and then back to A again. Since it’s possible to arrive back at the starting vertex, this is a cyclic graph:

ACDB

If you removed the C-to-A edge, this graph would become acyclic. That is, there would be no cycles. It would be impossible to start at any vertex and arrive back at the same vertex.

Note

In this directed graph, there’s also a cycle from A to C since the edges are pointing in both directions. In an undirected graph, though, two vertices wouldn’t count as a cycle. Undirected graphs need at least three vertices to make a cycle.

Checking for Cycles

Next, you’ll write an algorithm to check whether a directed graph contains a cycle.

Return to depth_first_search.dart and create another extension on Graph:

extension CyclicGraph<E> on Graph<E> {

}

Add the following recursive helper method to CyclicGraph:

bool _hasCycle(Vertex<E> source, Set<Vertex<E>> pushed) {
  // 1
  pushed.add(source);
  // 2
  final neighbors = edges(source);
  for (final edge in neighbors) {
    // 3
    if (!pushed.contains(edge.destination)) {
      if (_hasCycle(edge.destination, pushed)) {
        return true;
      }
    // 4
    } else {
      return true;
    }
  }
  // 5
  pushed.remove(source);
  // 6
  return false;
}

Here’s how it works:

  1. Initialize the algorithm by adding the source vertex.
  2. Visit 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’ve found a cycle.
  5. Remove the source vertex so you can continue to find other paths with a potential cycle.
  6. If you’ve reached this far, then no cycle was found.

To complete the code, add the public hasCycle method to CyclicGraph:

bool hasCycle(Vertex<E> source) {
  Set<Vertex<E>> pushed = {};
  return _hasCycle(source, pushed);
}

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

Testing it Out

To create a graph that matches the image above, open bin/starter.dart and replace the content of main with the following:

final graph = AdjacencyList<String>();

final a = graph.createVertex('A');
final b = graph.createVertex('B');
final c = graph.createVertex('C');
final d = graph.createVertex('D');

graph.addEdge(a, b, edgeType: EdgeType.directed);
graph.addEdge(a, c, edgeType: EdgeType.directed);
graph.addEdge(c, a, edgeType: EdgeType.directed);
graph.addEdge(b, c, edgeType: EdgeType.directed);
graph.addEdge(c, d, edgeType: EdgeType.directed);

print(graph);
print(graph.hasCycle(a));

Run that and you’ll see the output below:

A --> B, C
B --> C
C --> A, D
D -->

true

If you comment out the c-to-a edge, the method will return false.

Challenges

Try out the following challenges to test your understanding of depth-first searches. You can find the answers in the back of the book or in the supplemental materials that accompany the book.

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.

ADBFCHG

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

Challenge 2: Recursive DFS

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

Key Points

  • Depth-first search (DFS) is another algorithm to traverse or search a graph.
  • DFS explores a branch as far as possible before backtracking to the next branch.
  • The stack data structure allows you to backtrack.
  • A graph is said to have a cycle when a path of edges and vertices leads back to the source vertex.