Graph

Representation

In graph theory, there are several ways to represent a graph depending on the nature of the problem and the operations you need to perform. Here are some common graph representations and how they might be presented in a problem:

• Edge List

// Graph with vertices 1, 2, 3 and edges (1, 2), (2, 3), (3, 1)
let edges = [
  [1, 2],
  [2, 3],
  [3, 1],
];

• Adjacency List

// Graph representation
let adjList = {
  1: [2, 3],
  2: [1, 3],
  3: [1, 2],
};

• Adjacency Matrix

// Graph with 3 vertices
let adjMatrix = [
  [0, 1, 1], // Connections for vertex 1
  [1, 0, 1], // Connections for vertex 2
  [1, 1, 0], // Connections for vertex 3
];

• Incidence Matrix

let incidenceMatrix = [
  [1, 0, 1, 0], // Vertex 1
  [1, 1, 0, 1], // Vertex 2
  [0, 1, 1, 1], // Vertex 3
];

DFS - recursive

let fn = (graph) => {
  let dfs = (node) => {
    let ans = 0;
    // do some logic
    for (const neighbor of graph[node]) {
      if (!seen.has(neighbor)) {
        seen.add(neighbor);
        ans += dfs(neighbor);
      }
    }

    return ans;
  };

  let seen = new Set([START_NODE]);
  return dfs(START_NODE);
};

DFS - iterative

let fn = (graph) => {
  let stack = [START_NODE];
  let seen = new Set([START_NODE]);
  let ans = 0;

  while (stack.length) {
    let node = stack.pop();
    // do some logic
    for (const neighbor of graph[node]) {
      if (!seen.has(neighbor)) {
        seen.add(neighbor);
        stack.push(neighbor);
      }
    }
  }

  return ans;
};

Examples

Number of Provinces - Adjacency Matrix

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c. A province is a group of directly or indirectly connected cities and no other cities outside of the group. You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise. Return the total number of provinces.

var findCircleNum = function (isConnected) {
  let n = isConnected.length;
  let graph = new Map();

  for (let i = 0; i < n; i++) {
    graph.set(i, []);
  }

  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j]) {
        graph.get(i).push(j);
        graph.get(j).push(i);
      }
    }
  }

  let dfs = (node) => {
    for (const neighbor of graph.get(node)) {
      if (!seen.has(neighbor)) {
        seen.add(neighbor);
        dfs(neighbor);
      }
    }
  };

  let seen = new Set();
  let ans = 0;

  for (let i = 0; i < n; i++) {
    if (!seen.has(i)) {
      ans++;
      seen.add(i);
      dfs(i);
    }
  }

  return ans;
};

Number of Islands - Matrix

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function (grid) {
  let directions = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ]; // directions to move from the current cell
  let m = grid.length; // number of rows
  let n = grid[0].length; // number of columns
  let seen = []; // array to track visited cells

  let valid = (row, col) => {
    // checks if the cell is valid (within bounds and contains "1")
    return 0 <= row && row < m && 0 <= col && col < n && grid[row][col] == "1";
  };

  for (let i = 0; i < m; i++) {
    // create a matrix of false values to represent unvisited cells
    seen.push(new Array(n).fill(false));
  }

  let dfs = (row, col) => {
    // DFS to explore the entire island, marking all its parts as visited
    for (const [dx, dy] of directions) {
      // check each neighboring cell
      let nextRow = row + dy;
      let nextCol = col + dx;
      if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
        // if the cell is valid and not yet visited
        seen[nextRow][nextCol] = true; // mark it as visited
        dfs(nextRow, nextCol); // explore its neighbors
      }
    }
  };

  let ans = 0;
  for (let row = 0; row < m; row++) {
    for (let col = 0; col < n; col++) {
      if (grid[row][col] == "1" && !seen[row][col]) {
        // found the start of an island
        ans++; // increment the island count
        seen[row][col] = true; // mark the starting cell as visited
        dfs(row, col); // explore the entire island
      }
    }
  }

  return ans;
};

Reorder Routes to Make All Paths Lead to the City Zero - Edge List

There are n cities numbered from 0 to n - 1 and n - 1 roads such that there is only one way to travel between two different cities (this network form a tree). Last year, The ministry of transport decided to orient the roads in one direction because they are too narrow.
Roads are represented by connections where connections[i] = [ai, bi] represents a road from city ai to city bi.
This year, there will be a big event in the capital (city 0), and many people want to travel to this city.
Your task consists of reorienting some roads such that each city can visit the city 0. Return the minimum number of edges changed.
It's guaranteed that each city can reach city 0 after reorder.

/**
 * @param {number} n
 * @param {number[][]} connections
 * @return {number}
 */
