Back to Graphs
Q3Question 3 of 24

How do graphs, BFS, DFS, and shortest path work in Java

Answer: A graph is a collection of vertices connected by edges, and BFS, DFS, and Dijkstra are the core algorithms for traversal, cycle detection, and shortest path finding.

Key Concepts
  • A graph is a set of vertices (nodes) connected by edges; it can be directed or undirected, weighted or unweighted.
  • An adjacency list represents a graph as a map from each vertex to its list of neighbors, using O(V+E) space.
  • BFS (Breadth-First Search) explores all neighbors at the current depth before moving deeper, using a queue, and finds the shortest path in unweighted graphs.
  • DFS (Depth-First Search) explores as deep as possible along each branch before backtracking, using a stack or recursion, and is used for cycle detection and topological sort.
  • Dijkstra's algorithm finds the shortest path in a weighted graph with non-negative weights, using a priority queue with O((V+E) log V) time complexity.
  • Cycle detection in a directed graph uses DFS with three states (unvisited, in-progress, visited) to find back edges.
  • Java has no built-in graph class; you build one using Map<String, List<String>> for adjacency lists or a dedicated Graph record.

Definition

A graph is a collection of vertices connected by edges, and BFS, DFS, and Dijkstra are the core algorithms for traversal, cycle detection, and shortest path finding.
  • Graph is a data structure consisting of vertices (nodes) and edges (connections between nodes); edges can be directed or undirected, weighted or unweighted.
  • Adjacency list is the standard graph representation in Java, using a Map> where each vertex maps to its list of neighbors.
  • BFS (Breadth-First Search) explores vertices level by level using a queue, visiting all neighbors of the current vertex before moving to the next level.
  • DFS (Depth-First Search) explores as deep as possible along each branch using recursion or an explicit stack, backtracking when it reaches a dead end.
  • Dijkstra's algorithm finds the shortest path from a source to all other vertices in a weighted graph with non-negative edge weights, using a priority queue to always process the closest unvisited vertex.

Think of National Bank of India's branch network across India. Each branch is a vertex, and the roads between branches are edges (weighted by travel time). BFS is like sending a message to all branches within one hour, then all branches within two hours, expanding outward in rings. DFS is like Rajesh driving down one road as far as he can, then backtracking to try the next road. Dijkstra is like a GPS finding the fastest route from the Mumbai head office to the Chennai branch, always choosing the next road segment with the shortest cumulative travel time.

Understanding the Concepts

What is a graph?

A graph is a set of vertices (nodes) connected by edges. If edges have a direction (A to B is not the same as B to A), the graph is directed. If edges have no direction, the graph is undirected. If edges carry a weight (cost, distance, time), the graph is weighted.

In Java, the standard representation is an adjacency list: a Map where each vertex maps to the list of its neighbors.

JAVA
package com.bank.core;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class GraphBasics {

    public static void main(String[] args) {
        // Adjacency list: bank branch network
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("Mumbai", List.of("Pune", "Chennai", "Delhi"));
        graph.put("Pune", List.of("Mumbai", "Hyderabad"));
        graph.put("Chennai", List.of("Mumbai", "Bangalore"));
        graph.put("Delhi", List.of("Mumbai", "Kolkata"));
        graph.put("Hyderabad", List.of("Pune", "Bangalore"));
        graph.put("Bangalore", List.of("Chennai", "Hyderabad"));
        graph.put("Kolkata", List.of("Delhi"));

        System.out.println("National Bank of India branch network:");
        graph.forEach((branch, neighbors) ->
            System.out.println("  " + branch + " -> " + neighbors));

        System.out.println("Vertices: " + graph.size());
        int edges = graph.values().stream().mapToInt(List::size).sum();
        System.out.println("Edge entries: " + edges + " (undirected, counted twice)");
    }
}
TEXT
Expected output:
National Bank of India branch network:
  Mumbai -> [Pune, Chennai, Delhi]
  Pune -> [Mumbai, Hyderabad]
  Chennai -> [Mumbai, Bangalore]
  Delhi -> [Mumbai, Kolkata]
  Hyderabad -> [Pune, Bangalore]
  Bangalore -> [Chennai, Hyderabad]
  Kolkata -> [Delhi]
