Understanding Graph Traversal - BFS vs DFS

calendar Mar 12, 2019 · 7 min read · programming algorithm  ·
Share on: linkedin copy

Breadth-first search (BFS) and depth-first search (DFS) are two algorithms for traversing graphs. These algorithms are used to search for specific nodes or to find the shortest path between two nodes in a graph.

BFS

The breadth-first search (BFS) algorithm is a graph traversal algorithm that explores all of the neighbors of a starting node before moving on to any of the neighbor's neighbors. It is called a "breadth-first" algorithm because it explores the neighbors at each level of the graph before moving on to the next level.

Here is a step-by-step example of how the BFS algorithm works, using a simple graph as an example:

  1. Start by placing the starting node on a queue.
  2. Take the first node off the queue and explore all of its neighbors. For each of these neighbors, add them to the queue if they have not been explored yet.
  3. Take the next node off the queue and explore all of its neighbors. For each of these neighbors, add them to the queue if they have not been explored yet.
  4. Repeat this process until the queue is empty, or until you have found the goal node (if you are searching for a specific node in the graph).

Here is some sample Python code that implements the BFS algorithm:

 1# define the graph as a dictionary where the keys are the nodes and the values are the neighbors of each node
 2graph = {
 3    'A': ['B', 'C', 'E'],
 4    'B': ['A', 'D', 'E'],
 5    'C': ['A', 'F', 'G'],
 6    'D': ['B'],
 7    'E': ['A', 'B', 'D'],
 8    'F': ['C'],
 9    'G': ['C']
10}
11
12# define the BFS function, which takes in the graph and the starting node as inputs
13def BFS(graph, start):
14    # create a queue to store the nodes that need to be explored
15    queue = []
16    # add the starting node to the queue
17    queue.append(start)
18    # create a set to store the nodes that have been explored
19    visited = set()
20    # while the queue is not empty, continue exploring nodes
21    while queue:
22        # take the first node off the queue
23        node = queue.pop(0)
24        # if the node has not been explored yet, explore it
25        if node not in visited:
26            # add the node to the set of explored nodes
27            visited.add(node)
28            # add the neighbors of the node to the queue
29            neighbors = graph[node]
30            for neighbor in neighbors:
31                queue.append(neighbor)
32    # return the set of explored nodes
33    return visited
34
35# test the BFS function by finding all of the nodes that can be reached from the starting node 'A'
36print(BFS(graph, 'A'))
37# this should return {'A', 'B', 'C', 'E', 'D', 'F', 'G'}

Complexity Analysis:

  • The time complexity of BFS is O(|V| + |E|), where |V| is the number of nodes in the graph and |E| is the number of edges. This is because BFS explores all of the nodes and edges in the graph.
  • The space complexity of BFS is O(|V|), where |V| is the number of nodes in the graph. This is because BFS uses a queue to store the nodes that need to be explored, and the size of the queue can grow up to |V| in the worst case.

DFS

The depth-first search (DFS) algorithm is a graph traversal algorithm that explores as far as possible along each branch before moving to the next branch. It is called a "depth-first" algorithm because it explores the depth of the graph first before exploring the breadth.

Here is a step-by-step example of how the DFS algorithm works, using a simple graph as an example:

  1. Start by placing the starting node on a stack.
  2. Take the top node off the stack and explore all of its neighbors. For each of these neighbors, add them to the stack if they have not been explored yet.
  3. Take the next node off the stack and explore all of its neighbors. For each of these neighbors, add them to the stack if they have not been explored yet.
  4. Repeat this process until the stack is empty, or until you have found the goal node (if you are searching for a specific node in the graph).

Here is some sample Python code that implements the DFS algorithm:

 1# define the graph as a dictionary where the keys are the nodes and the values are the neighbors of each node
 2graph = {
 3    'A': ['B', 'C', 'E'],
 4    'B': ['A', 'D', 'E'],
 5    'C': ['A', 'F', 'G'],
 6    'D': ['B'],
 7    'E': ['A', 'B', 'D'],
 8    'F': ['C'],
 9    'G': ['C']
10}
11
12# define the DFS function, which takes in the graph and the starting node as inputs
13def DFS(graph, start):
14    # create a stack to store the nodes that need to be explored
15    stack = []
16    # add the starting node to the stack
17    stack.append(start)
18    # create a set to store the nodes that have been explored
19    visited = set()
20    # while the stack is not empty, continue exploring nodes
21    while stack:
22        # take the top node off the stack
23        node = stack.pop()
24        # if the node has not been explored yet, explore it
25        if node not in visited:
26            # add the node to the set of explored nodes
27            visited.add(node)
28            # add the neighbors of the node to the stack
29            neighbors = graph[node]
30            for neighbor in neighbors:
31                stack.append(neighbor)
32    # return the set of explored nodes
33    return visited
34
35# test the DFS function by finding all of the nodes that can be reached from the starting node 'A'
36print(DFS(graph, 'A'))
37# this should return {'A', 'B', 'D', 'E', 'C', 'F', 'G'}

Complexity Analysis:

  • The time complexity of DFS is O(|V| + |E|), where |V| is the number of nodes in the graph and |E| is the number of edges. This is because DFS explores all of the nodes and edges in the graph.
  • The space complexity of DFS is O(|V|), where |V| is the number of nodes in the graph. This is because DFS uses a stack to store the nodes that need to be explored, and the size of the stack can grow up to |V| in the worst case.

When to Use BFS and When to Use DFS?

The choice between using the breadth-first search (BFS) or the depth-first search (DFS) algorithm depends on the specific problem you are trying to solve and the characteristics of the data you are working with.

Here are some general guidelines for when to use each algorithm:

  • Use BFS when you want to find the shortest path between two nodes in a graph. This is because BFS always explores the nodes at each level of the graph before moving on to the next level, so it is guaranteed to find the shortest path if one exists.
  • Use DFS when the graph is very large and you want to save memory. This is because DFS only explores a few nodes as deep as possible before moving on to the next branch, so it uses less memory than BFS.
  • Use DFS when you want to find all of the nodes in a connected component of a graph. This is because DFS explores each branch of the graph as deeply as possible, so it is guaranteed to find all of the nodes in a connected component if one exists.
  • Use BFS when the graph is not very large and you want to find the shortest path between two nodes, even if the graph is not connected. This is because BFS explores all of the neighbors of a starting node before moving on to any of the neighbor's neighbors, so it is guaranteed to find the shortest path between two nodes if one exists.

Author: Sadman Kabir Soumik