Breadth First Traversal and Depth First Traversal

BFS and DFS

Breadth-first Search (BFS) and Depth First Traversal (DFS) are the two main algorithms to traverse the graph. BFS traverses breadthwise whereas DFS traverses depthwise. Both come under the category of recursive algorithms.

In this DSA tutorial, we will learn these two algorithms in detail. To further enhance your understanding and application of BFS and DFS, consider enrolling in the Data Structures And Algorithms Certification, to gain comprehensive insights into effective data structure utilization for improved problem-solving and time management.

What is Breadth First Traversal in Data Structures?

Breadth-first Search (BFS) is a graph traversal algorithm that explores all the vertices of a graph in a breadthwise order. It means it starts at a given vertex or node and visits all the vertices at the same level before moving to the next level. It is a recursive algorithm for searching all the vertices of a graph or tree data structure.

BFS Algorithm

1. Visited
2. Not Visited

Here's a step-by-step explanation of how the BFS algorithm works:

1. Start by selecting a starting vertex or node.
2. Add the starting vertex to the end of the queue.
3. Mark the starting vertex as visited and add it to the visited array/list.
4. While the queue is not empty, do the following steps:
• Remove the front vertex from the queue.
• Visit the removed vertex and process it.
• Enqueue all the adjacent vertices of the removed vertex that have not been visited yet.
• Mark each visited adjacent vertex as visited and add it to the visited array/list.
5. Repeat step 4 until the queue is empty.

The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node.

Example to illustrate the working of the BFS Algorithm

We use an undirected graph with 5 vertices.

We start from vertex 1, the BFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack.

Next, we visit the element at the front of the queue i.e. 2, and go to its adjacent nodes. Since 1 has already been visited, we visit 3 instead.

Vertex 3 has an unvisited adjacent vertex in 5, so we add that to the back of the queue and visit 4, which is at the front of the queue.

Only 5 remain in the queue since the only adjacent node of 4 i.e. 1 is already visited. We visited it.

Since the queue is empty, we have completed the Breadth First Traversal of the graph.

Read More - DSA Interview Questions and Answers

Pseudocode of Breadth-First Search Algorithm

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty 
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

Rules of Breadth-First Traversal Algorithm

1. A Queue(which facilitates FIFO) is used in Breadth-First Search.
2. Since Graphs have no root, we can start the Breadth-First Search traversal from any Vertex of the Graph.
3. While Breadth-First Search, we visit all the Nodes in the Graph.
4. For every Node already visited, we visit all of its unvisited neighboring Nodes and add them to the Queue.
5. Breadth-First Search continues until all Vertices in the graph are visited.
6. No loops are caused in Breadth-First Search, as we prevent revisiting the same Node by marking them visited.

Implementation of BFS Algorithm in Different Programming Languages

from collections import deque

class Graph:
    def __init__(self, v):
        self.V = v
        self.adj = [deque() for _ in range(v)]

    def add_edge(self, v, w):
        self.adj[v].append(w)

    def bfs(self, s):
        visited = [False] * self.V
        queue = deque()

        visited[s] = True
        queue.append(s)

        while queue:
            s = queue.popleft()
            print(s, end=" ")

            for n in self.adj[s]:
                if not visited[n]:
                    visited[n] = True
                    queue.append(n)

if __name__ == "__main__":
    graph = Graph(7)

    graph.add_edge(0, 7)
    graph.add_edge(0, 2)
    graph.add_edge(1, 3)
    graph.add_edge(1, 4)
    graph.add_edge(2, 5)
    graph.add_edge(2, 1)
    graph.add_edge(3, 6)

    print("Following is Breadth First Traversal (starting from vertex 2):")
    graph.bfs(2)
    

// BFS algorithm in Java

import java.util.*;

public class Main {
  private int V;
  private LinkedList adj[];

  // Create a graph
  Main(int v) {
    V = v;
    adj = new LinkedList[v];
    for (int i = 0; i < v; ++i)
      adj[i] = new LinkedList();
  }

  // Add edges to the graph
  void addEdge(int v, int w) {
    adj[v].add(w);
  }

  // BFS algorithm
  void BFS(int s) {

    boolean visited[] = new boolean[V];

    LinkedList queue = new LinkedList();

    visited[s] = true;
    queue.add(s);

    while (queue.size() != 0) {
      s = queue.poll();
      System.out.print(s + " ");

      Iterator i = adj[s].listIterator();
      while (i.hasNext()) {
        int n = i.next();
        if (!visited[n]) {
          visited[n] = true;
          queue.add(n);
        }
      }
    }
  }

