Key differences between Breadth-First Search and Depth-First Search

Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores vertices in a graph layer by layer. Starting from a selected node, BFS visits all its adjacent nodes at the current depth level before moving to nodes at the next depth level. This method ensures that all nodes are explored in the order of their distance from the start node, making BFS particularly useful for shortest path problems in unweighted graphs. BFS is implemented using a queue which helps in tracking nodes to explore next. As nodes are visited, they are marked and enqueued, ensuring each node is processed once. BFS is widely used in networking, pathfinding algorithms, and for analyzing social networking graphs due to its ability to efficiently map all reachable nodes.

Functions of BFS:

• Shortest Path:

BFS is used to find the shortest path between two nodes in an unweighted graph, providing the minimum number of edges that connect them.

• Level Order Traversal:

In trees, BFS can be employed to perform a level order traversal, where nodes at the same depth are visited sequentially.

• Connectivity Check:

BFS can determine if a graph is connected by starting from one node and checking if all nodes are reachable.

• Cycle Detection:

In undirected graphs, BFS can detect cycles by checking if a visited node is revisited through a different parent node.

• Bipartiteness Check:

BFS can check whether a graph is bipartite by attempting to color the graph using two colors as it traverses, ensuring no two adjacent nodes share the same color.

• Network Broadcast:

In networking, BFS can simulate the process of broadcasting information from a source node to all other nodes in the network.

• Finding All Nodes Within One Connectivity Component:

BFS can explore and mark all nodes within a single connected component of the graph, which is useful for cluster analysis.

• Maximum Flow Problem:

BFS is used in the Edmonds-Karp algorithm to find maximum flow in a flow network. It searches for the shortest augmenting path from the source to the sink in the residual graph.

Example of BFS:

The graph is unweighted and undirected, and the BFS traversal starts from a specified start node.

import java.util.*;

public class BFSExample {

    private int V;   // Number of vertices

    private LinkedList<Integer> adj[]; //Adjacency Lists

    // Constructor

    BFSExample(int v) {

        V = v;

        adj = new LinkedList[v];

        for (int i = 0; i < v; ++i)

            adj[i] = new LinkedList();

    }

    // Function to add an edge into the graph

    void addEdge(int v, int w) {

        adj[v].add(w);

    }

    // prints BFS traversal from a given source s

    void BFS(int s) {

        // Mark all the vertices as not visited(By default set as false)

        boolean visited[] = new boolean[V];

        // Create a queue for BFS

        LinkedList<Integer> queue = new LinkedList<Integer>();

        // Mark the current node as visited and enqueue it

        visited[s] = true;

        queue.add(s);

        while (queue.size() != 0) {

            // Dequeue a vertex from queue and print it

            s = queue.poll();

            System.out.print(s + ” “);

            // Get all adjacent vertices of the dequeued vertex s

            // If a neighbor has not been visited, then mark it visited and enqueue it

            Iterator<Integer> i = adj[s].listIterator();

            while (i.hasNext()) {

                int n = i.next();

                if (!visited[n]) {

                    visited[n] = true;

                    queue.add(n);

                }

            }

        }

    }

    // Main method to run the BFS example

    public static void main(String args[]) {

        BFSExample g = new BFSExample(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

        System.out.println(“Following is Breadth First Traversal (starting from vertex 0)”);

        g.BFS(0);

    }

}

Explanation

• BFSExample class:

Creates a graph with a specified number of vertices using an adjacency list.

• addEdge method:

Adds an undirected edge between two vertices.

• BFS method:

Implements the BFS algorithm starting from a vertex s. It uses a boolean array visited[] to keep track of visited vertices and a queue to hold the vertices for BFS traversal.

• main method:

Sets up the graph by adding edges and initiates a BFS traversal starting from vertex 0.

Depth-First Search (DFS)

Depth-First Search (DFS) is a graph traversal algorithm that prioritizes exploration of nodes as deep as possible before backtracking. Starting from a selected node, DFS explores each branch of the graph to its fullest depth before moving to another branch, effectively exploring the graph via a stack-based approach, either through recursion or using an explicit stack. This method allows DFS to traverse all nodes in a path-focused manner, making it useful for situations that require thorough exploration like puzzle solving, scheduling problems, and cycle detection in graphs. DFS is also used in topological sorting and finding connected components in graphs. Its ability to dive deep into graph structures efficiently makes it a fundamental algorithm in both theoretical and applied computer science.

Functions of DFS:

• Path Finding:

DFS can be used to find a path between two nodes in a graph. It explores as far along each branch before backtracking, which helps in discovering paths.

• Detecting Cycle:

DFS can be used to detect cycles in a graph, which is valuable for applications that need to ensure there are no cycles, like prerequisite scheduling.

• Topological Sorting:

For directed acyclic graphs (DAGs), DFS can be used to perform a topological sort. This is useful for scheduling tasks, resolving dependencies, and more.

• Connected Components:

DFS can identify connected components in a graph. In an undirected graph, it can explore all nodes reachable from a given node, marking out the different disjoint parts of the graph.

• Solving Puzzles:

Many puzzle games, such as mazes, can be solved using DFS by exploring all possible positions until the goal state is reached.

• Graph Coloring Problems:

DFS is used in graph coloring problems where colors are assigned to vertices such that no two adjacent vertices share the same color.

• Finding Bridges in a Graph:

DFS can be employed to find all bridges in a graph. A bridge is an edge removing which increases the number of connected components.

• Strongly Connected Components:

In directed graphs, DFS is used to find strongly connected components (SCCs). SCCs are portions of the graph where every vertex is reachable from every other vertex in the same component.

Example of DFS:

This example demonstrates how DFS traverses a graph represented as an adjacency list.

import java.util.*;

public class Graph {