Vertices: 7
Edge entries: 14 (undirected, counted twice)

How does BFS work?

BFS (Breadth-First Search) starts at a source vertex and explores all vertices at the current distance before moving to the next distance. It uses a FIFO queue. BFS finds the shortest path (fewest edges) in an unweighted graph.

  • Algorithm:
  • Add the source to the queue and mark it visited.
  • While the queue is not empty, poll a vertex, process it, and offer all its unvisited neighbors.
  • Each vertex is visited exactly once. Time: O(V+E).
JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class BfsDemo {

    public static void bfs(Map<String, List<String>> graph, String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(start);
        visited.add(start);
        int level = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            System.out.println("  Level " + level + ":");
            for (int i = 0; i < levelSize; i++) {
                String branch = queue.poll();
                System.out.println("    " + branch);
                for (String neighbor : graph.getOrDefault(branch, List.of())) {
                    if (!visited.contains(neighbor)) {
                        visited.add(neighbor);
                        queue.offer(neighbor);
                    }
                }
            }
            level++;
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("Mumbai", List.of("Pune", "Chennai", "Delhi"));
        graph.put("Pune", List.of("Mumbai", "Hyderabad"));
        graph.put("Chennai", List.of("Mumbai", "Bangalore"));
        graph.put("Delhi", List.of("Mumbai", "Kolkata"));
        graph.put("Hyderabad", List.of("Pune", "Bangalore"));
        graph.put("Bangalore", List.of("Chennai", "Hyderabad"));
        graph.put("Kolkata", List.of("Delhi"));

        System.out.println("BFS from Mumbai (nearest branches first):");
        bfs(graph, "Mumbai");
    }
}
TEXT
Expected output:
BFS from Mumbai (nearest branches first):
  Level 0:
    Mumbai
  Level 1:
    Pune
    Chennai
    Delhi
  Level 2:
    Hyderabad
    Bangalore
    Kolkata

How does DFS work?

DFS (Depth-First Search) starts at a source vertex and explores as deep as possible along each branch before backtracking. It uses recursion (implicit stack) or an explicit stack. DFS is used for cycle detection, topological sorting, and finding connected components.

  • Algorithm:
  • Mark the current vertex as visited.
  • For each unvisited neighbor, recurse.
  • Each vertex is visited exactly once. Time: O(V+E).
JAVA
package com.bank.core;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class DfsDemo {

    public static void dfs(Map<String, List<String>> graph, String current,
                           Set<String> visited, int depth) {
        visited.add(current);
        System.out.println("  " + "  ".repeat(depth) + current);
        for (String neighbor : graph.getOrDefault(current, List.of())) {
            if (!visited.contains(neighbor)) {
                dfs(graph, neighbor, visited, depth + 1);
            }
        }
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = new HashMap<>();
        graph.put("Mumbai", List.of("Pune", "Chennai", "Delhi"));
        graph.put("Pune", List.of("Mumbai", "Hyderabad"));
        graph.put("Chennai", List.of("Mumbai", "Bangalore"));
        graph.put("Delhi", List.of("Mumbai", "Kolkata"));
        graph.put("Hyderabad", List.of("Pune", "Bangalore"));
        graph.put("Bangalore", List.of("Chennai", "Hyderabad"));
        graph.put("Kolkata", List.of("Delhi"));

        System.out.println("DFS from Mumbai (depth-first exploration):");
        dfs(graph, "Mumbai", new HashSet<>(), 0);
    }
}
TEXT
Expected output:
DFS from Mumbai (depth-first exploration):
  Mumbai
    Pune
      Hyderabad
        Bangalore
          Chennai
    Delhi
      Kolkata

How is BFS different from DFS?