  public static void main(String args[]) {
    Main graph = new Main(7);

    graph.addEdge(0, 7);
graph.addEdge(0, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(2, 1);
graph.addEdge(3, 6);

    System.out.println("Following is Breadth First Traversal " + "(starting from vertex 2)");

    graph.BFS(2);
  }
}
    

#include <iostream>
#include <list>
#include <queue>

class Graph {
private:
    int V;
    std::list* adj;

public:
    Graph(int v) : V(v) {
        adj = new std::list[v];
    }

    ~Graph() {
        delete[] adj;
    }

    void addEdge(int v, int w) {
        adj[v].push_back(w);
    }

    void bfs(int s) {
        bool* visited = new bool[V]{false};
        std::queue queue;

        visited[s] = true;
        queue.push(s);

        while (!queue.empty()) {
            s = queue.front();
            queue.pop();

            std::cout << s << " ";

            for (int n : adj[s]) {
                if (!visited[n]) {
                    visited[n] = true;
                    queue.push(n);
                }
            }
        }

        delete[] visited;
    }
};

int main() {
    Graph graph(7);

    graph.addEdge(0, 7);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    graph.addEdge(2, 1);
    graph.addEdge(3, 6);

    std::cout << "Following is Breadth First Traversal (starting from vertex 2):" << std::endl;
    graph.bfs(2);

    return 0;
}
    

Output

Following is Breadth First Traversal (starting from vertex 2):
2 5 1 3 4 6

Applications of Breadth First Search Algorithm

1. Minimum spanning tree for unweighted graphs:In Breadth-First Search we can reach from any given source vertex to another vertex, with the minimum number of edges, and this principle can be used to find the minimum spanning tree which is the path covering all vertices in the shortest paths.
2. Peer-to-peer networking: In Peer-to-peer networking, to find the neighboring peer from any other peer, the Breadth-First Search is used.
3. Crawlers in search engines: Search engines need to crawl the internet. To do so, they can start from any source page, follow the links contained in that page in the Breadth-First Search manner, and therefore explore other pages.
4. GPS navigation systems: To find locations within a given radius from any source person, we can find all neighboring locations using the Breadth-First Search, and keep on exploring until those are within the K radius.
5. Broadcasting in networks: While broadcasting from any source, we find all its neighboring peers and continue broadcasting to them, and so on.
6. Path Finding: To find if there is a path between 2 vertices, we can take any vertex as a source, and keep on traversing until we reach the destination vertex. If we explore all vertices reachable from the source and cannot find the destination vertex, then that means there is no path between these 2 vertices.
7. Finding all reachable Nodes from a given Vertex: All vertices that are reachable from a given vertex can be found using the BFS approach in any disconnected graph. The vertices that are marked as visited in the visited array after the BFS is complete contain all those reachable vertices.

What is Depth First Traversal in Data Structures?

The depth-first search algorithm works by starting from an arbitrary node of the graph and exploring as far as possible before backtracking i.e. moving to an adjacent node until there is no unvisited adjacent node. After backtracking, it repeats the same process for all the remaining vertices which have not been visited till now. It is a recursive algorithm for searching all the vertices of a graph or tree data structure.

DFS Algorithm

1. Visited
2. Not Visited

The reason for this division is to prevent the traversal of the same node again thus, avoiding cycles in the graph. Depth First Traversal in Data Structure uses a stack to keep track of the vertices to visit. A boolean visited array is used to mark the visited vertices.

Here's a step-by-step explanation of how the DFS algorithm works::

1. Start by selecting a starting vertex or node.
2. Add the starting vertex on top of a stack.
3. Take the top item of the stack and add it to the visited list/array.
4. Create a list of that vertex's adjacent nodes. Add the ones that aren't in the visited list to the top of the stack.
Keep repeating steps 3 and 4 until the stack is empty.

The graph might have two different disconnected parts so to make sure that we cover every vertex, we can also run the BFS algorithm on every node.

Example to illustrate the working of the DFS Algorithm

We use an undirected graph with 5 vertices.

We start from vertex 1, the DFS algorithm starts by putting it in the Visited list and putting all its adjacent vertices in the stack.

Next, we visit the element at the top of stack i.e. 2 and go to its adjacent nodes. Since 1 has already been visited, we visit 3 instead.

Vertex 3 has an unvisited adjacent vertex in 5, so we add that to the top of the stack and visit it.

After we visit the last element 4, it doesn't have any unvisited adjacent nodes, so we have completed the Depth First Traversal of the graph.

Pseudocode of Depth-First Search Algorithm

DFS(G, u)
    u.visited = true
    for each v ∈ G.Adj[u]
        if v.visited == false
            DFS(G,v)
     
init() {
    For each u ∈ G
        u.visited = false
     For each u ∈ G
       DFS(G, u)
}

Implementation of DFS Algorithm in Different Programming Languages

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.vertices = vertices
        self.adjLists = defaultdict(list)
        self.visited = [False] * vertices

    def addEdge(self, src, dest):
        self.adjLists[src].append(dest)

    def DFS(self, vertex):
        self.visited[vertex] = True
        print(vertex, end=" ")

        for adj in self.adjLists[vertex]:
            if not self.visited[adj]:
                self.DFS(adj)

# Create a graph given
g = Graph(7)
g.addEdge(0, 7)
g.addEdge(0, 2)
g.addEdge(1, 3)
g.addEdge(1, 4)
g.addEdge(2, 5)
g.addEdge(2, 1)
g.addEdge(3, 6)

print("Following is Depth First Traversal (starting from vertex 2):")
g.DFS(2)
    

import java.util.*;

public class Main {
  private LinkedList adjLists[];
  private boolean visited[];

  // Graph creation
  Main(int vertices) {
    adjLists = new LinkedList[vertices];
    visited = new boolean[vertices];

    for (int i = 0; i < vertices; i++)
      adjLists[i] = new LinkedList();
  }

  // Add edges
  void addEdge(int src, int dest) {
    adjLists[src].add(dest);
  }

  // DFS algorithm
  void DFS(int vertex) {
    visited[vertex] = true;
    System.out.print(vertex + " ");

    Iterator ite = adjLists[vertex].listIterator();
    while (ite.hasNext()) {
      int adj = ite.next();
      if (!visited[adj])
        DFS(adj);
    }
  }

  public static void main(String args[]) {
    Main g = new Main(7);

   g.addEdge(0, 7);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 5);
g.addEdge(2, 1);
g.addEdge(3, 6);

    System.out.println("Following is Depth First Traversal" + "(starting from vertex 2)");

    g.DFS(2);
  }
}
    

#include <iostream>
#include <list>
#include <iterator>

class Graph {
private:
    int vertices;
    std::list* adjLists;
    bool* visited;

public:
    Graph(int v) : vertices(v) {
        adjLists = new std::list[v];
        visited = new bool[v]{false};
    }

    ~Graph() {
        delete[] adjLists;
        delete[] visited;
    }

    void addEdge(int src, int dest) {
        adjLists[src].push_back(dest);
    }

    void DFS(int vertex) {
        visited[vertex] = true;
        std::cout << vertex << " ";

        for (auto it = adjLists[vertex].begin(); it != adjLists[vertex].end(); ++it) {
            int adj = *it;
            if (!visited[adj])
                DFS(adj);
        }
    }
};

int main() {
    Graph g(7);

    g.addEdge(0, 7);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);
    g.addEdge(2, 5);
    g.addEdge(2, 1);
    g.addEdge(3, 6);

    std::cout << "Following is Depth First Traversal (starting from vertex 2):" << std::endl;
    g.DFS(2);

    return 0;
}
    

Output

Following is Depth First Traversal (starting from vertex 2):
2 5 1 3 6 4    

Applications of Depth First Search Algorithm

1. Finding any path between two vertices u and v in the graph.
2. Finding the number of connected components present in a given undirected graph.
3. For doing topological sorting of a given directed graph.
4. Finding strongly connected components in the directed graph.
5. Finding cycles in the given graph.
6. To check if the given graph is bipartite.

Complexity Analysis of BFS and DFS Algorithms

Here, V is the number of nodes and E is the number of edges.

Difference between BFS and DFS

Summary

Understanding these two types of graph traversal methods is essential to understanding the graph data structure. We have seen what is depth-first traversal and breadth-first traversal algorithms, how they are implemented, their time complexity, applications, differences, etc. To test your practical understanding of these two techniques, enroll in our Best Data Structures And Algorithms Course.