Graphs: Fundamentals, Operations & Complexity

Graphs

Why This Matters

Graphs model relationships between entities. A graph consists of vertices (nodes) and edges (connections). They're used to represent social networks (people and friendships), web pages (pages and links), road networks (cities and roads), and dependencies (tasks and prerequisites).

This matters because many real-world problems are graph problems. Finding the shortest path (GPS navigation), detecting cycles (deadlock detection), finding connected components (social network analysis), and topological sorting (build systems) all use graph algorithms.

In interviews, graph problems test your understanding of graph representations, traversal algorithms (BFS, DFS), and your ability to recognize when a problem is a graph problem. Many problems that seem complex become manageable when you model them as graphs.

What Engineers Usually Get Wrong

Most engineers think "graphs are just nodes and edges." While that's true, the real challenge is choosing the right representation (adjacency list vs matrix) and the right traversal (BFS vs DFS). Engineers often use adjacency matrices for sparse graphs (wasteful) or adjacency lists for dense graphs (slower lookups).

Engineers also confuse BFS and DFS. BFS finds shortest paths in unweighted graphs and explores level by level. DFS explores deeply first and is better for finding cycles or paths. Using the wrong traversal makes problems harder.

Another common mistake is not handling cycles. Graphs can have cycles, unlike trees. Forgetting to mark visited nodes causes infinite loops. Understanding when to use visited sets vs parent tracking is crucial.

How This Breaks Systems in the Real World

A social network was finding mutual friends using DFS. The graph had cycles (A is friends with B, B is friends with C, C is friends with A). The DFS didn't mark visited nodes, so it entered an infinite loop. The service hung. The fix? Use a visited set to prevent revisiting nodes. The lesson? Always mark visited nodes in graph traversals.

Another story: A build system was using DFS to resolve dependencies. It found a cycle (A depends on B, B depends on C, C depends on A). The DFS didn't detect the cycle, so it tried to build A, which needed B, which needed C, which needed A. The build system deadlocked. The fix? Use cycle detection (back edges in DFS) or topological sort (which fails if cycle exists).

Graph Fundamentals

Terminology

• Vertex (Node): Entity in the graph
• Edge: Connection between vertices
• Directed Graph: Edges have direction (A → B)
• Undirected Graph: Edges are bidirectional (A ↔ B)
• Weighted Graph: Edges have weights (distances, costs)
• Path: Sequence of vertices connected by edges
• Cycle: Path that starts and ends at same vertex
• Connected: Path exists between any two vertices (undirected)
• Strongly Connected: Path exists between any two vertices in both directions (directed)

Graph Types

Undirected:          Directed:           Weighted:
  A---B               A→B                 A--5--B
  |   |               ↓ ↑                 |     |
  C---D               C→D                3|     |2
                                      C--1--D

Graph Representations

1. Adjacency List

Each vertex stores list of neighbors.

