Definition
- Graph – a collection of vertices (nodes) and edges (connections between pairs of vertices) that models relationships between entities.
- Directed edge – a one-way relationship from a source vertex to a target vertex, like a payment flowing from sender to receiver.
- Undirected edge – a two-way relationship where both vertices can reach each other, like a joint bank account linking two holders.
- Weighted edge – an edge that carries a numeric value such as a transfer fee, distance, or latency.
- Adjacency list – the standard sparse representation where each vertex maps to the list of its neighbours; uses O(V + E) memory.
- Adjacency matrix – a V-by-V grid where cell (i, j) is true or holds the weight if an edge exists; uses O(V squared) memory but gives O(1) edge lookup.
Think of the money-transfer network at the National Bank of India. Each bank account is a vertex and every transfer between accounts is an edge. When Rajesh sends money to Priya, that is a directed edge from Rajesh to Priya because the money flows one way. If two accounts are linked as joint holders, that is an undirected edge because the relationship goes both ways. The entire web of accounts and transfers is a graph, and the transfer fee on each edge is the weight.
Understanding the Concepts
What is a graph?
A graph is a data structure that captures relationships between entities. The entities are called vertices or nodes, and the relationships are called edges. Every graph problem boils down to exploring, counting, or optimizing over these vertices and edges.
In the banking domain, the National Bank of India models its account network as a graph. Each account is a vertex, and every money transfer between two accounts is an edge. Rajesh, the developer, stores this graph so the fraud team can trace money flows and find suspicious cycles.
package com.bank.core;
import java.util.*;
public class AccountGraph {
private final Map<String, List<String>> adjacency = new HashMap<>();
public void addTransfer(String fromAccount, String toAccount) {
adjacency.computeIfAbsent(fromAccount, k -> new ArrayList<>()).add(toAccount);
}
public List<String> getNeighbours(String account) {
return adjacency.getOrDefault(account, Collections.emptyList());
}
}
Why do graphs exist and why do we need them?
Graphs exist because many real-world relationships cannot be captured by linear structures like arrays or trees. A tree has a single root and each node has one parent, but a bank transfer network has no single root and any account can send money to multiple accounts, which can in turn send money back. Graphs handle this generality.
Without graphs, the fraud team at National Bank of India would need to scan every transfer individually to find a cycle, which is expensive. With a graph, they build the adjacency structure once and run a cycle-detection algorithm that is linear in the number of vertices plus edges.
package com.bank.core;
import java.util.*;
public class WhyGraphsExist {
public static void main(String[] args) {
// Tree: one parent per node, no cycles
// Graph: any node can connect to any other node
AccountGraph graph = new AccountGraph();
graph.addTransfer("SAV2001", "CUR3001");
graph.addTransfer("CUR3001", "SAV4001");
graph.addTransfer("SAV4001", "SAV2001"); // cycle: money returns
System.out.println("Neighbours of SAV2001: " + graph.getNeighbours("SAV2001"));
// Output: Neighbours of SAV2001: [CUR3001]
}
}
How do you represent a graph in code?
The two standard representations are the adjacency list and the adjacency matrix. The adjacency list maps each vertex to a list of its neighbours and uses memory proportional to V + E, making it efficient for sparse graphs. The adjacency matrix is a V-by-V two-dimensional array where cell (i, j) holds true or the edge weight if an edge exists, giving O(1) edge lookup but using V-squared memory.
For the National Bank of India transfer network, which is sparse because most accounts do not transact with every other account, Rajesh uses an adjacency list.
package com.bank.core;
import java.util.*;
public class GraphRepresentations {
// Adjacency list: sparse, O(V + E) memory
static Map<Integer, List<Integer>> adjList = new HashMap<>();
// Adjacency matrix: dense, O(V^2) memory
static boolean[][] adjMatrix;
public static void main(String[] args) {
int vertices = 4;
adjMatrix = new boolean[vertices][vertices];
// Add directed edge 0 -> 1
adjList.computeIfAbsent(0, k -> new ArrayList<>()).add(1);
adjMatrix[0][1] = true;
// Add directed edge 1 -> 2
adjList.computeIfAbsent(1, k -> new ArrayList<>()).add(2);
adjMatrix[1][2] = true;
System.out.println("AdjList neighbours of 0: " + adjList.get(0));
System.out.println("AdjMatrix edge 0->1: " + adjMatrix[0][1]);
System.out.println("AdjMatrix edge 0->2: " + adjMatrix[0][2]);
}
}
AdjList neighbours of 0: [1]
AdjMatrix edge 0->1: true
AdjMatrix edge 0->2: false
How is a directed graph different from an undirected graph?
A directed graph has edges that go one way: from a source to a target. An undirected graph has edges that go both ways: adding an edge between A and B means A can reach B and B can reach A. In the adjacency list, a directed edge from u to v adds v to u's list only, while an undirected edge adds v to u's list and u to v's list.
| Feature | Directed | Undirected |
|---|---|---|
| Edge meaning | one-way relationship | two-way relationship |
| Adjacency list entry | add to source only | add to both endpoints |
| Cycle detection | three-colour DFS (white, grey, black) | parent tracking in DFS |
| Example | payment from sender to receiver | joint account linking two holders |
| Edge count for V nodes | up to V * (V - 1) | up to V * (V - 1) / 2 |
package com.bank.core;
import java.util.*;
public class DirectedVsUndirected {
static Map<String, List<String>> directed = new HashMap<>();
static Map<String, List<String>> undirected = new HashMap<>();
public static void main(String[] args) {
// Directed: Rajesh pays Priya
directed.computeIfAbsent("Rajesh", k -> new ArrayList<>()).add("Priya");
// Undirected: joint account
undirected.computeIfAbsent("Rajesh", k -> new ArrayList<>()).add("Priya");
undirected.computeIfAbsent("Priya", k -> new ArrayList<>()).add("Rajesh");
System.out.println("Directed from Rajesh: " + directed.get("Rajesh"));
System.out.println("Directed from Priya: " + directed.getOrDefault("Priya", List.of()));
System.out.println("Undirected from Rajesh: " + undirected.get("Rajesh"));
System.out.println("Undirected from Priya: " + undirected.get("Priya"));
}
}
Directed from Rajesh: [Priya]
Directed from Priya: []
Undirected from Rajesh: [Priya]
Undirected from Priya: [Rajesh]
What are weighted graphs and when do you use them?
A weighted graph attaches a numeric value to each edge. The weight can represent cost, distance, latency, or capacity. In the National Bank of India, the weight on a transfer edge is the transfer fee charged for that route. Finding the cheapest path from one account to another is a shortest-path problem solved by Dijkstra's algorithm.
package com.bank.core;
import java.math.BigDecimal;
import java.util.*;
public class WeightedGraph {
private final Map<String, List<Edge>> adjacency = new HashMap<>();
record Edge(String target, BigDecimal fee) {}
public void addTransferRoute(String from, String to, BigDecimal fee) {
adjacency.computeIfAbsent(from, k -> new ArrayList<>()).add(new Edge(to, fee));
}
public List<Edge> getRoutes(String account) {
return adjacency.getOrDefault(account, Collections.emptyList());
}
public static void main(String[] args) {
WeightedGraph graph = new WeightedGraph();
graph.addTransferRoute("SAV2001", "CUR3001", new BigDecimal("5.00"));
graph.addTransferRoute("SAV2001", "CUR4001", new BigDecimal("12.50"));
graph.addTransferRoute("CUR3001", "CUR4001", new BigDecimal("3.00"));
System.out.println("Routes from SAV2001:");
for (Edge e : graph.getRoutes("SAV2001")) {
System.out.println(" -> " + e.target() + " fee: " + e.fee());
}
}
}
Routes from SAV2001:
-> CUR3001 fee: 5.00
-> CUR4001 fee: 12.50
What are the key graph algorithms and when do you use each?
The four most important graph algorithms cover the majority of interview problems. BFS finds the shortest path in an unweighted graph and processes nodes level by level. DFS explores deeply first and is used for connected components, cycle detection, and topological sort. Dijkstra finds the cheapest weighted path. Union-Find groups vertices into connected components efficiently.
| Algorithm | Use case | Time complexity |
|---|---|---|
| BFS | shortest path (unweighted), level-order | O(V + E) |
| DFS | connected components, cycles, topological sort | O(V + E) |
| Dijkstra | shortest weighted path (no negative weights) | O((V + E) log V) |
| Union-Find | connected components, cycle detection | O(E * alpha(V)) near-constant |
package com.bank.core;
import java.util.*;
public class BFSShortestHops {
public static int shortestHops(Map<String, List<String>> graph,
String source, String target) {
if (source.equals(target)) return 0;
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.add(source);
visited.add(source);
int hops = 0;
while (!queue.isEmpty()) {
int size = queue.size();
hops++;
for (int i = 0; i < size; i++) {
String current = queue.poll();
for (String neighbour : graph.getOrDefault(current, List.of())) {
if (neighbour.equals(target)) return hops;
if (visited.add(neighbour)) {
queue.add(neighbour);
}
}
}
}
return -1; // unreachable
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("SAV2001", List.of("CUR3001", "CUR4001"));
graph.put("CUR3001", List.of("SAV5001"));
graph.put("CUR4001", List.of("SAV5001"));
System.out.println("Hops from SAV2001 to SAV5001: "
+ shortestHops(graph, "SAV2001", "SAV5001"));
}
}
Hops from SAV2001 to SAV5001: 2
What are common mistakes when working with graphs?
The most common mistake is forgetting to track visited nodes, which causes infinite loops in graphs with cycles. Another mistake is using DFS for shortest-path problems in unweighted graphs, where BFS is the correct choice. A third mistake is using an adjacency matrix for a sparse graph, wasting V-squared memory when V + E would suffice.
Wrong code that forgets visited tracking:
// WRONG: infinite loop on cyclic graph
public static void dfsWrong(Map<String, List<String>> graph, String node) {
System.out.println("Visiting: " + node);
for (String neighbour : graph.getOrDefault(node, List.of())) {
dfsWrong(graph, neighbour); // no visited check, loops forever
}
}
Correct code with visited tracking:
// CORRECT: visited set prevents revisiting
public static void dfsCorrect(Map<String, List<String>> graph,
String node, Set<String> visited) {
if (!visited.add(node)) return;
System.out.println("Visiting: " + node);
for (String neighbour : graph.getOrDefault(node, List.of())) {
dfsCorrect(graph, neighbour, visited);
}
}
What are edge cases in graph problems?
Edge cases include an empty graph with no vertices, a graph with a single vertex and no edges, a disconnected graph where some vertices have no path between them, and self-loops where a vertex has an edge to itself. In the banking domain, a self-loop means an account transferred money to itself, which is unusual but must not crash the system.
package com.bank.core;
import java.util.*;
public class GraphEdgeCases {
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
// Empty graph
System.out.println("Empty graph neighbours: "
+ graph.getOrDefault("SAV2001", List.of()));
// Self-loop
graph.computeIfAbsent("SAV2001", k -> new ArrayList<>()).add("SAV2001");
System.out.println("Self-loop neighbours: " + graph.get("SAV2001"));
// Disconnected: SAV2001 cannot reach CUR9999
graph.computeIfAbsent("CUR9999", k -> new ArrayList<>());
System.out.println("CUR9999 neighbours: " + graph.get("CUR9999"));
}
}
Empty graph neighbours: []
Self-loop neighbours: [SAV2001]
CUR9999 neighbours: []
How are graphs used in fraud detection at a bank?
The fraud team at National Bank of India uses graph algorithms to detect money laundering. A cycle in the transfer graph where money leaves an account and returns through a chain of intermediaries is a classic layering pattern. BFS finds the shortest hop count between two accounts, which reveals how close a suspect account is to a known bad actor. Connected components identify clusters of accounts that transact only with each other, which may indicate a mule network.
package com.bank.core;
import java.util.*;
public class FraudCycleDetector {
private final Map<String, List<String>> graph = new HashMap<>();
public void addTransfer(String from, String to) {
graph.computeIfAbsent(from, k -> new ArrayList<>()).add(to);
}
public boolean hasCycle() {
Set<String> visited = new HashSet<>();
Set<String> inStack = new HashSet<>();
for (String node : graph.keySet()) {
if (dfs(node, visited, inStack)) return true;
}
return false;
}
private boolean dfs(String node, Set<String> visited, Set<String> inStack) {
if (inStack.contains(node)) return true; // back edge: cycle
if (visited.contains(node)) return false;
visited.add(node);
inStack.add(node);
for (String neighbour : graph.getOrDefault(node, List.of())) {
if (dfs(neighbour, visited, inStack)) return true;
}
inStack.remove(node);
return false;
}
public static void main(String[] args) {
FraudCycleDetector detector = new FraudCycleDetector();
detector.addTransfer("SAV2001", "CUR3001");
detector.addTransfer("CUR3001", "SAV4001");
detector.addTransfer("SAV4001", "SAV2001"); // cycle
System.out.println("Cycle detected: " + detector.hasCycle());
}
}
Cycle detected: true
What should a senior engineer know about graphs?
A senior engineer should know how to choose the right representation based on graph density, how to pick the right algorithm for the problem type, and how to handle production concerns like large graphs that do not fit in memory. In production systems at National Bank of India, the transfer graph is stored in a graph database like Neo4j, and traversals are bounded to prevent runaway queries. The senior engineer also knows that recognising a problem as a graph problem is the hardest and most valuable skill, because many problems that look like string matching, scheduling, or network routing are graphs underneath.
package com.bank.core;
import java.util.*;
public class BoundedBFS {
// Production BFS with a hop limit to prevent runaway traversals
public static Set<String> reachableWithinHops(
Map<String, List<String>> graph, String source, int maxHops) {
Set<String> visited = new HashSet<>();
Queue<String> queue = new LinkedList<>();
queue.add(source);
visited.add(source);
int hops = 0;
while (!queue.isEmpty() && hops < maxHops) {
int size = queue.size();
hops++;
for (int i = 0; i < size; i++) {
String current = queue.poll();
for (String neighbour : graph.getOrDefault(current, List.of())) {
if (visited.add(neighbour)) {
queue.add(neighbour);
}
}
}
}
return visited;
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("SAV2001", List.of("CUR3001", "CUR4001"));
graph.put("CUR3001", List.of("SAV5001"));
graph.put("CUR4001", List.of("SAV6001", "SAV7001"));
Set<String> reachable = reachableWithinHops(graph, "SAV2001", 2);
System.out.println("Reachable within 2 hops: " + reachable);
}
}
Reachable within 2 hops: [SAV2001, CUR3001, CUR4001, SAV5001, SAV6001, SAV7001]
What are common interview follow-up questions?
Interviewers often ask these follow-up questions about graphs: How do you detect a cycle in a directed graph versus an undirected graph? What is the difference between BFS and DFS? When do you use Dijkstra versus Bellman-Ford? How do you handle negative edge weights? What is topological sort and when is it used? How do you find connected components? What is the difference between an adjacency list and an adjacency matrix?
Each of these follow-ups tests a specific aspect of graph understanding, and the candidate who connects them back to a coherent mental model of vertices, edges, and traversal strategies stands out.
package com.bank.core;
import java.util.*;
public class TopologicalSortExample {
// Kahn's algorithm: BFS-based topological sort for task ordering
public static List<String> topologicalSort(Map<String, List<String>> graph,
Map<String, Integer> inDegree) {
Queue<String> queue = new LinkedList<>();
for (var entry : inDegree.entrySet()) {
if (entry.getValue() == 0) queue.add(entry.getKey());
}
List<String> order = new ArrayList<>();
while (!queue.isEmpty()) {
String node = queue.poll();
order.add(node);
for (String neighbour : graph.getOrDefault(node, List.of())) {
inDegree.merge(neighbour, -1, Integer::sum);
if (inDegree.get(neighbour) == 0) queue.add(neighbour);
}
}
return order;
}
public static void main(String[] args) {
Map<String, List<String>> graph = new HashMap<>();
graph.put("KYC", List.of("AccountOpen"));
graph.put("AccountOpen", List.of("Deposit"));
graph.put("CreditCheck", List.of("AccountOpen"));
Map<String, Integer> inDegree = new HashMap<>();
inDegree.put("KYC", 0);
inDegree.put("CreditCheck", 0);
inDegree.put("AccountOpen", 2);
inDegree.put("Deposit", 1);
System.out.println("Task order: " + topologicalSort(graph, inDegree));
}
}
Task order: [KYC, CreditCheck, AccountOpen, Deposit]
Visual Overview
Graph Representations
Adjacency List (sparse) Adjacency Matrix (dense)
┌──────────┐ ┌───┬───┬───┬───┐
│ SAV2001 │─→ [CUR3001, CUR4001] │ │ 0 │ 1 │ 2 │
├──────────┤ ├───┼───┼───┼───┤
│ CUR3001 │─→ [SAV5001] │ 0 │ 0 │ 1 │ 0 │
├──────────┤ ├───┼───┼───┼───┤
│ CUR4001 │─→ [SAV5001] │ 1 │ 0 │ 0 │ 1 │
└──────────┘ ├───┼───┼───┼───┤
│ 2 │ 0 │ 0 │ 0 │
Memory: O(V + E) └───┴───┴───┴───┘
Memory: O(V^2)
Directed vs Undirected
Directed: Undirected:
Rajesh ──→ Priya Rajesh ←──→ Priya
(one-way payment) (joint account)
BFS vs DFS Traversal
BFS (level-order): DFS (depth-first):
┌───┐ ┌───┐
│ A │ Level 0 │ A │ Visit A
├───┤ └─┬─┘
│B C│ Level 1 │
├───┤ ┌─▼─┐
│D E│ Level 2 │ B │ Visit B
└───┘ └─┬─┘
│
┌─▼─┐
│ D │ Visit D (deep first)
└───┘
Key Takeaway
A graph is a collection of vertices connected by edges, and it is the most versatile data structure for modelling relationships. The two key distinctions are direction and weight. A directed edge represents a one-way relationship like a payment flowing from sender to receiver, while an undirected edge represents a mutual relationship like a joint account. Edges can carry weights such as transfer fees or distances, turning the graph into a cost network.
In code, the adjacency list is the go-to representation for sparse graphs because it uses memory proportional to the number of vertices plus edges. The adjacency matrix is better for dense graphs because it gives constant-time edge lookup, but it wastes V-squared memory when most pairs are not connected. At the National Bank of India, Rajesh uses an adjacency list for the transfer network because the graph is sparse: most accounts do not transact with every other account.
The power of graphs comes from the algorithms built on top of them. BFS gives the shortest path in terms of hops. DFS explores deeply and detects cycles. Dijkstra finds the cheapest weighted path. Union-Find groups vertices into connected components. The fraud team uses cycle detection to find money-laundering patterns where money leaves an account and returns through intermediaries, and BFS to measure how many hops separate a suspect account from a known bad actor.
The senior-level insight is that recognising a problem as a graph problem is the hardest and most valuable skill. Many problems that look like string matching, scheduling, or network routing are really graphs underneath. Once you see the vertices and edges, the entire toolbox of proven algorithms becomes available.
Remember one sentence: a graph is vertices connected by edges, directed or undirected, weighted or unweighted, and recognising that a problem is a graph problem unlocks BFS, DFS, Dijkstra, and Union-Find.
---