We traverse graphs to retrieve information, modify data, or find a path from one point to another. In this post, I'll cover some basic differences between the two approaches to graph traversal: depth-first and breadth-first.
(This post assumes basic knowledge of the graph data structure. Check out this article for an introduction to graphs.)
The main distinction comes down to whether you follow a path to its end point (go deep), or check out all possible first steps first (go wide/broad).
Cycles
Before we get into traversal methods, we should understand that graphs can be cyclical. In other words, it's possible to follow a path from one node back to itself again! This could create some looping problems.
For this reason, in our implementations of graph traversal algorithms, we should make sure to keep track of which nodes we've visited and which we haven't.
In JavaScript, one way to do that is to create a visited object, wherewe have keys to represent each node, and values set by default to false. When we visit a node, we simply change that value to true. We can also use a visited array to store the items we've checked out already.
Depth-first
If you've iterated through tree structures, you're already familiar with depth-first traversal. With DFS of non-tree graphs, just like with trees, we follow a single line of child nodes until we hit a childless node.
For DFS, we can use a stack implementation. When we traverse down a path of children, we add them to the stack as we go along. Once we reach a node with no accessible children, we follow our path backwards until we find a node that has another path extending off of it.
In the image above, we've chosen node A as our starting point. One of A's children is B, so we follow that path. One of B's children is D, so we follow that path. We continue to follow a path of children until we get to C. C has a child (D), but that child has already been visited. So we retrace our steps until we find another viable path.
In this case, D had another child that hadn't been visited yet-- E. Eventually we get back to A, which has two other children besides B. C has already been visited, so we visit G, finally completing the original call to traverse through the children of A.
Here's one possible (non-recursive) JS implementation of DFS using a stack:
Breadth-first
In breadth-first searches, we go broad first. This means that after we examine our first node, we examine all of its immediately neighboring nodes before we go any deeper.
For BFS, we use a queue implementation.
With the above example, that means that we'd first add node A to a queue and check its value. If it's not what we're looking for, we'd pop it off the front of our queue, and add its neighbors (B, C, and G) to our list, changing their values in our visited object to true. B would be the next in line. We check it. If it's not what we want, we pop it off the front of our queue, but not before adding its neighbors (D and E) to the back of our queue.
After taking A and B from front of the queue, C is next in line. Its immediate neighbor is D...but D is already in our list. When D comes up first in line, we'll finally add F to our queue.
Here's a possible implementation of BFS in JavaScript using a queue model.
DFS vs BFS
In general, BFS is best for short searches. You can see that in the above examples, a breadth-first took six steps, while a depth-first search took thirteen.
DFS is good, then, if you're interested in checking out all possible paths from one point to another. The famous N Queens problem is a great example of DFS.
Basically, use DFS if you want to exhaust all possible options, and use BFS if you want to find something as quickly as possible!
Top comments (0)