Learn the basic algorithms for traversing trees and graphs.
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.)
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 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.
- Print the value of the Node N.
- Mark N as visited.
- Get all the adjacent nodes to N.
- Call DFS on every adjacent Node that's not visited.
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.