What is the difference between depth-first search (DFS) and breadth-first search (BFS)?

Depth-first search (DFS) and breadth-first search (BFS) are two common algorithms used for traversing and searching graph data structures. While both algorithms can be used to explore a graph and find a particular node or path, they differ in their approach and behavior.

DFS starts at the root node (or any starting node) and explores as far as possible along each branch before backtracking. This means that it traverses the graph depth-wise before exploring its breadth. In other words, it explores as deep as possible before going wide. DFS uses a stack data structure to keep track of the nodes to visit next. DFS is useful for finding all nodes in a graph, determining whether a path exists between two nodes, and finding cycles in a graph.

Here is an example of DFS traversal in a binary tree:

void DFS(Node node) {
    if (node == null) {
        return;
    }
    System.out.print(node.value + " ");
    DFS(node.left);
    DFS(node.right);
}

In this example, DFS starts at the root node and recursively visits the left subtree and right subtree of each node in a depth-first order. The output of DFS traversal would be the values of the nodes in the binary tree printed in a depth-first order.

BFS, on the other hand, starts at the root node (or any starting node) and explores all the neighboring nodes at the current depth before moving on to the next level. This means that it traverses the graph breadth-wise before exploring its depth. In other words, it explores as wide as possible before going deep. BFS uses a queue data structure to keep track of the nodes to visit next. BFS is useful for finding the shortest path between two nodes in a graph, finding the minimum number of moves required to reach a destination, and finding the connected components of a graph.

Here is an example of BFS traversal in a binary tree:

void BFS(Node node) {
    Queue<Node> queue = new LinkedList<>();
    queue.add(node);
    while (!queue.isEmpty()) {
        Node current = queue.poll();
        System.out.print(current.value + " ");
        if (current.left != null) {
            queue.add(current.left);
        }
        if (current.right != null) {
            queue.add(current.right);
        }
    }
}

In this example, BFS starts at the root node and visits all the neighboring nodes at the current depth before moving on to the next level. It uses a queue to keep track of the nodes to visit next. The output of BFS traversal would be the values of the nodes in the binary tree printed in a breadth-first order.

In summary, DFS and BFS are two common algorithms used for traversing and searching graph data structures. DFS explores as far as possible along each branch before backtracking, while BFS explores all the neighboring nodes at the current depth before moving on to the next level. DFS is useful for finding all nodes in a graph and determining whether a path exists between two nodes, while BFS is useful for finding the shortest path between two nodes and finding the connected components of a graph.