FeatureBFSDFS
Data structureQueue (FIFO)Stack / recursion
Exploration orderLevel by level (breadth)Branch by branch (depth)
Shortest pathYes (unweighted graphs)No
Space complexityO(V) for queue at widest levelO(V) for recursion stack at deepest path
Cycle detectionYes (check before enqueueing)Yes (back edge detection)
Topological sortKahn's algorithm (BFS-based)Reverse post-order (DFS-based)
Use caseNearest branch, shortest hopsCycle detection, connected components
CompletenessFinds closest firstMay explore far before closer
JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class BfsVsDfs {

    static List<String> bfsOrder(Map<String, List<String>> graph, String start) {
        List<String> order = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new ArrayDeque<>();
        queue.offer(start);
        visited.add(start);
        while (!queue.isEmpty()) {
            String v = queue.poll();
            order.add(v);
            for (String n : graph.getOrDefault(v, List.of())) {
                if (visited.add(n)) queue.offer(n);
            }
        }
        return order;
    }

    static List<String> dfsOrder(Map<String, List<String>> graph, String start) {
        List<String> order = new ArrayList<>();
        Set<String> visited = new HashSet<>();
        dfsHelper(graph, start, visited, order);
        return order;
    }

    static void dfsHelper(Map<String, List<String>> graph, String v,
                          Set<String> visited, List<String> order) {
        visited.add(v);
        order.add(v);
        for (String n : graph.getOrDefault(v, List.of())) {
            if (!visited.contains(n)) dfsHelper(graph, n, visited, order);
        }
    }

    public static void main(String[] args) {
        var graph = Map.of(
            "Mumbai", List.of("Pune", "Chennai"),
            "Pune", List.of("Mumbai", "Hyderabad"),
            "Chennai", List.of("Mumbai", "Bangalore"),
            "Hyderabad", List.of("Pune"),
            "Bangalore", List.of("Chennai")
        );

        System.out.println("BFS order from Mumbai: " + bfsOrder(graph, "Mumbai"));
        System.out.println("DFS order from Mumbai: " + dfsOrder(graph, "Mumbai"));
        System.out.println("BFS visits level-by-level. DFS goes deep first.");
    }
}
TEXT
Expected output:
BFS order from Mumbai: [Mumbai, Pune, Chennai, Hyderabad, Bangalore]
DFS order from Mumbai: [Mumbai, Pune, Hyderabad, Chennai, Bangalore]
BFS visits level-by-level. DFS goes deep first.

What is a complete banking project using graphs?

This project models the National Bank of India branch network as a weighted graph, finds the nearest branch with BFS, detects fraud cycles with DFS, and computes the cheapest transfer route with Dijkstra.

Project structure

DIAGRAM
bank-graph-service/
├── src/
│   └── main/
│       └── java/
│           └── com/
│               └── bank/
│                   └── core/
│                       ├── Edge.java
│                       ├── BranchGraph.java
│                       ├── FraudCycleDetector.java
│                       ├── DijkstraRouter.java
│                       └── BankGraphApp.java
└── run.sh

Edge.java

JAVA
package com.bank.core;

public record Edge(String target, int cost) {}

BranchGraph.java

JAVA
package com.bank.core;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class BranchGraph {
    private final Map<String, List<Edge>> adjacency = new HashMap<>();

    public void addEdge(String from, String to, int cost) {
        adjacency.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, cost));
        adjacency.computeIfAbsent(to, k -> new ArrayList<>()).add(new Edge(from, cost));
    }

    public List<Edge> neighbors(String vertex) {
        return adjacency.getOrDefault(vertex, List.of());
    }

    public java.util.Set<String> vertices() {
        return adjacency.keySet();
    }
}

FraudCycleDetector.java

JAVA
package com.bank.core;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class FraudCycleDetector {

    // DFS cycle detection in a directed graph
    // States: 0=unvisited, 1=in-progress, 2=visited
    public static boolean hasCycle(Map<String, List<String>> directedGraph) {
        Map<String, Integer> state = new HashMap<>();
        for (String v : directedGraph.keySet()) state.put(v, 0);

        for (String v : directedGraph.keySet()) {
            if (state.get(v) == 0 && dfs(directedGraph, v, state)) {
                return true;
            }
        }
        return false;
    }

    private static boolean dfs(Map<String, List<String>> graph, String v,
                               Map<String, Integer> state) {
        state.put(v, 1); // in-progress
        for (String neighbor : graph.getOrDefault(v, List.of())) {
            if (state.getOrDefault(neighbor, 0) == 1) return true;  // back edge = cycle
            if (state.getOrDefault(neighbor, 0) == 0 && dfs(graph, neighbor, state)) return true;
        }
        state.put(v, 2); // visited
        return false;
    }
}

