Definition
- 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
Mapwhere 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.
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)");
}
}
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).
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");
}
}
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).
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);
}
}
Expected output:
DFS from Mumbai (depth-first exploration):
Mumbai
Pune
Hyderabad
Bangalore
Chennai
Delhi
Kolkata
How is BFS different from DFS?
| Feature | BFS | DFS |
|---|---|---|
| Data structure | Queue (FIFO) | Stack / recursion |
| Exploration order | Level by level (breadth) | Branch by branch (depth) |
| Shortest path | Yes (unweighted graphs) | No |
| Space complexity | O(V) for queue at widest level | O(V) for recursion stack at deepest path |
| Cycle detection | Yes (check before enqueueing) | Yes (back edge detection) |
| Topological sort | Kahn's algorithm (BFS-based) | Reverse post-order (DFS-based) |
| Use case | Nearest branch, shortest hops | Cycle detection, connected components |
| Completeness | Finds closest first | May explore far before closer |
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.");
}
}
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
bank-graph-service/ ├── src/ │ └── main/ │ └── java/ │ └── com/ │ └── bank/ │ └── core/ │ ├── Edge.java │ ├── BranchGraph.java │ ├── FraudCycleDetector.java │ ├── DijkstraRouter.java │ └── BankGraphApp.java └── run.sh
Edge.java
package com.bank.core;
public record Edge(String target, int cost) {}
BranchGraph.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
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
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
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
javac -d out src/main/java/com/bank/core/*.java
java -cp out com.bank.core.BankGraphApp
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
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)");
}
}
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
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");
}
}
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.
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"));
}
}
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.
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");
}
}
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
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.
---