Interview Cheat Sheets | Graph Cheat Sheet

December 24th, 2023

Introduction

This article will serve to further summarize the excellent overview of graphs from the tech interview handbook.

Overview

Graphs, fundamental in computer science, consist of nodes or vertices connected by edges. Trees, a type of graph, lack cycles and connect any two vertices with a single edge. Graphs model relationships between entities and can represent friendships, distances between locations, etc.

Graph Representations

Commonly encountered representations:

1. Adjacency matrix
2. Adjacency list
3. Hash table of hash tables

Time Complexity

For graphs with V vertices and E edges:

Interview Considerations

Things to Look Out for

• A tree-like diagram may be a graph allowing cycles; naive recursive solutions may fail.
• Accurate tracking of visited nodes is crucial to avoid infinite loops.

Corner Cases

• Empty graph
• Graph with one or two nodes
• Disconnected graphs
• Graph with cycles

Graph Search Algorithms

Commonly Used

• Breadth-first Search

  • A typescript implementation:

    class Graph {
      private vertices: number;
      private adjacencyList: Map<number, number[]>;
    
      constructor(vertices: number) {
        this.vertices = vertices;
        this.adjacencyList = new Map();
      }
    
      addEdge(vertex: number, neighbor: number) {
        if (!this.adjacencyList.has(vertex)) {
          this.adjacencyList.set(vertex, []);
        }
        this.adjacencyList.get(vertex)?.push(neighbor);
      }
    
      bfs(startingVertex: number) {
        const visited: boolean[] = Array(this.vertices).fill(false);
        const queue: number[] = [];
    
        visited[startingVertex] = true;
        queue.push(startingVertex);
    
        while (queue.length !== 0) {
          const currentVertex = queue.shift()!;
          console.log(currentVertex);
    
          const neighbors = this.adjacencyList.get(currentVertex);
          if (neighbors) {
            for (const neighbor of neighbors) {
              if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.push(neighbor);
              }
            }
          }
        }
      }
    }
    

• Depth-first Search

  • A typescript implementation:

    class Graph {
      private vertices: number;
      private adjacencyList: Map<number, number[]>;
    
      constructor(vertices: number) {
        this.vertices = vertices;
        this.adjacencyList = new Map();
      }
    
      addEdge(vertex: number, neighbor: number) {
        if (!this.adjacencyList.has(vertex)) {
          this.adjacencyList.set(vertex, []);
        }
        this.adjacencyList.get(vertex)?.push(neighbor);
      }
    
      dfs(startingVertex: number) {
        const visited: boolean[] = Array(this.vertices).fill(false);
        const stack: number[] = [];
    
        stack.push(startingVertex);
    
        while (stack.length !== 0) {
          const currentVertex = stack.pop() as number;
    
          if (!visited[currentVertex]) {
            visited[currentVertex] = true;
            console.log(currentVertex);
    
            const neighbors = this.adjacencyList.get(currentVertex);
            if (neighbors) {
              for (const neighbor of neighbors) {
                if (!visited[neighbor]) {
                  stack.push(neighbor);
                }
              }
            }
          }
        }
      }
    }
    

Uncommonly Used

• Topological Sort

  • A typescript implementation:

  class Graph {
    private vertices: number;
    private adjacencyList: Map<number, number[]>;
  
    constructor(vertices: number) {
      this.vertices = vertices;
      this.adjacencyList = new Map();
    }
  
    addEdge(vertex: number, neighbor: number) {
      if (!this.adjacencyList.has(vertex)) {
        this.adjacencyList.set(vertex, []);
      }
      this.adjacencyList.get(vertex)?.push(neighbor);
    }
  
    topologicalSort() {
      const stack: number[] = [];
      const visited: boolean[] = Array(this.vertices).fill(false);
  
      for (let i = 0; i < this.vertices; i++) {
        if (!visited[i]) {
          this.topologicalSortUtil(i, visited, stack);
        }
      }
  
      return stack.reverse();
    }
  
    private topologicalSortUtil(
      vertex: number,
      visited: boolean[],
      stack: number[]
    ) {
      visited[vertex] = true;
  
      const neighbors = this.adjacencyList.get(vertex);
      if (neighbors) {
        for (const neighbor of neighbors) {
          if (!visited[neighbor]) {
            this.topologicalSortUtil(neighbor, visited, stack);
          }
        }
      }
  
      stack.push(vertex);
    }
  }
  

• Dijkstra’s algorithm

Almost Never Used

• Bellman-Ford algorithm
• Floyd-Warshall algorithm
• Prim’s algorithm
• Kruskal’s algorithm

Depth-first Search (DFS)

The algorithm explores as far as possible along each branch before backtracking. Uses a stack (implicit or actual).

Breadth-first Search (BFS)

The algorithm explores all nodes at the present depth before moving to the next depth level. Utilizes a queue.

Topological Sorting

Linear ordering of vertices ensures that for every directed edge uv, u precedes v. Commonly used for scheduling jobs or tasks with dependencies.

Essential Questions for Practice

1. Number of Islands
2. Flood Fill - My solution
3. 01 Matrix - My solution

Recommended Practice Questions

Breadth-first Search

• Rotting Oranges - My solution

Either Search

• Clone Graph
• Pacific Atlantic Water Flow

Topological Sorting

• Course Schedule - My solution