1// For undirected graph
2class Graph {
3  private adjacencyList: Map<number, number[]> = new Map();
4
5  addVertex(vertex: number): void {
6    if (!this.adjacencyList.has(vertex)) {
7      this.adjacencyList.set(vertex, []);
8    }
9  }
10
11  addEdge(vertex1: number, vertex2:

2. Adjacency Matrix

2D array where matrix[i][j] indicates edge from i to j.

1class GraphMatrix {
2  private matrix: number[][];
3  private vertices: number;
4
5  constructor(vertices: number) {
6    this.vertices = vertices;
7    this.matrix = Array(vertices)
8      .fill(null)
9      .map(() => Array(vertices).fill(0));
10  }
11
12  addEdge(from:  to  weight

Comparison

Graph Traversals

Breadth-First Search (BFS)

Explores level by level, finds shortest paths in unweighted graphs.

1function BFS(graph: Map<number, number[]>, start: number): number[] {
2  const result: number[] = [];
3  const visited = new Set<number>();
4  const queue: number[] = [start];
5
6  visited.add(start);
7
8  while (queue.length > 0) {

Depth-First Search (DFS)

Explores deeply first, better for finding cycles and paths.

1// Recursive
2function DFSRecursive(
3  graph: Map<number, number[]>,
4  start: number
5): number[] {
6  const result: number[] = [];
7  const visited = new Set<number>();
8
9  function dfs(vertex: number): void {
10    visited.add(vertex);
11    result.push(vertex)

Graph Algorithms

Find Connected Components

1function connectedComponents(graph: Map<number, number[]>): number[][] {
2  const components: number[][] = [];
3  const visited = new Set<number>();
4
5  function dfs(vertex: number, component: number[]): void {
6    visited.add(vertex);
7    component.vertex

Detect Cycle (Undirected Graph)

1function hasCycleUndirected(graph: Map<number, number[]>): boolean {
2  const visited = new Set<number>();
3
4  function dfs(vertex: number, parent: number | null): boolean {
5    visited.add(vertex);
6
7    for (const neighbor of graph.get(vertex) || []) {
8      if (visitedneighbor

Detect Cycle (Directed Graph)

1function hasCycleDirected(graph: Map<number, number[]>): boolean {
2  const visited = new Set<number>();
3  const recStack = new Set<number>(); // Current recursion path
4
5  function dfs(vertex: number): boolean {
6    visited.add(vertex);
7    recStack.add(vertex);
8
9    for (const neighbor  graphvertex

Topological Sort

1function topologicalSort(graph: Map<number, number[]>): number[] {
2  const result: number[] = [];
3  const visited = new Set<number>();
4  const recStack = new Set<number>();
5
6  function dfs(vertex: number): boolean {
7    if (recStack.has(vertex)

Shortest Path (Unweighted - BFS)

1function shortestPath(
2  graph: Map<number, number[]>,
3  start: number,
4  end: number
5): number[] {
6  const queue: number[] = [start];
7  const visited = new Set<number>([start]);
8  const parent = new Map<number, number>();
9
10  while (queue.length

Examples

Example 1: Clone Graph

1class Node {
2  val: number;
3  neighbors: Node[] = [];
4  constructor(val: number) {
5    this.val = val;
6  }
7}
8
9function cloneGraph(node: Node | null): Node | null {
10  if (!node) return null;
11
12  const cloned = new Map<Node, Node>();
13
14  function dfsoriginal Node Node

Example 2: Course Schedule (Topological Sort)

1function canFinish(numCourses: number, prerequisites: number[][]): boolean {
2  const graph = new Map<number, number[]>();
3  const inDegree = new Array(numCourses).fill(0);
4
5  // Build graph and calculate in-degrees
6  for (const [course, prereq] of prerequisites) {
7    if (!graph.has(prereq)

Example 3: Number of Islands (Connected Components)

1function numIslands(grid: string[][]): number {
2  if (!grid || grid.length === 0) return 0;
3
4  const rows = grid.length;
5  const cols = grid[0].length;
6  let islands = 0;
7
8  function dfs(row: number, col: number): void {
9    if (
10      row < 0 || row >= rows ||

Common Pitfalls

• Not marking visited: Causes infinite loops in cycles
• Wrong traversal choice: BFS for shortest path, DFS for cycles/paths
• Wrong representation: Adjacency matrix for sparse graphs wastes space
• Not handling disconnected graphs: Need to check all components
• Cycle detection errors: Undirected (back edge to non-parent) vs Directed (back edge in recStack)
• Not reversing topological sort: DFS gives reverse order, need to reverse
• Memory issues: Large graphs can cause stack overflow (use iterative DFS)

Failure Stories You'll Recognize

The Infinite Loop: A social network used DFS to find mutual friends but didn't mark visited nodes. The graph had cycles, so DFS entered an infinite loop. The service hung. The fix? Always mark visited nodes in graph traversals.

The Build Deadlock: A build system used DFS for dependencies but didn't detect cycles. A circular dependency (A→B→C→A) caused the build to deadlock. The fix? Use cycle detection or topological sort (which fails if cycle exists).

The Wrong Representation: A service used an adjacency matrix for a sparse graph (millions of vertices, few edges). The matrix was huge but mostly empty. Memory usage was excessive. The fix? Use adjacency list for sparse graphs.

What Interviewers Are Really Testing

They want to see you choose the right representation and traversal. Junior engineers use the wrong traversal or don't handle cycles. Senior engineers understand when to use BFS vs DFS and handle edge cases correctly.

When they ask "find shortest path," they're testing:

• Do you recognize this is a graph problem?
• Do you use BFS (unweighted) or Dijkstra (weighted)?
• Do you handle cycles and disconnected graphs?

Interview Questions

Beginner

Q: What is the difference between BFS and DFS? When would you use each?

A:

BFS (Breadth-First Search):

• Explores level by level (uses queue)
• Finds shortest path in unweighted graphs
• Uses more memory (stores all nodes at current level)
• Use cases: Shortest path, level-order traversal, finding minimum steps

DFS (Depth-First Search):

• Explores deeply first (uses stack/recursion)
• Better for finding cycles, paths, connected components
• Uses less memory (only stores path from root to current)
• Use cases: Cycle detection, topological sort, finding paths, maze solving

Key Difference:

• BFS: Level by level, finds shortest path
• DFS: Deep exploration, finds any path

Example:

• Finding shortest path between two people in social network → BFS
• Checking if maze has path from start to end → DFS
• Finding cycles in dependency graph → DFS

Intermediate

Q: How do you detect a cycle in a directed graph?

A:

Approach: DFS with recursion stack

1function hasCycle(graph: Map<number, number[]>): boolean {
2  const visited = new Set<number>();
3  const recStack = new Set<number>(); // Current recursion path
4
5  function dfs(vertex: number): boolean {
6    visited.add(vertex);
7    recStack.add(vertex);
8
9    for (const neighbor of graphvertex

How it works:

• visited: Tracks all visited nodes (prevents revisiting)
• recStack: Tracks current recursion path (from root to current)
• Back edge to node in recStack = cycle (path back to ancestor)

For undirected graph: Back edge to non-parent indicates cycle.

Senior

Q: Design a system to find the shortest path between any two nodes in a weighted graph with millions of nodes. How would you optimize it?

A:

Challenge: Need efficient shortest path algorithm that scales.

Solution: Use Dijkstra's algorithm with optimizations

1class ShortestPathFinder {
2  private graph: Map<number, Array<[number, number]>>; // [neighbor, weight]
3
4  dijkstra(start: number, end: number): number {
5    const dist = new Map<number, number>();
6    const visited = new Set<number>();
7    const pq = new MinHeap<[number, number]

Optimizations for Scale:

1. Bidirectional Search: Run Dijkstra from both start and end, meet in middle

   • Reduces search space significantly
   • Time: O((V + E) log V) but explores fewer nodes

2. A Algorithm*: Use heuristic (e.g., Euclidean distance) to guide search

   • Faster for graphs with geographic structure
   • Time: O((V + E) log V) but explores fewer nodes

3. Contraction Hierarchies: Preprocess graph to create shortcuts

   • Trade preprocessing time for faster queries
   • Query time: O(log V) after preprocessing

4. Distributed Processing: Partition graph, run Dijkstra in parallel

   • For graphs too large for single machine
   • Use MapReduce or distributed graph processing

5. Caching: Cache common shortest paths

   • For repeated queries
   • Use LRU cache with TTL

Trade-offs:

• Dijkstra: Simple, works for all graphs, O((V + E) log V)
• Bidirectional: Faster but more complex
• A*: Fastest for geographic graphs, needs good heuristic
• Preprocessing: Slower first query, faster subsequent queries

• Graph: Vertices (nodes) and edges (connections). Models relationships
• Representations: Adjacency list (sparse graphs) vs Adjacency matrix (dense graphs, fast lookups)
• BFS: Level-by-level, finds shortest path in unweighted graphs, uses queue
• DFS: Deep exploration, finds cycles/paths, uses stack/recursion
• Cycle Detection: Undirected (back edge to non-parent), Directed (back edge in recStack)
• Topological Sort: Ordering where all edges point forward. Fails if cycle exists
• Shortest Path: BFS for unweighted, Dijkstra for weighted
• Connected Components: Use DFS to find all components in disconnected graph
• Time Complexity: Most graph algorithms are O(V + E)
• Edge Cases: Empty graph, single vertex, cycles, disconnected graph, self-loops

How InterviewCrafted Will Teach This

We'll teach graphs through relationship modeling problems, not abstract definitions. Instead of memorizing "a graph has vertices and edges," you'll learn through scenarios like "how do you find the shortest path?" or "how do you detect cycles in dependencies?"

You'll see how graphs are used in real systems (social networks, routing, build systems) and understand when to use BFS vs DFS. When an interviewer asks "find shortest path," you'll think "BFS for unweighted, Dijkstra for weighted"—not just "traverse the graph."

• Trees - Trees are a special type of graph (acyclic, connected). Understanding trees helps with graph traversal algorithms.
• Hash Tables - Used to implement adjacency lists efficiently and track visited nodes in graph algorithms.
• Stacks and Queues - Stacks are used for DFS (iterative), queues for BFS. Understanding these structures is essential for graph traversal.
• Recursion & Backtracking - Many graph algorithms (DFS, path finding) are naturally recursive. Understanding recursion helps implement graph algorithms.
• Disjoint Set (Union-Find) - Used for finding connected components and detecting cycles in graphs. Essential for graph connectivity problems.