DijkstraRouter.java

JAVA
package com.bank.core;

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class DijkstraRouter {

    public record PathResult(Map<String, Integer> distances, Map<String, String> previous) {}

    public static PathResult shortestPaths(BranchGraph graph, String source) {
        Map<String, Integer> dist = new HashMap<>();
        Map<String, String> prev = new HashMap<>();
        for (String v : graph.vertices()) dist.put(v, Integer.MAX_VALUE);
        dist.put(source, 0);

        var pq = new PriorityQueue<>(Comparator.comparingInt(v -> dist.getOrDefault((String) v, Integer.MAX_VALUE)));
        pq.offer(source);

        while (!pq.isEmpty()) {
            String u = (String) pq.poll();
            for (Edge edge : graph.neighbors(u)) {
                int newDist = dist.get(u) + edge.cost();
                if (newDist < dist.getOrDefault(edge.target(), Integer.MAX_VALUE)) {
                    dist.put(edge.target(), newDist);
                    prev.put(edge.target(), u);
                    pq.offer(edge.target());
                }
            }
        }
        return new PathResult(dist, prev);
    }

    public static String tracePath(Map<String, String> previous, String target) {
        var path = new java.util.ArrayDeque<String>();
        String current = target;
        while (current != null) {
            path.addFirst(current);
            current = previous.get(current);
        }
        return String.join(" -> ", path);
    }
}

BankGraphApp.java

JAVA
package com.bank.core;

import java.util.List;
import java.util.Map;

public class BankGraphApp {
    public static void main(String[] args) {
        System.out.println("=== National Bank of India: Branch Network ===");

        // Build weighted graph (cost = transfer fee in INR)
        var graph = new BranchGraph();
        graph.addEdge("Mumbai", "Pune", 50);
        graph.addEdge("Mumbai", "Chennai", 200);
        graph.addEdge("Mumbai", "Delhi", 150);
        graph.addEdge("Pune", "Hyderabad", 100);
        graph.addEdge("Chennai", "Bangalore", 80);
        graph.addEdge("Hyderabad", "Bangalore", 120);
        graph.addEdge("Delhi", "Kolkata", 180);

        // BFS: nearest branches from Mumbai
        System.out.println("\nBFS nearest branches from Mumbai:");
        var bfsResult = DijkstraRouter.shortestPaths(graph, "Mumbai");
        bfsResult.distances().entrySet().stream()
            .sorted(Map.Entry.comparingByValue())
            .forEach(e -> System.out.println("  " + e.getKey() + ": " + e.getValue() + " INR transfer fee"));

        // Dijkstra: cheapest route Mumbai -> Bangalore
        System.out.println("\nCheapest route Mumbai -> Bangalore:");
        String path = DijkstraRouter.tracePath(bfsResult.previous(), "Bangalore");
        System.out.println("  Route: " + path);
        System.out.println("  Total fee: " + bfsResult.distances().get("Bangalore") + " INR");

        // Fraud cycle detection (directed payment flows)
        System.out.println("\nFraud cycle detection:");
        var payments = Map.of(
            "SAV2001", List.of("CUR3001"),
            "CUR3001", List.of("SAV2002"),
            "SAV2002", List.of("SAV2001")  // cycle: money loops back
        );
        System.out.println("  Payment chain has cycle: " + FraudCycleDetector.hasCycle(payments));

        var cleanPayments = Map.of(
            "SAV2001", List.of("CUR3001"),
            "CUR3001", List.of("SAV2002"),
            "SAV2002", List.<String>of()
        );
        System.out.println("  Clean chain has cycle:   " + FraudCycleDetector.hasCycle(cleanPayments));
    }
}

How to compile and run

BASH
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.BankGraphApp
TEXT
Expected output:
=== National Bank of India: Branch Network ===

