Mastering Graph Algorithms: BFS, DFS, Dijkstra, Floyd-Warshall, and Bellman-Ford in Java

Chapter 1: Breadth-First Search (BFS) in Java

Breadth-First Search (BFS) is a graph traversal algorithm used to explore nodes and edges of a graph systematically. It starts from a source node, explores all its neighbors first, and then proceeds to their unvisited neighbors — effectively exploring the graph level by level.

BFS uses a queue data structure to maintain the order of nodes to be visited. Once a node is visited, it is marked so that it isn't visited again. This ensures that BFS does not get stuck in a loop in cyclic graphs.

In undirected graphs, BFS can be used to find connected components or to check if a graph is bipartite. In directed graphs, it can be used to determine reachability from a given node. It works well for unweighted graphs when you need to find the shortest path from the source to all other nodes.

2. BFS Coding (with 2 Examples)

a. Syllabus-Oriented Example (Graph Traversal)

import java.util.*;

public class BFSExample {

    public static void bfs(int start, List<List<Integer>> graph) {

        boolean[] visited = new boolean[graph.size()];

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

        visited[start] = true;

        queue.offer(start);

        while (!queue.isEmpty()) {

            int node = queue.poll();

            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {

                if (!visited[neighbor]) {

                    visited[neighbor] = true;

                    queue.offer(neighbor);

                }

            }

        }

    }

    public static void main(String[] args) {

        int V = 5;

        List<List<Integer>> graph = new ArrayList<>();

        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());

        // Creating a sample graph

        graph.get(0).add(1);

        graph.get(0).add(2);

        graph.get(1).add(3);

        graph.get(2).add(4);

        bfs(0, graph);  // Output: 0 1 2 3 4

    }

}

b. Real-World Example (Shortest path in social network)

import java.util.*;

public class SocialNetworkBFS {

    public static int shortestConnection(String source, String target, Map<String, List<String>> network) {

        Set<String> visited = new HashSet<>();

        Queue<String> queue = new LinkedList<>();

        Map<String, Integer> distance = new HashMap<>();

        queue.offer(source);

        visited.add(source);

        distance.put(source, 0);

        while (!queue.isEmpty()) {

            String person = queue.poll();

            if (person.equals(target)) return distance.get(person);

            for (String friend : network.getOrDefault(person, new ArrayList<>())) {

                if (!visited.contains(friend)) {

                    visited.add(friend);

                    distance.put(friend, distance.get(person) + 1);

                    queue.offer(friend);

                }

            }

        }

        return -1;  // Not connected

    }

    public static void main(String[] args) {

        Map<String, List<String>> network = new HashMap<>();

        network.put("Alice", Arrays.asList("Bob", "Carol"));

        network.put("Bob", Arrays.asList("Dave"));

        network.put("Carol", Arrays.asList("Eve"));

        network.put("Dave", Arrays.asList("Frank"));

        System.out.println("Shortest path: " + shortestConnection("Alice", "Frank", network));  // Output: 3

    }

}

3. Pros of BFS

• ✅ Guarantees the shortest path in unweighted graphs.
• ✅ Easy to implement using queues and adjacency lists.
• ✅ Works well for level-order traversal in trees and graphs.
• ✅ Can detect cycles in undirected graphs.
• ✅ Can be modified to find connected components, bipartiteness, and more.

4. Cons of BFS

• ❌ Consumes a lot of memory in wide graphs due to queue size.
• ❌ Not suitable for graphs with weighted edges.
• ❌ Can be slower than DFS in deep but narrow graphs.
• ❌ Needs extra space for visited arrays and queues.
• ❌ Cannot detect back edges or perform topological sorting directly.

5. How Is BFS Better Than Other Traversal Techniques?

• Compared to DFS: BFS guarantees shortest paths in unweighted graphs, which DFS doesn’t.
• Compared to Dijkstra: BFS is faster and simpler for unweighted graphs; Dijkstra is overkill in such cases.
• Compared to Bellman-Ford/Floyd-Warshall: BFS is significantly less complex and better suited for basic reachability or path-finding in simple graphs.

6. Best-Case Scenarios to Use BFS

• Finding the shortest path in unweighted graphs.
• Crawling websites where breadth-first logic is preferred.
• Searching in a maze or grid-based game.
• Exploring social networks (e.g., mutual friend recommendations).
• Level-order traversal of a binary tree.

7. Applications of BFS

• GPS systems for route planning (if graph is unweighted).
• Social networks to find degrees of separation.
• Peer-to-peer network discovery (like torrent clients).
• AI in games for exploring all reachable states.
• Finding connected components in a graph.

8. Worst-Case Scenarios to Use BFS

• Graphs with millions of nodes and high branching factors — memory usage can explode.
• Weighted graphs — it will give incorrect results for shortest paths.
• Situations where depth-first exploration is required (e.g., backtracking problems like Sudoku).
• If the target node is deep and isolated, BFS wastes time visiting all levels before it.
• When graph structure requires cycle detection in directed graphs — DFS is better suited.