    private int numVertices; // Number of vertices in the graph

    private LinkedList<Integer>[] adjList; // Adjacency list for storing edges

    // Constructor

    public Graph(int vertices) {

        numVertices = vertices;

        adjList = new LinkedList[vertices];

        for (int i = 0; i < vertices; ++i) {

            adjList[i] = new LinkedList<>();

        }

    }

    // Function to add an edge into the graph

    void addEdge(int v, int w) {

        adjList[v].add(w); // Add w to v’s list.

    }

    // A function used by DFS

    void DFSUtil(int v, boolean visited[]) {

        // Mark the current node as visited and print it

        visited[v] = true;

        System.out.print(v + ” “);

        // Recur for all the vertices adjacent to this vertex

        Iterator<Integer> i = adjList[v].listIterator();

        while (i.hasNext()) {

            int n = i.next();

            if (!visited[n])

                DFSUtil(n, visited);

        }

    }

    // The function to do DFS traversal. It uses recursive DFSUtil()

    void DFS(int v) {

        // Mark all the vertices as not visited(set as false by default in java)

        boolean visited[] = new boolean[numVertices];

        // Call the recursive helper function to print DFS traversal

        DFSUtil(v, visited);

    }

    public static void main(String args[]) {

        Graph g = new Graph(4);

        g.addEdge(0, 1);

        g.addEdge(0, 2);

        g.addEdge(1, 2);

        g.addEdge(2, 0);

        g.addEdge(2, 3);

        g.addEdge(3, 3);

        System.out.println(“Depth First Traversal (starting from vertex 2):”);

        g.DFS(2);

    }

}

Explanation:

• Graph class contains a constructor to initialize the number of vertices and create an array of linked lists for the adjacency list.
• addEdge method adds directed edges to the graph.
• DFSUtil is a recursive function that marks the current node as visited and then recursively visits all its unvisited neighbors.
• DFS initializes a visited array to keep track of which vertices have been visited and starts the DFS traversal from a given vertex.
• In the main method, a Graph object is created, edges are added, and DFS is called from vertex 2. The output will be the order in which the vertices are visited.

Key differences between BFS and DFS

Key Similarities between BFS and DFS

• Purpose:

Both BFS and DFS are used for traversing or searching tree or graph data structures. They are foundational techniques for numerous algorithmic problems, including pathfinding and graph traversal operations.

• Applicability:

Both algorithms can be used on all types of graphs, including directed and undirected, weighted and unweighted. They are versatile for exploring different aspects of graph structures.

• Output:

Both BFS and DFS can be used to check for connectivity in a graph and determine whether a path exists between two nodes.

• Complexity:

The time complexity for both BFS and DFS in the context of an adjacency list representation of a graph is O(V + E), where V is the number of vertices and E is the number of edges. This is because each node and each vertex is explored in the worst case.

• Graph Representation:

Both algorithms can operate on various representations of graphs such as adjacency matrices, adjacency lists, or edge lists.

• Algorithmic Pattern:

Both are recursive in nature, although BFS uses a queue and iterative approach, while DFS uses a stack (which can be simulated through recursion).

• Use in Solutions:

Both BFS and DFS are used as building blocks in many complex algorithms and problems, including solving puzzles and games, finding components in a network, and scheduling problems.

• Vertex Exploration:

In both algorithms, each vertex is visited once and marked to prevent revisiting and causing infinite loops, especially in cyclic graphs.