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 

2. Adjacency Matrix

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

1 

Comparison

Graph Traversals

Breadth-First Search (BFS)

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

1 

Depth-First Search (DFS)

Explores deeply first, better for finding cycles and paths.

1 

Graph Algorithms

Find Connected Components

1 

Detect Cycle (Undirected Graph)

1 

Detect Cycle (Directed Graph)

1 

Topological Sort

1 

Shortest Path (Unweighted - BFS)

1 

Examples

Example 1: Clone Graph

1 

Example 2: Course Schedule (Topological Sort)

1 

Example 3: Number of Islands (Connected Components)

1 

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

1 

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

1 

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