var minReorder = function (n, connections) {
  let roads = new Set(); // set of roads that go from city 0 to its neighbors
  let graph = new Map(); // hash table with created nodes where each node is a key, and it has an array of its connections (incoming or outgoing)
  let seen = new Array(n).fill(false); // array to track visited and counted connections, necessary to ensure each connection is processed only once

  for (let i = 0; i < n; i++) {
    graph.set(i, []); // populate the graph with empty arrays for each node
  }

  let convertToHash = (row, col) => {
    return row + "," + col; // create a unique identifier for each road from city 0
  };

  for (const [x, y] of connections) {
    graph.get(x).push(y); // add connections in both directions (since the graph is undirected)
    graph.get(y).push(x);
    roads.add(convertToHash(x, y)); // add the road from city 0 to the set
  }

  let dfs = (node) => {
    // perform a DFS traversal of the tree
    let ans = 0;
    for (const neighbor of graph.get(node)) {
      // get the neighbors for each node (e.g., for node 0, get [1, 4])
      if (!seen[neighbor]) {
        // if this node has not been visited, visit it
        if (roads.has(convertToHash(node, neighbor))) {
          // if the road matches one in the set, it needs to be reordered
          ans++;
        }

        seen[neighbor] = true; // mark this node as seen
        ans += dfs(neighbor); // recursively call DFS on this neighbor node
      }
    }

    return ans;
  };

  seen[0] = true; // mark the first element (city 0) as seen
  return dfs(0); // start DFS from the first key in our connections map, as per the problem's requirement
};

Keys and Rooms - Adjacency List

var canVisitAllRooms = function (rooms) {
  let dfs = (node) => {
    for (const neighbor of rooms[node]) {
      // iterate through the array of keys in the current room
      if (!seen.has(neighbor)) {
        // if we haven't visited this room yet, we need to explore it
        seen.add(neighbor); // mark this room as visited by adding it to the 'seen' set
        dfs(neighbor); // recursively explore this room
      }
    }
  };

  let seen = new Set([0]); // initialize the 'seen' set with the first room (room 0) as visited
  dfs(0); // start the depth-first search from room 0
  return seen.size == rooms.length; // check if the number of visited rooms is equal to the total number of rooms
};

BFS

let fn = (graph) => {
  let queue = [START_NODE];
  let seen = new Set([START_NODE]);
  let ans = 0;

  while (queue.length) {
    let currentLength = queue.length;
    let nextQueue = [];

    for (let i = 0; i < currentLength; i++) {
      let node = queue[i];
      // do some logic
      for (const neighbor of graph[node]) {
        if (!seen.has(neighbor)) {
          seen.add(neighbor);
          nextQueue.push(neighbor);
        }
      }
    }

    queue = nextQueue;
  }

  return ans;
};

Examples

Shortest Path in Binary Matrix - Matrix

Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1.
A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
All the visited cells of the path are 0.
All the adjacent cells of the path are 8-directionally connected (i.e., they are different and they share an edge or a corner).
The length of a clear path is the number of visited cells of this path.

var shortestPathBinaryMatrix = function (grid) {
  // If the starting point (0,0) is blocked, there's no valid path, return -1
  if (grid[0][0] === 1) return -1;

  let steps = 0; // Initialize the number of steps taken to 0
  let n = grid.length; // Size of the grid (assumed to be n x n)
  let seen = []; // Array to track visited cells
  let directions = [
    // Possible 8 directions (right, down, down-right, up-left, etc.)
    [0, 1],
    [1, 0],
    [1, 1],
    [-1, -1],
    [-1, 1],
    [1, -1],
    [0, -1],
    [-1, 0],
  ];

  // Function to check if a cell is within bounds, unblocked (0), and not visited
  let valid = (row, col) => {
    return row >= 0 && row < n && col >= 0 && col < n && grid[row][col] === 0;
  };

  // Initialize the 'seen' matrix with 'false' indicating no cells have been visited yet
  for (let i = 0; i < n; i++) {
    seen.push(new Array(n).fill(false));
  }

  // Mark the starting cell (0,0) as visited
  seen[0][0] = true;
  let queue = [[0, 0]]; // Start BFS with the first cell (0,0)

  // While there are cells to process in the queue
  while (queue.length) {
    let currentLength = queue.length; // Number of cells at the current level of BFS
    let nextQueue = []; // Queue for the next level
    steps++; // Increment the step counter as we go deeper into the grid

    // Process all cells at the current BFS level
    for (let i = 0; i < currentLength; i++) {
      let [row, col] = queue[i]; // Get the current cell
      // If the current cell is the bottom-right corner, return the steps taken
      if (row === n - 1 && col === n - 1) {
        return steps;
      }

      // Check all 8 possible directions
      for (const [dx, dy] of directions) {
        let nextRow = row + dy;
        let nextCol = col + dx;
        // If the next cell is valid and not yet visited
        if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
          seen[nextRow][nextCol] = true; // Mark the cell as visited
          nextQueue.push([nextRow, nextCol]); // Add it to the queue for the next BFS level
        }
      }
    }

    // Move to the next level of BFS
    queue = nextQueue;
  }

  // If we exhaust all possibilities and don't reach the bottom-right corner, return -1
  return -1;
};

All Nodes Distance K in Binary Tree - convert binary tree to the graph

Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.
You can return the answer in any order.

var distanceK = function (root, target, k) {
  let queue = [target];
  let seen = new Set([target]);
  let distance = 0;

  let dfs = (node, parent) => {
    if (!node) {
      return;
    }

    node.parent = parent;
    dfs(node.left, node);
    dfs(node.right, node);
  };

  dfs(root, null);

  while (queue.length && distance < k) {
    let currentLength = queue.length;
    let nextQueue = [];

    for (let i = 0; i < currentLength; i++) {
      let node = queue[i];
      for (const neighbor of [node.left, node.right, node.parent]) {
        if (neighbor && !seen.has(neighbor)) {
          seen.add(neighbor);
          nextQueue.push(neighbor);
        }
      }
    }

    queue = nextQueue;
    distance++;
  }

  return queue.map((node) => node.val);
};