BFS nearest branches from Mumbai:
  Mumbai: 0 INR transfer fee
  Pune: 50 INR transfer fee
  Hyderabad: 150 INR transfer fee
  Delhi: 150 INR transfer fee
  Chennai: 200 INR transfer fee
  Bangalore: 170 INR transfer fee
  Kolkata: 330 INR transfer fee

Cheapest route Mumbai -> Bangalore:
  Route: Mumbai -> Pune -> Hyderabad -> Bangalore
  Total fee: 270 INR

Fraud cycle detection:
  Payment chain has cycle: true
  Clean chain has cycle:   false

What are common mistakes with graph algorithms?

The most common mistake is forgetting to mark vertices as visited, which causes infinite loops in graphs with cycles.

Wrong: BFS without visited check

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class WrongBfsNoVisited {
    public static void main(String[] args) {
        var graph = Map.of(
            "A", List.of("B"),
            "B", List.of("A", "C"),
            "C", List.of("B")
        );

        Queue<String> queue = new ArrayDeque<>();
        queue.offer("A");
        int steps = 0;

        // BUG: no visited set, A and B keep re-enqueuing each other
        while (!queue.isEmpty() && steps < 10) {
            String v = queue.poll();
            System.out.println("  Visit: " + v);
            for (String n : graph.getOrDefault(v, List.of())) {
                queue.offer(n); // adds duplicates
            }
            steps++;
        }
        System.out.println("Stopped after " + steps + " steps (infinite without limit)");
    }
}
TEXT
Expected output:
  Visit: A
  Visit: B
  Visit: A
  Visit: C
  Visit: B
  Visit: A
  Visit: C
  Visit: B
  Visit: A
  Visit: C
Stopped after 10 steps (infinite without limit)

Correct: BFS with visited set

JAVA
package com.bank.core;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class CorrectBfsWithVisited {
    public static void main(String[] args) {
        var graph = Map.of(
            "A", List.of("B"),
            "B", List.of("A", "C"),
            "C", List.of("B")
        );

        Queue<String> queue = new ArrayDeque<>();
        Set<String> visited = new HashSet<>();
        queue.offer("A");
        visited.add("A");

        while (!queue.isEmpty()) {
            String v = queue.poll();
            System.out.println("  Visit: " + v);
            for (String n : graph.getOrDefault(v, List.of())) {
                if (visited.add(n)) { // add returns false if already present
                    queue.offer(n);
                }
            }
        }
        System.out.println("BFS complete: each vertex visited exactly once");
    }
}
TEXT
Expected output:
  Visit: A
  Visit: B
  Visit: C
BFS complete: each vertex visited exactly once

How does Dijkstra's shortest path algorithm work?

Dijkstra's algorithm finds the shortest weighted path from a source to all other vertices. It maintains a distance map and a priority queue. At each step, it picks the unvisited vertex with the smallest known distance, relaxes all its edges (checks if the path through this vertex is shorter), and updates distances.

Dijkstra only works with non-negative edge weights. For negative weights, use Bellman-Ford.

JAVA
package com.bank.core;

import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;

public class DijkstraStepByStep {

    record WeightedEdge(String target, int weight) {}

