Depth-First Search


Premium Content - Free Preview

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.)

Depth-First-Search

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.

DFS Algorithm

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.


End of Free Content Preview. Please Sign in or Sign up to buy premium content.

Contact Us