Depth-First Search

To do something useful with graphs, you need to be traverse them systematically to find connections and paths. Depth-First Search (DFS) traverses through a graph's nodes by going as far as possible in one direction before backtracking. (See Backtracking for a non-tree example.)

In this Algorithm visualizer you can view the graph as a logical chart or as a list of lists. Pick a start vertex, and then click Run DFS to see the algorithm in action!

DFS Algorithm

DFS goes through a graph as far as possible in one direction before backtracking to other nodes. DFS is similar to the pre-order tree traversal, but you need to make sure you don't get stuck in a loop. To do this, you'll need to keep track of which Nodes have been visited. Before clicking below, see if you can figure out a recursive algorithm to print out a graph in DFS order.

Q: If you're using actual Nodes for your graph, you can mark them as visited, but how will you track visits if you're just using lists of numbers?
A: You can use an array of booleans that keeps track of which Nodes have been visited.