Graph traversal is the process of visiting nodes within a graph. During a grpah traversal, we might be searching for one or more values, updating nodes, deleting nodes, or doing some type of other process for each node, such as printing the node's value to the screen. In this article, we'll introduce two fundamental algorithms: depth-first search and breadth-first search. We'll introduce them in the context of searching for values, outline when one vs the other algorithm should be used, and outline additional ways these algorithms can be used other than searching. We'll also showcase full code implementations for these algorithms in multiple programming languages.
Connected and Disconnected Graphs
Before proceeding to our overview of graph algorithms, we will need to introduce the concepts of connected and disconnected graphs. A graph is called connected if, for every pair of vertices v and u, a path exists which connects the two vertices. A graph is called disconnected if there exists any pair of vertices which do not have a path connecting them. For any graph which is disconnected, there are at least two subgraphs which are themselves connected.
Searching In Graphs
Generally speaking, the purpose of a graph traversal is to either find some value in a graph, or check if some value exists in a graph. During the traversal process, the algorithm will visit nodes in a certain order and check each node. If the node has the expected value, the algorithm will stop and indicate that it has found what it is looking for. If the node does not, the algorithm will proceed with the next node based on some explicit or implicit node ordering. In the algorithms we'll be discussing here, the search will start with some abitrary start node, which we will refer to as the root node, then move on to nodes which are connected to that node, then their connections, etc. Because cycles can exist in graphs, our algorithm will need to ensure that we don't get caught up in an infinite loop. It will also need to ensure that we don't visit nodes more than once, as this would be wasteful. The algorithm will also need to determine if and when all nodes have already been visited, which corresponds to the case where the item which is being searched for does not exist in the graph. In the sections below, we'll introduced depth first search and breadth first search, both of which are based on discovering nodes and exploring them. We'll also discuss the difference between searching from one node vs searching the entire graph, including disconnected subgraphs.
Depth First Search
In the steps provided above, we iterate over each node in the graph outside of the depth-first search algorithm and reuse the same visitedNodes set to filter out nodes which have already appeared in a depth-first search so we don't perform any redundant searches. The code below outlines the implementation for these methods. Note that in some programming languages, Stacks, Queues, and Sets are not provided by the language. In those cases, I've provided implementations below. If you'd like to learn more about our Php set implementation, please visit our page on php sets with object references.
Iterative Depth First Search
The code below implements this algorithm and provides implementations for Stacks for languages which do not provide it by default:
Breadth First Search
You may have noticed that the steps above seem similar to the steps for the iterative depth-first search algorithm. These algorithms are actually entirely the same, except the breadth-first search algorithm uses a queue instead of a stack. The nature of queues vs stacks changes the order in which nodes are traversed, thus resulting in bfs instead of dfs. If you're not familiar with queues or would like a quick refresher, please visit our introduction to queues. The code below implements this algorithm, and in cases where the languages does not provide a queue implementation, the code below does:
Note that we have not included a recursive implementation for the depth first search. The recursive implementation we've provided for depth-first search utilizes the function call stack which is handled internally by the operating system. There is no "call queue" which we can directly utilize, so any recursive implementation of breadth-first search would be more complex, and therefore is omitted from this article.
Iterating Over and Visiting Nodes
In these other use cases, the algorithms will be largely the same; the only differences will be in where the return statements are. Instead of baking the search logic into the algorithm, we could introduce a layer of abstract to seperate the logic of traversing the graph vs the logic of what to do when we visit a node. This is a common use case for the visitor pattern. With that layer of abstraction, we could still perform searches, but we could also perform some of the other items listed above. In other words, we can make the behavior a parameter of the search algorithm via a callback function. The use of dfs vs bfs will change the ordering of when each callback function is invoked, but will otherwise perform the same function.
When to Use DFS vs BFS
Depth-first search and breadth-first search both accomplish the same goals, but selecting the right algorithm can make a huge difference in time and memory consumed during the search / traversal. In the table below, we'll outline the different kinds of use cases each algorithm is useful for. We'll also include an entry for list iteration, which is applicable in cases where we have an external list of all nodes in addition to the nodes themselves.
|Algorithm||When To Use||Example Use Cases|
|List Iteration||When we have access to a consolidated list or set of all vertices and need to find some specific value and there is no special relationship between the nodes in the graph. Note: if we only have a graph represented by a node or list of nodes, and there is no single consolidated list, we cannot use this method.|
|Depth-First Search||If we are performing a search and expect the value we are looking for to be deep in the graph with respect to the entry node, this will find the solution faster than breadth-first search and possibly list iteration. This also applies if each depth of the graph implies some change, such as a turn taken in a game. We can also use dfs if we want to avoid the extra memory overhead of using the queue in breadth-first search.|
|Breadth-First Search||If we are searching and expect the value to be close to the entry node, this will find the solution faster than depth-first search and possibly list iteration. We can also use bfs if the paths of the graph run very deep and using a queue will use less memory than using the stack for the full paths.|
In addition to the points above, if a particular graph has a certain ordering based on the relationships between nodes and how they are connected, dfs or bfs may come into play based on the nature of that ordering.
Space and Time Complexity
The space and time complexity for depth-first search and breadth-first search are the same, as their implementations themselves are very similar. In the table below, we'll describe complexity in terms of the number of nodes v and the number of edges e.
|Space||O(v)||The algorithm uses a set to record nodes which have been visited and a stack/queue to record which nodes will be visited next. The worst-case sizes of both are proportional to the number of vertices.|
|Time||O(v + e)||The algorithm will visit each node once per number of edges which connect to it, or just once in the case it has no connections.|
Searching Over Large or Distributed Graphs
The algorithm implementations above work in cases where the entire graph is held in memory of a single computer / device. In cases where the graph is distributed over a network, and we use HTTP calls to traverse the graph, or in cases where the device has low memory and we do not want to keep a set of visited nodes which requires additional memory, we can use algorithms which implicitly represent depth-first and breadth-first searches but operate using a more "distributed" version of the algorithms. If you would like to read more on this, please visit the page below for more info: