Difference between BFS and DFS | DSA in C++ - Software Development PDF Download

Introduction

When dealing with graphs, one of the fundamental tasks is traversing through its nodes or vertices. Breadth-First Search (BFS) and Depth-First Search (DFS) are two popular algorithms used for graph traversal. In this article, we will delve into the key differences between BFS and DFS, including their working principles, implementation in C++, and provide examples to help you understand their usage.

Understanding BFS (Breadth-First Search):

BFS explores a graph in a breadthward motion, visiting all the neighbors of a node before moving on to the next level. The primary steps involved in BFS are:

• Start with a source node and initialize an empty queue.
• Enqueue the source node into the queue.
• While the queue is not empty, dequeue a node, mark it as visited, and print its value.
• Enqueue all the unvisited neighbors of the current node into the queue.

Example: Consider the following graph:

    A

     / \

    B   C

   / \   \

  D   E   F

The BFS traversal of this graph starting from node A would be: A, B, C, D, E, F.

Implementation in C++:

#include <iostream>

#include <queue>

#include <vector>

using namespace std;

void BFS(vector<vector<int>>& graph, int start) {

    vector<bool> visited(graph.size(), false);

    queue<int> q;    

    q.push(start);

    visited[start] = true;    

    while (!q.empty()) {

        int current = q.front();

        q.pop();

        cout << current << " ";      

        for (int neighbor : graph[current]) {

            if (!visited[neighbor]) {

                q.push(neighbor);

                visited[neighbor] = true;

            }

        }

    }

}

int main() {

    // Create an adjacency list for the graph

    vector<vector<int>> graph = {

        {1},

        {0, 3, 4},

        {4},

        {1},

        {2}

    };    

    cout << "BFS Traversal: ";

    BFS(graph, 0);   

    return 0;

}

Output:

BFS Traversal: 0 1 3 4 2

Understanding DFS (Depth-First Search):

DFS explores a graph in a depthward motion, visiting a node and then recursively visiting its unvisited neighbors. The primary steps involved in DFS are:

• Start with a source node and initialize an empty stack.
• Push the source node onto the stack.
• While the stack is not empty, pop a node, mark it as visited, and print its value.
• Push all the unvisited neighbors of the current node onto the stack.

Example: Consider the same graph as above.

The DFS traversal of this graph starting from node A would be: A, B, D, E, C, F.

Implementation in C++:

#include <iostream>

#include <stack>

#include <vector>

using namespace std;

void DFS(vector<vector<int>>& graph, int start) {

    vector<bool> visited(graph.size(), false);

    stack<int> st;    

    st.push(start);

    visited[start] = true;    

    while (!st.empty()) {

        int current = st.top();

        st.pop();

        cout << current << " ";        

        for (int neighbor : graph[current]) {

            if (!visited[neighbor]) {

                st.push(neighbor);

                visited[neighbor] = true;

            }

        }

    }

}

int main() {

    // Create an adjacency list for the graph

    vector<vector<int>> graph = {

        {1},

        {0, 3, 4},

        {4},

        {1},

        {2}

    };    

    cout << "DFS Traversal: ";

    DFS(graph, 0);    

    return 0;

}

Output:

DFS Traversal: 0 1 3 4 2

Comparing BFS and DFS:

• Time Complexity:
  • Both BFS and DFS visit each node once, resulting in a time complexity of O(V), where V is the number of vertices.
• Space Complexity:
  • BFS requires additional space to store the queue, resulting in a space complexity of O(V).
  • DFS requires additional space to store the stack, resulting in a space complexity of O(V) due to the recursion stack.
• Path Finding:
  • BFS guarantees finding the shortest path between two nodes in an unweighted graph.
  • DFS does not guarantee finding the shortest path, but it can be used to find all possible paths between two nodes.
• Memory Requirements:
  • BFS typically requires more memory compared to DFS due to the need to store all the neighbors of a node in a queue.

Sample Problems

• Given a binary tree, implement BFS and DFS to traverse and print its elements.
• Find the number of connected components in an undirected graph using BFS or DFS.
• Determine whether a cycle exists in a directed graph using BFS or DFS.

Conclusion

BFS and DFS are essential algorithms for graph traversal. BFS explores the graph level by level, while DFS explores it depth-first. Both algorithms have their strengths and are used in various applications. By understanding their differences and implementations in C++, you can utilize them effectively in your programs and solve a wide range of graph-related problems.