Difference between BFS and DFS

Breadth-First Search (BFS) and Depth-First Search (DFS) are two fundamental algorithms used for traversing or searching graphs and trees. This article covers the basic difference between Breadth-First Search and Depth-First Search.

Breadth-First Search (BFS):

BFS, Breadth-First Search, is a vertex-based technique for finding the shortest path in the graph. It uses a Queue data structure that follows first in first out. In BFS, one vertex is selected at a time when it is visited and marked then its adjacent are visited and stored in the queue. It is slower than DFS.
Example:

 Input:
        A
       / \
      B   C
     /   / \
    D   E   F

Output:

A, B, C, D, E, F

Code:

C++

#include <iostream>
#include <list>

using namespace std;

// This class represents a directed graph using adjacency
// list representation
class Graph {
    int V; // No. of vertices

    // Pointer to an array containing adjacency lists
    list<int>* adj;

public:
    Graph(int V); // Constructor

    // function to add an edge to graph
    void addEdge(int v, int w);

    // prints BFS traversal from a given source s
    void BFS(int s);
};

Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
}

void Graph::addEdge(int v, int w)
{
    adj[v].push_back(w); // Add w to v’s list.
}

void Graph::BFS(int s)
{
    // Mark all the vertices as not visited
    bool* visited = new bool[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;

    // Create a queue for BFS
    list<int> queue;

    // Mark the current node as visited and enqueue it
    visited[s] = true;
    queue.push_back(s);

    // 'i' will be used to get all adjacent vertices of a
    // vertex
    list<int>::iterator i;

    // Create a mapping from integers to characters
    char map[6] = { 'A', 'B', 'C', 'D', 'E', 'F' };

    while (!queue.empty()) {
        // Dequeue a vertex from queue and print it
        s = queue.front();
        cout << map[s] << " "; // Use the mapping to print
                               // the original label
        queue.pop_front();

        // Get all adjacent vertices of the dequeued vertex
        // s If a adjacent has not been visited, then mark
        // it visited and enqueue it
        for (i = adj[s].begin(); i != adj[s].end(); ++i) {
            if (!visited[*i]) {
                queue.push_back(*i);
                visited[*i] = true;
            }
        }
    }
}

int main()
{
    // Create a graph given in the diagram
    /*     A
          / \
         B   C
        /   / \
       D   E   F
    */
    Graph g(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);

    cout << "Breadth First Traversal is: ";
    g.BFS(0); // Start BFS from A (0)

    return 0;
}

Python

from collections import deque

# This class represents a directed graph using adjacency list representation


class Graph:
    def __init__(self, V):
        self.V = V  # No. of vertices
        self.adj = [[] for _ in range(V)]  # Adjacency lists

    # Function to add an edge to graph
    def addEdge(self, v, w):
        self.adj[v].append(w)  # Add w to v’s list

    # Prints BFS traversal from a given source s
    def BFS(self, s):
        # Mark all the vertices as not visited
        visited = [False] * self.V

        # Create a queue for BFS
        queue = deque()

        # Mark the current node as visited and enqueue it
        visited[s] = True
        queue.append(s)

        # Create a mapping from integers to characters
        mapping = ['A', 'B', 'C', 'D', 'E', 'F']

        while queue:
            # Dequeue a vertex from queue and print it
            s = queue.popleft()
            # Use the mapping to print the original label
            print(mapping[s], end=" ")

            # Get all adjacent vertices of the dequeued vertex s
            # If an adjacent has not been visited, then mark it visited
            # and enqueue it
            for i in self.adj[s]:
                if not visited[i]:
                    queue.append(i)
                    visited[i] = True


if __name__ == "__main__":
    # Create a graph given in the diagram
    #      A
    #     / \
    #    B   C
    #   /   / \
    #  D   E   F
    g = Graph(6)
    g.addEdge(0, 1)
    g.addEdge(0, 2)
    g.addEdge(1, 3)
    g.addEdge(2, 4)
    g.addEdge(2, 5)

    print("Breadth First Traversal is: ", end="")
    g.BFS(0)  # Start BFS from A (0)

JavaScript

// This class represents a directed graph using adjacency list representation
class Graph {
    constructor(V) {
        this.V = V; // No. of vertices
        this.adj = new Array(V).fill(null).map(() => []); // Array of adjacency lists
    }

    // Function to add an edge to graph
    addEdge(v, w) {
        this.adj[v].push(w); // Add w to v’s list.
    }

    // Function to perform BFS traversal from a given source s
    BFS(s) {
        // Mark all the vertices as not visited
        let visited = new Array(this.V).fill(false);

        // Create a queue for BFS
        let queue = [];

        // Mark the current node as visited and enqueue it
        visited[s] = true;
        queue.push(s);

        // Mapping from integers to characters
        let map = ['A', 'B', 'C', 'D', 'E', 'F'];

        while (queue.length > 0) {
            // Dequeue a vertex from queue and print it
            s = queue.shift();
            console.log(map[s] + " "); // Use the mapping to print the original label

            // Get all adjacent vertices of the dequeued vertex s
            // If an adjacent has not been visited, then mark it visited
            // and enqueue it
            for (let i of this.adj[s]) {
                if (!visited[i]) {
                    queue.push(i);
                    visited[i] = true;
                }
            }
        }
    }
}

// Main function
function main() {
    // Create a graph given in the diagram
    /*     A
          / \
         B   C
        /   / \
       D   E   F
    */
    let g = new Graph(6);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(2, 4);
    g.addEdge(2, 5);

    console.log("Breadth First Traversal is: ");
    g.BFS(0); // Start BFS from A (0)
}

// Run the main function
main();

Output

Breadth First Traversal is: A B C D E F

Depth First Search (DFS):

DFS, Depth First Search, is an edge-based technique. It uses the Stack data structure and performs two stages, first visited vertices are pushed into the stack, and second if there are no vertices then visited vertices are popped.
Example:

  Input:
        A
       / \
      B   D
     /   / \
    C   E   F

Output:

A, B, C, D, E, F