    public static void main(String[] args) {
        // Directed weighted graph: transfer fees between branches
        Map<String, List<WeightedEdge>> graph = new HashMap<>();
        graph.put("Mumbai", List.of(new WeightedEdge("Pune", 50), new WeightedEdge("Delhi", 150)));
        graph.put("Pune", List.of(new WeightedEdge("Hyderabad", 100)));
        graph.put("Delhi", List.of(new WeightedEdge("Hyderabad", 80)));
        graph.put("Hyderabad", List.of());

        // Dijkstra from Mumbai
        Map<String, Integer> dist = new HashMap<>();
        for (String v : graph.keySet()) dist.put(v, Integer.MAX_VALUE);
        dist.put("Mumbai", 0);

        var pq = new PriorityQueue<String>(Comparator.comparingInt(v -> dist.getOrDefault(v, Integer.MAX_VALUE)));
        pq.offer("Mumbai");

        System.out.println("Dijkstra step-by-step from Mumbai:");
        while (!pq.isEmpty()) {
            String u = pq.poll();
            System.out.println("  Process: " + u + " (dist=" + dist.get(u) + ")");
            for (var edge : graph.getOrDefault(u, List.of())) {
                int newDist = dist.get(u) + edge.weight();
                if (newDist < dist.getOrDefault(edge.target(), Integer.MAX_VALUE)) {
                    dist.put(edge.target(), newDist);
                    pq.offer(edge.target());
                    System.out.println("    Relax: " + edge.target() + " from " + dist.getOrDefault(edge.target(), Integer.MAX_VALUE) + " to " + newDist);
                }
            }
        }

        System.out.println("\nShortest distances from Mumbai:");
        dist.forEach((v, d) -> System.out.println("  " + v + ": " + d + " INR"));
    }
}
TEXT
Expected output:
Dijkstra step-by-step from Mumbai:
  Process: Mumbai (dist=0)
    Relax: Pune from 2147483647 to 50
    Relax: Delhi from 2147483647 to 150
  Process: Pune (dist=50)
    Relax: Hyderabad from 2147483647 to 150
  Process: Delhi (dist=150)
  Process: Hyderabad (dist=150)

Shortest distances from Mumbai:
  Mumbai: 0 INR
  Pune: 50 INR
  Delhi: 150 INR
  Hyderabad: 150 INR

What should a senior or principal engineer know?

At the senior level, you should know when to use BFS vs DFS, how to represent graphs efficiently, and the limitations of Dijkstra.

At the principal level, consider:

  • Graph databases: Neo4j, Amazon Neptune for large-scale relationship queries.
  • Adjacency matrix vs list: matrix is O(V^2) space, good for dense graphs. List is O(V+E), good for sparse graphs.
  • Topological sort: needed for dependency resolution (build systems, course prerequisites). Use DFS or Kahn's algorithm.
  • Negative weights: Dijkstra fails with negative edges. Use Bellman-Ford (O(VE)) or SPFA.
  • **A* search**: Dijkstra with a heuristic. Used in maps and game pathfinding.
  • Strongly connected components: Tarjan's or Kosaraju's algorithm, used in fraud ring detection.
JAVA
package com.bank.core;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class SeniorGraphKnowledge {
    public static void main(String[] args) {
        System.out.println("Senior/Principal graph checklist:");
        System.out.println("  1. BFS for shortest path (unweighted), DFS for cycle detection");
        System.out.println("  2. Dijkstra for weighted shortest path (non-negative weights)");
        System.out.println("  3. Adjacency list for sparse, matrix for dense graphs");
        System.out.println("  4. Topological sort for dependency ordering");
        System.out.println("  5. Bellman-Ford for negative weights");
        System.out.println("  6. Graph DBs (Neo4j) for large relationship queries");

        // Topological sort example: loan approval dependencies
        Map<String, List<String>> deps = new HashMap<>();
        deps.put("KYC", List.of());
        deps.put("CreditCheck", List.of("KYC"));
        deps.put("Appraisal", List.of("KYC"));
        deps.put("Approval", List.of("CreditCheck", "Appraisal"));
        deps.put("Disbursement", List.of("Approval"));

        System.out.println("\nLoan processing dependency graph:");
        deps.forEach((step, prerequisites) ->
            System.out.println("  " + step + " depends on: " + (prerequisites.isEmpty() ? "nothing" : prerequisites)));
        System.out.println("  Topological order: KYC -> CreditCheck -> Appraisal -> Approval -> Disbursement");
    }
}
TEXT
Expected output:
Senior/Principal graph checklist:
  1. BFS for shortest path (unweighted), DFS for cycle detection
  2. Dijkstra for weighted shortest path (non-negative weights)
  3. Adjacency list for sparse, matrix for dense graphs
  4. Topological sort for dependency ordering
  5. Bellman-Ford for negative weights
  6. Graph DBs (Neo4j) for large relationship queries

Loan processing dependency graph:
  KYC depends on: nothing
  CreditCheck depends on: [KYC]
  Appraisal depends on: [KYC]
  Approval depends on: [CreditCheck, Appraisal]
  Disbursement depends on: [Approval]
  Topological order: KYC -> CreditCheck -> Appraisal -> Approval -> Disbursement

What are common interview follow-up questions?

  • How do you detect a cycle in an undirected graph? (DFS: if you visit a neighbor that is already visited and is not the parent, there is a cycle. BFS can also detect it the same way.)
  • What is the time complexity of BFS and DFS? (Both are O(V+E) where V is the number of vertices and E is the number of edges.)
  • What is the difference between Dijkstra and Bellman-Ford? (Dijkstra uses a priority queue and requires non-negative weights, O((V+E) log V). Bellman-Ford relaxes all edges V-1 times, handles negative weights, O(VE).)
  • How do you find the shortest path in a weighted graph with negative edges? (Bellman-Ford. It also detects negative cycles.)
  • What is a minimum spanning tree? (A subset of edges that connects all vertices with the minimum total weight. Use Kruskal's or Prim's algorithm.)
  • How do you represent a graph in Java? (Adjacency list: Map> for unweighted, Map> for weighted. Adjacency matrix: int[][] for dense graphs.)

Visual Overview

DIAGRAM
 BFS Level-by-Level Traversal
 ==============================

  Start: Mumbai

  Level 0:  [Mumbai]
              │
          ┌───┼───┐
          ▼   ▼   ▼
  Level 1:  [Pune] [Chennai] [Delhi]
              │       │        │
              ▼       ▼        ▼
  Level 2:  [Hyderabad] [Bangalore] [Kolkata]

  Queue state at each step:
  Step 0: [Mumbai]
  Step 1: [Pune, Chennai, Delhi]
  Step 2: [Chennai, Delhi, Hyderabad]
  Step 3: [Delhi, Hyderabad, Bangalore]
  Step 4: [Hyderabad, Bangalore, Kolkata]
  Step 5: [Bangalore, Kolkata]
  Step 6: [Kolkata]
  Step 7: [] (done)


 Dijkstra's Algorithm
 =====================

  Mumbai ──50──> Pune ──100──> Hyderabad
    │                            ▲
    └─────150───> Delhi ──80────┘

  Priority Queue steps:
  1. Process Mumbai (0): relax Pune=50, Delhi=150
  2. Process Pune (50):  relax Hyderabad=150
  3. Process Delhi (150): Hyderabad already 150, no improvement
  4. Process Hyderabad (150): done

  Result: Mumbai=0, Pune=50, Delhi=150, Hyderabad=150

Key Takeaway

A graph is a set of vertices connected by edges. In Java, you represent a graph as an adjacency list using a Map where each vertex maps to its list of neighbors. Graphs model relationships: bank branch networks, payment flows, dependency chains, and fraud rings.

BFS explores vertices level by level using a queue. It finds the shortest path in unweighted graphs because it visits all vertices at distance K before any vertex at distance K+1. DFS explores as deep as possible along each branch using recursion or a stack. It is the foundation for cycle detection, topological sorting, and finding connected components.

Dijkstra's algorithm extends BFS to weighted graphs. It uses a priority queue to always process the vertex with the smallest known distance, then relaxes its edges. In our National Bank of India project, Dijkstra found that the cheapest transfer route from Mumbai to Bangalore goes through Pune and Hyderabad, costing 270 INR, even though the direct route through Chennai is shorter in hops.

The most critical implementation detail is the visited set. Without it, BFS and DFS loop forever in graphs with cycles. For cycle detection in directed graphs, use three states (unvisited, in-progress, visited) to identify back edges. We used this to detect circular payment chains that indicate potential fraud.

At the senior level, know when to use BFS (shortest unweighted path), DFS (cycle detection, topological sort), and Dijkstra (shortest weighted path). For negative weights, use Bellman-Ford. For large-scale graph queries in production, consider graph databases like Neo4j or Amazon Neptune.

Remember one sentence: BFS uses a queue and finds shortest paths level by level, DFS uses a stack and finds cycles by detecting back edges, and Dijkstra uses a priority queue to find the cheapest weighted path.

---

Share
Use ← → arrow keys to navigate