Open in app

Sign in

Write

Sign in

Graph theory algorithms

Dilip Kumar
35 min readMay 28, 2024

--

Graph traversal algorithm

There are many ways and techniques to traverse the graph. Sometimes we traverse all the nodes, sometimes all the edges, sometimes from A to B, etc. Let’s go through each type of traversal algorithm.

All paths from source to target

The goal is to find all the possible paths from source to target. It could be on a directed or undirected graph.

All paths from source to target on directed acyclic graph

https://leetcode.com/problems/all-paths-from-source-to-target/

Following is one example of traversing a path from node 0 to n-1 on a directed acyclic path.

Approach

  1. For each node x we have choices to explore all the neighbors.
  2. If we choose one path and keep traversing the path then if this will reach to target node then we will capture this path to answer.
  3. Since this is a DAG therefore we don’t need to worry about the cycle. Therefore no need to maintain the visited node.
  4. Since we need to capture the local path, therefore we need to pass path[] to every recursion which will be updated for each neighbor.
  5. Before we pick the next neighbor, we need to clean up path[] i.e. remove the last added neighbor.

Following is the code to implement it.

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function (graph) {
    const n = graph.length;
    const ans = [];
    const recursion = (node, path) => {
        if (node === n - 1) {
            // Add into answer
            ans.push([...path]);
            return;
        }
        for (const neighbor of graph[node]) {
            path.push(neighbor);
            recursion(neighbor, path);
            path.pop(); // undo it to cleanup path for next neighbor traversal
        }
    }
    recursion(0, [0]);
    return ans;
};

Time complexity

  1. With just two nodes start and target then we only have one path.
  2. If we add a third node then now we will have two paths, one the old and the second via the newly added node.
  3. With the newly-added node, new paths could be created by preceding all previous paths with the newly-added node

4. It means for the previous i node, if we had x paths then after adding one more node, we will have x + x = 2xpath i.e. f(i)= 2* f(i-1).

5. So total path would be T=f(2) + f(3) + .....+f(n) = 1 + 2 + 2^2 + 2 ^3 +…….+2^(n-2) = 2^(n-1) + 1.

6. If O(N) is an effort to build each path then the total time complexity would be O(N*2^N)

All paths from source to target on an undirected graph

  1. With an undirected graph, we might have a cycle.
  2. To avoid visiting the same node, we need to also maintain visited array
  3. Mark the node as visited at the beginning of the recursion. If the node is already visited then don’t traverse it as a neighbor.
  4. At the end of the recursion, we undo the visited array for the same node.

Following is the code to find all possible paths.

/**
 * @param {number[][]} graph
 * @return {number[][]}
 */
var allPathsSourceTarget = function (graph) {
    const n = graph.length;
    const ans = [];
    const visited = new Array(n).fill(false);

    const recursion = (node, path) => {
        // Mark node as visited
        visited[node] = true;
        if (node === n - 1) {
            // Add into answer
            ans.push([...path]);
            return;
        }
        for (const neighbor of graph[node]) {
            if(!visited[neighbor]) {
              path.push(neighbor);
              recursion(neighbor, path);
              path.pop(); // undo it to cleanup path for next neighbor traversal
            } 
       }
      // Undo marking node as visited
      visited[node] = false;
    }
    recursion(0, [0]);
    return ans;
};

The least value of all max values in the paths

https://leetcode.com/problems/swim-in-rising-water/

We need to find out the least value of all the path max weights. Though this problem can be solved optimally using Dijkstra, but for learning let’s use all possible path approaches to solve it as a brute force.

  1. For each path, track the maximum weight of each path.
  2. Keep global ans and keep updating for local ans.
  3. Since we might have a cycle, therefore need to keep the visited array.

The following will be the code that will throw TLE.

const bruteForce = grid => {
    const m = grid.length;
    const n = grid[0].length;
    const visited = new Array(m).fill(0).map(a => new Array(n).fill(false));
    const getNeighbors = (i, j) => {
        const dir = [[-1, 0], [1, 0], [0, 1], [0, -1]];
        const ans = [];
        for (const [p, q] of dir) {
            const x = p + i;
            const y = q + j;
            if (x >= 0 && x < m && y >= 0 && y < n) {
                ans.push([x, y]);
            }
        }
        return ans;
    }
    let ans = Number.MAX_SAFE_INTEGER;
    const rec = (i, j, local) => {
        visited[i][j] = true;
        const new_max = Math.max(local, grid[i][j]);

        // Ans area, when reach to the end
        if (i === m - 1 && j === n - 1) {
            // update ans
            ans = Math.min(new_max, ans);
            visited[i][j] = false;
            return;
        }
        // All chocies
        for (const [x, y] of getNeighbors(i, j)) {
            // if already visit
            if (!visited[x][y]) {
                rec(x, y, new_max);
            }
        }
        // backtrack
        visited[i][j] = false;
    }
    rec(0, 0, Number.MIN_SAFE_INTEGER);
    return ans;
}

Cycle Detection

Cycle detection also works differently on directed vs undirected graphs. Two goals.

  1. Detect cycle
  2. Print Cycle

Directed graph and cycle detection using arrival/departure time

  1. Every time explore a node, set the arrival time.
  2. Every time exit from node, set the departure time.

This gives three types of edges.

Back edge (after visited, departure time will not be set)
Cross edge (after visited, departure time will be set)
Forward edge (before visited, departure time will be set)

Following is code to implement it.


const cycleCheck =  (graph) => {
  const n = graph.length;
  const visited = new Array(n).fill(false);
  const arrival = new Array(n).fill(0);
  const departure = new Array(n).fill(0);
  let timestamp = 0;
  const dfs = u => { // Return true if cycle
    visited[u] = true;
    arrival[u]= ++timestamp;
    for (const v of graph[u]) {
      if(!visited[v]) {
        if(dfs(v)) {
          return true;
        }
      } else { // possibility of cycle, if back edge
        if(!departure[v]) {
            return true;
        }
      }
    }
    departure[u] = ++timestamp;
    return false;
  }
  for (let u=0; u < n; u++) {
      if(!visited[u]) {
        if(dfs(u)) {
          return true;
        }
      }
  }
  
}

Directed graph and cycle detection using UNVISITED/EXPLORED/VISITED state

  1. Running DFS on a connected/disconnected graph generates a DFS spanning tree/forest, respectively.
  2. With the help of one more vertex state: EXPLORED (that means visited but not yet completed) on top of VISITED (visited and completed), we can use this DFS spanning tree/forest to classify graph edges into three types:

Tree edge:

This is an edge that is part of DFS spanning tree. We can detect this when DFS moves from vertex u currently with state: EXPLORED
to another vertex v with state: UNVISITED.

Back/Bidirectional edge:

We can detect this when DFS moves from vertex u currently with state: EXPLORED to another vertex v with state: EXPLORED too, which implies that vertex v is an ancestor of vertex u in the DFS spanning tree. This detects the cycle.

Forward/Cross edges

We can detect this when DFS moves from vertex u currently with state: EXPLORED to another vertex v with state: VISITED.

Following is code to implement this algorithm.

// 1: UNVISITED, 2: EXPLORED, 3: VISITED
const visited = new Array(n).fill(1); // Initialize as UNVISITED
const dfs = node => {
  visited[node]= 2; // Mark as EXPLORED
  for (const neighbor of graph[node]) {
    if(visited[neighbor] == 1) { // Tree edge 1 means not yet explored
      if(dfs(neighbor)){
        return true;
      }
    } else if ( visited[neighbor] == 2) { // back edge on EXPLORED
        // This detects the cycle
        return true;
    } else if ( visited[neighbor] == 3) { // forward/cross edge on VISITED
      // No action
    }
  }
  visited[node]= 3;
  return false;
}

for (let i=0; i < n; i++) {
  if(visited[i] == 1) { // Launc dfs if node is UNVISITED
    if(dfs(i)){
      console.log("Cycle is found");
    }
  }
}

Print Cycle

To print the cycle, we need to maintain the parent relationship and once the cycle is detected, run the loop to traverse the parent until the cycle node is found and ever the result. Following is the updated code.

// 1: UNVISITED, 2: EXPLORED, 3: VISITED
const visited = new Array(n).fill(1); // Initialize as UNVISITED
const parent = new Array(n).fill(-1);
const cycle = [];
const dfs = node => {
  visited[node]= 2;
  for (const neighbor of graph[node]) {
    if(visited[neighbor] == 1) { // Tree edge 1 means not yet visited
      parent[neighbor] = node; // Update parent relationship
      if(dfs(neighbor)){
        return true;
      }
    } else if ( visited[neighbor] == 2) { // back edge
        // This detects the cycle, let's print it.
        let temp = node;
        cycle.length = 0; // empty cycle array for clean slate
        while(temp != neighbor) { // here neighbor is cycle node
          cycle.push(temp);
          temp = parent[temp];
        }
        cycle.push(neighbor); 
        // reverse the order
        cycle.reverse();
        // Print the cycle
        console.log({cycle});
        return true;
    } else if ( colors[neighbor] == 3) { // forward/cross edge
      // No action
    }
  }
  visited[node]= 3;
  return false;
}

for (let i=0; i < n; i++) {
  if(colors[i] == 1) {
    if(dfs(i)){
      console.log("Cycle is found");
    }
  }
}

How to find if a node is part of the cycle?

  1. One approach is to keep running while loop on parent to collect all the nodes part of a cycle. But this will lead to very high time complexity.
  2. There is an alternate approach to decrementing the starting node as 1 and on finding back edge then increment it as 1 .
  3. After that apply the prefix sum, sum with 0 will not be part of the cycle.
  4. To apply the prefix sum, you need to calculate prefixOrder
  5. Then apply countCycle[parent[node]]+= countCycle[node] to calculate the prefix sum for each node in prefixOrder.

Following is the updated code to find if node is part of a cycle or not.

// 1: UNVISITED, 2: EXPLORED, 3: VISITED
const visited = new Array(n).fill(1); // Initialize as UNVISITED
const parent = new Array(n).fill(-1);
const cycle = [];
const countCycle = new Array(n).fill(0);
const reverse = [];
const dfs = node => { // Return true if cycle
  visited[node]= 2;
  for (const neighbor of graph[node]) {
    if(visited[neighbor] == 1) { // Tree edge 1 means not yet visited
      parent[neighbor] = node; // Update parent relationship
      if(dfs(neighbor)){
        return true;
      }
    } else if ( visited[neighbor] == 2) { // back edge
        // To find if node is part of cycle or not
        countCycle[node]++;
        countCycle[parent[neighbor]]--; // 0 -1 0 0 1 (cycle 2->3->4->2)
        return true;
    } else if ( visited[neighbor] == 3) { // forward/cross edge
      // No action
    }
  }
  visited[node]= 3;
  // To find if node is part of cycle or not
  reverse.push(node);
  return false;
}

for (let i=0; i < n; i++) {
  if(visited[i] == 1) {
    if(dfs(i)){
      console.log("Cycle is found");
    }
  }
// To find if node is part of cycle or not, 
// update countCycle to calculate prefix sum as per reverse order
for (const node of reverse){
  countCycle[parent[node]]+= countCycle[node];
}
// Count the number of nodes part of the some cycle
let nodesInCycle = 0;
for (const count of countOfCycle) {
  if(count > 0) {
    nodesInCycle++;
  }
}
console.log({nodesInCycle});
}

Undirected graph and cycle detection using DFS Graph

  1. Since u->v & v->u therefore there is no concept of cross edges with an undirected graph.
  2. Since parent[neighbor]==node can be a possibility once node is visited therefore need to ignore it.

Following is the updated code for cycle detection in an undirected graph.

// 1: UNVISITED, 2: EXPLORED, 3: VISITED
const visited = new Array(n).fill(1); // Initialize as UNVISITED
const parent = new Array(n).fill(-1);
const dfs = node => {
  visited[node]= 2;
  for (const neighbor of graph[node]) {
    if(parent[node] == neighbor) { // Only this check is required for undirected graph
      continue; 
    }
    if(visited[neighbor] == 1) { // Tree edge 1 means not yet visited
      if(dfs(neighbor)){
        return true;
      }
    } else if ( visited[neighbor] == 2) { // back edge
        // This detects the cycle
        return true;
    }
  }
  visited[node]= 3;
  return false;
}

for (let i=0; i < n; i++) {
  if(visited[i] == 1) {
    if(dfs(i)){
      console.log("Cycle is found");
    }
  }
}

827. Making A Large Island

https://leetcode.com/problems/making-a-large-island/description

You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.

Return the size of the largest island in grid after applying this operation.

An island is a 4-directionally connected group of 1s.

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 3
Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.

Approach

  1. Run DFS to color each connected components and track the size as well.
  2. To try each edges of 0 i.e. converting 0 to 1 , first we find out the list of connected components it touches then sum up to find out the new components size.
  3. Use color starting with 2 and modify the same grid . This will help to use the same grid to identify the visited node.

Following is code for reference.

const getNeighbors = (grid, [i, j]) => {
    const m = grid.length;
    const n = grid[0].length;
    const ans = [];
    const dirs = [[1, 0], [-1, 0], [0, -1], [0, 1]];
    for (const [p, q] of dirs) {
        const x = i + p;
        const y = j + q;
        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]) {
            ans.push([x, y]);
        }
    }
    return ans;
}

const dfsColoring = (grid, [i, j], color) => {
    // update color for node
    grid[i][j] = color;
    let size = 1;
    for (const [x, y] of getNeighbors(grid, [i, j])) {
        if (grid[x][y] === 1) { // 1 means not yet visited
            size += dfsColoring(grid, [x, y], color);
        }
    }
    return size;
}
/**
 * @param {number[][]} grid
 * @return {number}
 */
var largestIsland = function (grid) {
    const m = grid.length;
    const n = grid[0].length;

    let color = 2;
    const componentSize = new Map();
    // Modify grid cell value to color and use it to track visited node as well
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) { // Not visited, launch dfs
                componentSize.set(color, dfsColoring(grid, [i, j], color++));
            }
        }
    }
    let ans = Math.max(...Array.from(componentSize.values()));
    // Now check with converting 0 to 1
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 0) {
                const components = new Set();
                for (const [x, y] of getNeighbors(grid, [i, j])) {
                    components.add(grid[x][y]); // Use updated color
                }
                // Get new count
                let local = 1;
                for (const color of components) {
                    local += componentSize.get(color);
                }
                // Update global
                ans = Math.max(ans, local);
            }
        }
    }
    return ans;
}

721. Accounts Merge

Given a list of accounts where each element accounts[i] is a list of strings, where the first element accounts[i][0] is a name, and the rest of the elements are emails representing emails of the account.

Now, we would like to merge these accounts. Two accounts definitely belong to the same person if there is some common email to both accounts. Note that even if two accounts have the same name, they may belong to different people as people could have the same name. A person can have any number of accounts initially, but all of their accounts definitely have the same name.

After merging the accounts, return the accounts in the following format: the first element of each account is the name, and the rest of the elements are emails in sorted order. The accounts themselves can be returned in any order.

Example 1:

Input: accounts = [["John","johnsmith@mail.com","john_newyork@mail.com"],["John","johnsmith@mail.com","john00@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Output: [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],["Mary","mary@mail.com"],["John","johnnybravo@mail.com"]]
Explanation:
The first and second John's are the same person as they have the common email "johnsmith@mail.com".
The third John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'], 
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.

Approach

  1. We will represent emails as nodes.
  2. An edge will signify that two emails are connected and hence belong to the same person.

Q. How to calculate edges?

Ans. We have two options.

Option#1: Build edge between every pair of account’s email.

For example [“Name”,”email#1”,”email#2”,"email#3","email#4"] ,we can build edge between every pair of these four emails. This will make O(n*n) edges. This will create a complete subgraph.

Option#2: Connect first email to rest only

As long as two emails are connected by a path of edges, we know they belong to the same account.

We can create an acyclic graph using only K−1 edges required to connect K nodes.

Then run the dfs/bfs to find out the connected components. Following is code for reference.

const buildGraph = accounts => {
    const graph = new Map();
    for (const [name, ...emails] of accounts) {
        const firstEmail = emails[0];
        for (const email of emails) {
            if (!graph.has(email)) {
                graph.set(email, []);
            }
            // Skip the firstEmail
            if (email === firstEmail) {
                continue;
            }
            graph.get(email).push(firstEmail);
            graph.get(firstEmail).push(email);
        }
    }
    return graph;
}
const buildEmailToName = accounts => {
    const emailToName = new Map();
    for (const [name, ...emails] of accounts) {
        for (const email of emails) {
            emailToName.set(email, name); // email to name 
        }
    }
    return emailToName;
}

const dfs = (graph, visited, node, component) => {
    visited.add(node);
    component.push(node);
    for (const neighbor of graph.get(node)) {
        if (!visited.has(neighbor)) {
            dfs(graph, visited, neighbor, component);
        }
    }
}

/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */
var accountsMerge = function (accounts) {
    const graph = buildGraph(accounts);
    const emailToName = buildEmailToName(accounts);
    const visited = new Set();
    const ans = [];
    for (const [email] of graph) {
        // launch dfs if node is not yet visited
        if (!visited.has(email)) {
            const component = [];
            dfs(graph, visited, email, component);
            // sort emails
            component.sort();
            // Add name in the begining
            component.unshift(emailToName.get(email));
            ans.push(component);
        }
    }
    return ans;
};

301. Remove Invalid Parentheses

Given a string s that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.

Return a list of unique strings that are valid with the minimum number of removals. You may return the answer in any order.

Example 1:

Input: s = "()())()"
Output: ["(())()","()()()"]

Approach: Use bfs to implement the minimum removal of invalid parenthesis with help of level order traversal

  1. Goal is to removal minimal of invalid parenthesis to make string valid
  2. We can apply bfs level order traversal.
  3. Input string will act as starting node.
  4. Neighbor of node will be calculated by removing each char one by one.
  5. If at any level, we found the valid parenthesis then include it in answer and return.
  6. It means, it will not do next level processing if previous level found the answer.

Following is code for reference.

const isValid = s => {
    let counter = 0;
    for (const chr of s) {
        if (chr === '(') {
            counter++;
        }
        if (chr === ')') {
            counter--;
        }
        if (counter < 0) {
            return false;
        }
    }
    return counter === 0;
}
const getNeighbors = (s) => {
    const neighbors = [];
    for (let i = 0; i < s.length; i++) {
        const option = s.substring(0, i) + s.substring(i + 1);
        neighbors.push(option);
    }
    return neighbors;
}

/**
 * @param {string} s
 * @return {string[]}
 */
var removeInvalidParentheses = function (s) {
    const queue = [s];
    const ans = [];
    const visited = new Map();
    while (queue.length > 0) {
        const n = queue.length;
        let found = false;
        for (let i = 0; i < n; i++) {
            const node = queue.shift();
            const valid = isValid(node);
            // if valid node then add 
            if (valid) {
                found = true;
                ans.push(node);
            }

            const neighbors = getNeighbors(node);
            for (const neighbor of neighbors) {
                if (!visited.has(neighbor)) {
                    queue.push(neighbor);
                    visited.set(neighbor, true);
                }
            }
        }
        // if found then return 
        if (found) {
            return ans;
        }
    }
    return ans;
};

Bipartite Graph Check (Undirected Graph)

  1. Vertices can be divided into two disjoint sets: A bipartite graph can be partitioned into two sets of vertices, with no edges between vertices within each set.
  2. Every edge connects vertices in different sets: Every edge in a bipartite graph connects a vertex from one set to a vertex from the other set.
  3. No odd-length cycles: A bipartite graph cannot contain any odd-length cycles, as this would require vertices from the same set to be connected by an edge.
  4. Maximum degree is bounded by the size of the smaller set: The maximum degree of a vertex in a bipartite graph is equal to the size of the smaller set.
  5. Coloring with two colors: A bipartite graph can be colored with two colors,, such that no adjacent vertices have the same color.

BFS using coloring properties

Let’s use the coloring property to write code to detect if a graph is a bi-partite or not.

  1. It starts by coloring the source vertex (zeroth layer) with the value 0.
  2. Color direct neighbors of the source vertex (first layer) with value 1.
  3. Color the neighbors of direct neighbors (second layer) with value 0 again.
  4. I.e. keep alternating between values 0 and value 1 as the only two valid colors.
  5. If we encounter any violation(s) along the way — an edge with two endpoints having the same color, then we can conclude that the given input graph is not a Bipartite Graph.
  6. In the case of disconnected components, each should be a bipartite graph.
/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function (graph) {
    const n = graph.length;
    const colors = new Array(n).fill(-1);
    const bfs = root => {
        const queue = [root];
        colors[root] = 0; // Color root with 0    
        while (queue.length > 0) {
            const u = queue.shift();
            for (const v of graph[u]) {
                if (colors[v] === -1) { // Unvisited node
                    colors[v] = 1 - colors[u]; // opposite to prev layer
                    queue.push(v);
                } else if (colors[v] === colors[u]) { // Two layers should not have same color
                    return false;
                }
            }
        }
        return true;
    }
    // Check for disconnected components
    for (let i = 0; i < n; i++) {
        if (colors[i] === -1) {
            if (!bfs(i)) { // if one component is not a Bipartite then all is not
                return false;
            }
        }
    }
    return true;
};

BFS using no odd length cycle properties

In the case of a cycle, if a cross edge exists on the same level then an odd cycle exists.

/**
 * @param {number[][]} graph
 * @return {boolean}
 */
var isBipartite = function (graph) {
    const n = graph.length;
    const parent = new Array(n).fill(null);
    const distance = new Array(n).fill(-1);
    const bfs = root => {
        const queue = [root];
        parent[root] = null;
        distance[root] = 0;
        while (queue.length > 0) {
            const u = queue.shift();
            for (const v of graph[u]) {
                if (distance[v] === -1) {
                    queue.push(v);
                    parent[v] = u;
                    distance[v] = distance[u] + 1;
                } else if (parent[u] !== v) {  // cycle exist
                    // if same level cross edge then odd cycle
                    if (distance[u] === distance[v]) {
                        return false;
                    }
                }

            }
        }
        return true;
    }
    for (let i = 0; i < n; i++) {
        if (distance[i] === -1) {
            if (!bfs(i)) {
                return false;
            }
        }
    }
    return true;
};

Topological Ordering

Ordering of DAG i.e. directed acyclic graph. The topological ordering of the graph is not unique.

Topological sort Using DFS on an acyclic graph

const topo = [];
const dfs = node => {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if(visited[node]) {
        dfs(neighbor);
    }
  }
  topo.push(node); // Add at just before getting popped out from stack
}
const sort = ()=> {
  for (int i=0; i < n; i++) {
    if(!visited[i]) {
      dfs(i);
    }
  }
  // Reverse the topo
  return topo.reverse(); // Graph can have many topological sort, this will return one of them
}

Longest path

DAG can have multiple topological orders. DP is nothing but a topological sort. Therefore we can apply dp to solve this problem.

const rec = node=> {
  if(dp[node] !== -1) {
    return dp[node];
  }
  let ans = 1;
  for (const neighbor of graph[node]) {
    ans = Math.max(ans, 1 + rec(neighbor);
  }
  dp[node] = ans;
  return ans;
}
const solve = ()=> {
  let ans = 0;
  for (let i=0; i < n; i++) {
    ans = Math.max(ans, rec(i));
  }
  return ans;
}

Topological sort Using BFS on an acyclic graph (Kahn’s algo)

  1. Find node with indegree=0 and add into topological order
  2. Then remove the node and recalculate the indegree.
  3. Repeat

Q. Removing and recalculating in degrees is an expensive operation. How to recalculate in degrees again and again?

Ans. During building the graph, we can also calculate the initial state of in-degree. Once a node is processed in bfs , instead of physically removing a node from the graph, we can simply update the in-degree for all the neighbors of that node. No need to use visited an array to track the processed node; instead indegree[i]==0 will take care of it.

Q. How to check if the graph has a cycle or not?

A. In the case of the cycle, a node in the cycle will never have indegree[i]=0 therefore these nodes will never be added. So if the size topo is less than n then it means the cycle does exist.

const topo = [];
const indegree = [];
const buildGraph = (n, edges)=> {
  const graph = new Array(n).fill(0).map(a=> []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    indegree[v]++;
  }
};
const bfs = ()=> {
  const queue = [];
  // Initialize queue with all node with indegree 0
  for (let i=0; i < n; i++) {
    const degree = indegree[i];
    if(degree == 0) {
      queue.push(i);
    }
  }
  
  while(queue.length > 0) {
    const node = queue.shift();
    topo.push(node); // Track toplogical order
    for (const neighbor of graph[node]) {
      indegree[neighbor]--;
      if(indegree[neighbor] == 0) {
        queue.push(neighbor);
      }
    }
  }
  if(topo.length == n) {
    return topo;
  }
  console.log("Graph contains cycle");
}

Lexo graphically smallest topological sorting

Simply use Priority Queue instead of regular Queue.

Shortest path

Breath first search is used to find out the shortest path from the source node to the rest. There are many variations of BFS implementation, we will go through each.

BFS — The single source shortest path on the unweighted graph

Level order reversing (bfs) is used to find the shortest path on an unweighted graph. Following are high-level steps.

  1. Initialize queue with the start node.
  2. Keep traversing until the queue is not empty.
  3. Traverse each neighbor of the node from the queue if not visited.

BFS Code pattern #1: Level order traversing

  1. Traverse all nodes at a level
  2. Use distance to track the distance of node and visisted to track the visited node. You can also merge both and just use distance in this simple case to track visited nodes as well.
const bfs = (start) => {
    const visisted = new Array(n).fill(false);
    const distance = new Array(n).fill(-1);
    const queue = [start];
    distance[start] = 0;
    visited[start] = true;
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (!visited[neighbor]) {
                visisted[neighbor] = true; 
                distance[neighbor] = distance[node] + 1;
                queue.push(neighbor);
            }
         }
    }
    return distance;
}

BFS Code pattern #2: Template for distance

We can also write BFS to use distance to track the visited node. This works same as visited for the unweighted graph. If graph is weighted then we do use both. See next section on why.

const bfs = (start) => {
    const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    const queue = [start];
    distance[start] = 0;
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of graph[node]) {
            if (distance[neighbor] > distance[node] + 1) {
                distance[neighbor] = distance[node] + 1;
                queue.push(neighbor);
            }
        }
    }
    return distance;
}

The time complexity of BFS is O(E+V)

0–1 BFS single source shortest path

For a graph with edge weight as either 0 or 1 . Need to find out the shortest path from the given source node. We can take the following approach.

  1. The intuition here is that since weights are only 0 and 1 therefore we can easily sort it by always keeping 0 at the front and 1 at the end.
  2. Use Dequeue instead of Queue.
  3. If the node is 0 then add to the front otherwise to the back.
  4. visited[node] check is required to avoid processing the same node multiple times. Adding this check has no relationship with correctness. This check is only required for optimal time complexity. bcz, the first node which is popped out from the queue will be the smallest distance. It will never be a possibility that later in the phase we discover the shortest path for the node.
  5. Time complexity: O(E+V)
const bfs = (start) => {
    const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    const visited = new Array(n).fill(false);
    const queue = [start];
    distance[start] = 0;
    while (queue.length > 0) {
        const node = queue.shift();
        if(visited[node]) {
            continue;
        }
        visited[node] = true;
        for (const [neighbor, w] of graph[node]) {
            if (distance[neighbor] > distance[node] + w) {
                distance[neighbor] = distance[node] + w;
                if (w === 0) {
                    queue.unshift(neighbor);
                } else {
                    queue.push(neighbor);
                }
            }
        }
    }
    return distance;
}

Dijkstra +ve weighted single source shortest path

  1. Now we will use the weight as the total distance from the starting node instead of a number of hops.
  2. Among all the neighbors, we need to pick the neighbor with the smallest weight. To get the smallest weight quickly, we will be using minPriorityQueue to store the node.
  3. The rest of the flow will be the same as regular BFS.
const bfs = (start) => {
    const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    const visited = new Array(n).fill(false);
    const queue = new PriorityQueue((a,b) => a[1] - b[1]); // Min PriorityQ
    queue.add([start, 0]); // Add start node with 0 cost
    distance[start] = 0;
    while (queue.length > 0) {
        const [node, cost] = queue.shift();
        if(visited[node]) {
            continue;
        }
        visited[node] = true;
        for (const [neighbor, w] of graph[node]) {
            if (distance[neighbor] > distance[node] + w) {
                distance[neighbor] = distance[node] + w;
                queue.add([neighbor, distance[neighbor]]);
            }
        }
    }
    return distance;
}

Time complexity: O((E+V) * logE)

Swim in rising-water

https://leetcode.com/problems/swim-in-rising-water/

  1. The weight of each edge from (i,j) to (x,y) is weight=max(distance[i][j], grid[x][y])
  2. The cost of the path never decreases as we traverse i.e. no negative weights in the graph.
  3. We can apply Dijkstra here to find out the least time to reach from (0,0) to (m-1,n-1)
const usingDijkstra = grid => {
    const m = grid.length;
    const n = grid[0].length;
    const distance = new Array(m).fill(0).map(a => new Array(n).fill(Number.MAX_SAFE_INTEGER));
    // Weight of each edge from (i,j) to neighbor (x,y) is defined as below
    // cost(x,y) = max(cost(i,j), grid[x][y])
    // cost of path never decrease as we traverse i.e. no negative weights in the graph
    // We can apply Dijkstra to find the shortest path form (0,0) to (n-1,n-1)
    const queue = new CustomPriorityQueue((a, b) => a[0] - b[0]);
    queue.add([grid[0][0], 0, 0]);
    distance[0][0] = grid[0][0];
    while (queue.getSize() > 0) {
        const [cost, i, j] = queue.removeTop();
        for (const [x, y] of getNeighbors(m, n, i, j)) {
            if (distance[x][y] > Math.max(cost, grid[x][y])) {
                distance[x][y] = Math.max(cost, grid[x][y]);
                queue.add([distance[x][y], x, y]);
            }
        }
    }
    return distance[m - 1][n - 1];
}

To optimize it, we can also add a check on visited .

const usingDijkstra = grid => {
    const m = grid.length;
    const n = grid[0].length;
    const distance = new Array(m).fill(0).map(a => new Array(n).fill(Number.MAX_SAFE_INTEGER));
    const visited = new Array(m).fill(0).map(a => new Array(n).fill(false));    
    const queue = new CustomPriorityQueue((a, b) => a[0] - b[0]);
    queue.add([grid[0][0], 0, 0]);
    distance[0][0] = grid[0][0];
    while (queue.getSize() > 0) {
        const [cost, i, j] = queue.removeTop();
        if(visited[i][j]) {
            continue;
        }
        visited[i][j] = true;
        for (const [x, y] of getNeighbors(m, n, i, j)) {
            const weight = Math.max(cost, grid[x][y]);
            if (weight  < distance[x][y]) {
                distance[x][y] = weight;
                queue.add([distance[x][y], x, y]);
            }
        }
    }
    return distance[m - 1][n - 1];
}

Bellman-Ford -ve weighted single source shortest path

  1. Trying to reduce edges along the shortest path
  2. Let's say [[u,v,w],[.,.,.],[.,.,.]] is the list of edges with weight.
  3. We find what was the path using the last j-1edges then calculate using j edges.
var shortestPath = function(src) {
    const dp = new Array(n).fill(0).map(a => new Array(m+1).fill(Number.MAX_SAFE_INTEGER));
    // dp[i][j]: shortest path from start to i with j hops, 0 hops mean 0 edges
    // base case: it will 0 to reach from src to src with 0 edges
    dp[src][0] = 0;
    
    // Iterate all hops i.e. edges
    for (let j=1; j < m + 1; j++) {
        // copy from prev column
        for (let i=0; i < n; i++) {
            dp[i][j] = dp[i][j-1];
        }
        // choose shortest path
        for (const [u, v, w] of edges) { // Treat as directed edge
            dp[v][j] = Math.min(
                dp[v][j],
                dp[u][j-1] + w 
            )
        }
    }
    return dp[m];
};

The following problem can be solved using this algorithm.

https://leetcode.com/problems/cheapest-flights-within-k-stops/description/

Single-Destination Shortest Paths

  1. Instead of a single-source s, a single destination vertex t is given.
  2. We are asked what are the shortest paths from more than one source
    vertices to t.
  3. It is better to think backward.
  4. Instead of running an SSSP algorithm multiple times frontally, we can transpose the graph (reverse the direction of all its edges) and run the SSSP the algorithm just once with the destination vertex t as the source vertex.
  5. This technique works on weighted graphs too.

Floyd-Warshall — All pair shortest path algorithm

This is based on reducing nodes by one.

var shortestPath = function (n, edges) {
    const dp = new Array(n).fill(0).map(a => new Array(n).fill(Number.MAX_SAFE_INTEGER));
    // Base case 1: Length of shortest path from using no intermediate vertices
    for (let u= 0; u< n; u++) {
        dp[u][u] = 0;
    }
    // Base case 2: For the given edges, shortest distance is same as weight
    for (const [u, v, w] of edges) { // Undirected graph
        dp[u][v] = w;
        dp[v][u] = w;
    }
    // Repeat n times
    for (let i = 0; i < n; i++) { // nodes that can come between u & v
        for (let u = 0; u < n; u++) {
            for (let v = 0; v < n; v++) {
                dp[u][v] = Math.min(dp[u][v], dp[u][i] + dp[i][v]);
            }
        }
    }
}

Q1. Find cycle using Floyd-Warshal algorithm

Q2. Run Floyd-Warshal on undirected graph

Printing the Shortest Paths for Floyd-Warshal

  1. To print the shortest path, we need to store parent information for each vertex.
  2. In this algorithm, we need 2D parent.
var shortestPath = function (n, edges) {
    const dp = new Array(n).fill(0).map(a => new Array(n).fill(Number.MAX_SAFE_INTEGER));
    const parent = new Array(n).fill(0).map(a => new Array(n).fill(-1));
    // Base case 1: Length of shortest path from using no intermediate vertices
    for (let u= 0; u< n; u++) {
        dp[u][u] = 0;
    }
    // Base case 2: For the given edges, distance is same as weight
    for (const [u, v, w] of edges) {
        dp[u][v] = w;
        dp[v][u] = w;
    }
    // Base case 3: Initiailize parent with same node
    for (let i = 0; i < n; i++) {
      for (let j= 0; j< n; j++) {
          parent[i][j] = i;
      }
    }    
    // Repeat n times
    for (let i = 0; i < n; i++) {
        for (let u = 0; u < n; u++) {
            for (let v = 0; v < n; v++) {
                if(dp[u][v] > dp[u][i] + dp[i][v]) {
                  dp[u][v] = dp[u][i] + dp[i][v];
                  parent[u][v] = parent[i][v]; // from u to v, path is via i   
                }
            }
        }
    }
   // Print all paths between node i and j
   const printPath = (i, j) => {
      if(i !== j) {
        printPath(i, parent[i][j]);
      } 
      console.log(" " +j);
    }
}

MiniMax and MaxiMin using Floyd-Warshall

Multisource shortest path

  1. Some Shortest Paths problems may involve more than a single source.
  2. We call this variant the Multi-Sources Shortest Paths (MSSP) and can be on either unweighted or weighted graphs.

Approach 1: We can simply enqueue all the sources and set dist[s] = 0 for each source s upfront during the initialization step before running the SSSP loop as normal.

Approach 2: Another way of looking at this technique is to imagine that
there exists a (virtual) super source vertex that is (virtually) connected to all those source vertices with (virtual) cost 0 (so these additional 0-weighted edges do not actually contribute to the actual shortest paths).

These technique works on weighted graphs too.

Grid of 1 and 0 find out the farthest zero from any digit one

  1. A grid consists of digits 0 and 1
  2. For each 0, find out the minimum distance to 1.
  3. Find out the overall max distance for each 0 calculated above.

Approach 1: Bruteforce to get the minimum distance for each 0 and keep track of the global max

const solve = grid => {
  const m = grid.length;
  const n = grid[0].length;
  let ans = 0;
  for (let i=0; i < m; i++) {
    for (let j=0; j < n; j++) {
      const cell = grid[i][j];
      if(cell === 0) {
        // Launch bfs to get the distance for first occurance of 1
        const local = bfs(grid, i, j);
        ans = Math.max(ans, local);
      }
    }
  }
  return ans;
}
const bfs = (grid, x, y) => {
  // Refer any bfs template to complete this code.
  return 0;
}

The time complexity of this code is: O(m*n*m*n)

Approach 2: Multisource bfs/dijkstra/dfs

  1. For all 0 finding the closest 1 is a pattern to apply a multisource algorithm.
  2. We can add a supernode and connect to all 1 then run bfs on this super node to find out the shortest path.
  3. The local answer for each cell will be distance -1.
  4. Store the local answer in a distance grid then scan each answer to find out the max value.

5. While writing the code, we can skip adding this supernode, instead initialize all 1 to the queue to begin the bfs.

Following is the code to implement the multisource algorithm.

const solve = grid => {
  const m = grid.length;
  const n = grid[0].length;
  const ones = [];
  const zeroes = [];
  // Get locations for zeroes and ones
  for (let i=0; i < m; i++) {
    for (let j=0; j < n; j++) {
      const cell = grid[i][j];
      if(cell === 0) {
         zeroes.push([i,j]);
      } else {
        ones.push([i,j]);
      }
    }
  }
  // Run multisource bfs
  const queue = [];
  const distance = new Array(m).fill(0).map(a => new Array(n).fill(Number.MAX_SAFE_INTEGER));
  for (const [x,y] of ones) {
    queue.push([x,y]); // Initialize queue
    distance[x][y] = 0; // Initialize distance as zero
  }
  while(queue.length > 0) {
    const [x,y] = queue.shift(); // pop from queue
    for (const [i][j] of getNeighbors(grid, [x,y])) {
      if(distance[i][j] > distance[x][y] + 1) {
          distance[i][j] = distance[x][y] + 1;
          queue.push([i, j);
      }
    }
  }
  // Now calculate the ans
  let ans = 0;
  for (const [i, j] of zeroes) {
    ans = Math.max(ans, distance[i][j]);
  }
  return ans;
}

Find the minimum time to tier 1 cities from every city

  1. Cities are represented as nodes in the graph.
  2. Edge represents the road between two cities. The weight of the edge represents the time it will take to travel on the road to reach from source city to destination city.
  3. Each city is categorized as Tier 1, Tier 2, and Tier 3.
  4. Another data is given to show the flights from one tier city to another tier city and the time taken by flight.
  5. The goal here is to find out the minimum time it will take to reach the tier 1 city from any other city.

Approach 1: Add new edges to the original graph

  1. Add flight as another list of edges to the original graph for each pair of tier cities.
  2. Add all tier 1 cities to the priority queue to implement a multisource single-path algorithm.
  3. Run Dijkastra for each node to get the shortest distance to Tier 1 city
  4. Calculate the global minimum as the answer.

Limitations of this approach:

  1. The number of cities is in the range of 10^5 . Adding a pair of each city for the flight edge will make the graph super big.
  2. This will lead to a TLE error.

Approach 2: Connect both graphs from Tier x city to the same Tier x with zero cost

  1. Connect the city node in the graph to flight same tier node with zero cost as unidirectional.
  2. One edge from the source graph to the tier graph.
  3. The second edge is from the tier graph to the cities graph.

Note: If we use multidirectional then you can take a cost path to reach another city with zero cost. Therefore we need to take the unidirectional edge.

4. Represent city nodes as 0 to n — 1.

5. Represent tier nodes as n….n+k for in and out nodes.

Following is the code implementation of this approach.

const getTierInNode = (n, tier) => {
  return n + tier;
}
const getTierOutNode = (n,tier, k) => {
  return n + tier + k; // k is number of tiers
}

const buildGraph = (n, cities, k, tiers) => {
  const graph = new Array(n + k).fill(0).map(a => []);
  // Add city
  for (const [u, v, w] of cities) {
    graph[u].push([v, w]);
    graph[v].push([u, w]);
  }
  // Add tier
  for (const [x, y, w] of tiers) {
    const u = getTierInNode(n, x);
    const v = getTierOutNode(n, k, 3);
    graph[u].push([v, w]);
  }
  // Add city to tier
  for (let i= 0; i< n; i++) {
    const tier = tiers[i]; // Category for the city i
    const in = getTierInNode(n, tier);
    const out = getTierOutNode(n, tier, k);
    // Add edge
    graph[i].push([in, 0]);
    graph[out].push([i, 0]);
  }
  return graph;
}

const solve = () => {
  // Build graph
  // Run Dijkstra
  // Calculate answer
}

286. Walls and Gates

https://leetcode.com/problems/walls-and-gates/description

You are given an m x n grid rooms initialized with these three possible values.

  • -1 A wall or an obstacle.
  • 0 A gate.
  • INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.

Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Example 1:

Input: rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]
Output: [[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Approach#1: Launch bfs for each gate and keep track of minimum distance

const INF = 2147483647;
const getNeighbors = (rooms, [i, j]) => {
    const m = rooms.length;
    const n = rooms[0].length;
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const ans = [];
    for (const [p, q] of dirs) {
        const x = p + i;
        const y = q + j;
        if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] !== -1) {
            ans.push([x, y]);
        }
    }
    return ans;
}
const bfs = (rooms, [i, j]) => {
    const m = rooms.length;
    const n = rooms[0].length;
    const queue = [[i, j]];
    while (queue.length > 0) {
        const [x, y] = queue.shift();
        for (const [p, q] of getNeighbors(rooms, [x, y])) {
            if (rooms[p][q] > rooms[x][y] + 1) {
                queue.push([p, q]);
                // update distance
                if (rooms[p][q] > rooms[x][y] + 1) {
                    rooms[p][q] = rooms[x][y] + 1;
                }
            }
        }
    }
}
/**
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
var wallsAndGates = function (rooms) {
    const m = rooms.length;
    const n = rooms[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (rooms[i][j] === 0) {
                // launch bfs
                bfs(rooms, [i, j]);
            }
        }
    }
};

Approach #2: Multisource bfs

  1. Each gate is not fully searched before moving on to a new gate.
  2. Each gate only looks at the areas within 1 space before we check the next gate.
  3. So each area within one space of the gates are checked for rooms and these rooms are marked, then added to the queue.
  4. Once all gates are checked, each new space is checked, and so forth.
  5. So, once a room gets hit, it has to be from the closest gate.
const INF = 2147483647;
const getNeighbors = (rooms, [i, j]) => {
    const m = rooms.length;
    const n = rooms[0].length;
    const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
    const ans = [];
    for (const [p, q] of dirs) {
        const x = p + i;
        const y = q + j;
        if (x >= 0 && x < m && y >= 0 && y < n && rooms[x][y] === INF) {
            ans.push([x, y]);
        }
    }
    return ans;
}

/**
 * @param {number[][]} rooms
 * @return {void} Do not return anything, modify rooms in-place instead.
 */
var wallsAndGates = function (rooms) {
    const m = rooms.length;
    const n = rooms[0].length;
    const queue = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (rooms[i][j] === 0) {
                queue.push([i, j]);
            }
        }
    }

    while (queue.length > 0) {
        const [x, y] = queue.shift();
        for (const [p, q] of getNeighbors(rooms, [x, y])) {
            queue.push([p, q]);
            // update distance
            rooms[p][q] = rooms[x][y] + 1;
        }
    }
};

Eulerian Cycle/Path

  1. A circuit that uses every edge of the graph with no repeats i.e. starting from node X and come back to the same node X .
  2. A path that uses every edge of the graph with no repeats is the Eulerian path.
  3. Node can be visited multiple times.
  4. Not all graph has an Eulerian Cycle or path.

Undirected graph condition

  1. Eulerian circuit: A graph contains an Eulerian circuit if all vertices have even degrees.
  2. Eulerian path: A graph contains an Eulerian path if it has at most two vertices of odd degree. One of the odd vertices will be starting and the second will be ending path.

Directed graph condition

  1. Eulerian circuit: A directed graph contains an Eulerian circuit if each vertex has the same in-degree and out-degree.
  2. Eulerian path: A directed graph contains an Eulerian path if each vertex except two has the same in-degree and out-degree.

Problem with normal DFS

  1. In normal DFS, we visit the node only once and we do not care how many times we visit the edge.

Can we modify DFS?

  1. If we can use a data structure that will track the visited edges then we can use DFS.
  2. One option is to remove the edges once visited. So that we can be sure that the visited edge is not considered again.

Standard DFS — Doesn’t work

const dfs = node => {
  visited[node] = true;
  for (const neighbor of graph[node]) {
    if(!visited[neighbor]) {
      dfs(neighbor);
    }
  }
}

Modify DFS to track visited edges by removing edge

const path = [];
const dfs = node => {
  while(graph[node].length > 0) {
    const neighbor = graph[node].pop();
    dfs(neighbor);
  }
  path.push(node);
}
// reverse of `path` will be the Euler path.

Hierholzer’s algorithm to find Eulerian path

  1. Instead of physically deleting the edge, keep track of index of neighbor needs to be processed.
  2. Increment the index of neighbor for each node.
  3. Exit the loop if all neighbors are processed.
const path = [];
const process = [0,0,0,.....,0]; // Initialize 0 for each node
const dfs = node => {
  while(process[node] < graph[node].length) {
    const neighbor = graph[node][process[node]++];    
    dfs(neighbor);
  }
  path.push(node);
}
// reverse of `path` will be the Euler path.

332. Reconstruct Itinerary

https://leetcode.com/problems/reconstruct-itinerary/description/

You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.

All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.

  • For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"].

You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.

Example 1:

Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]]
Output: ["JFK","MUC","LHR","SFO","SJC"]

Approach

  1. Each ticket represent the edge of two nodes in the graph.
  2. We need to use ticket only once, it mens edge needs to be traverse only once.
  3. We have given starting node as JFK.
  4. Goal is to return the itinerary of user to start from JFK to last city.
  5. This is nothing but Eulerian path. We can simply apply it.
  6. Note: Since we need to return one lexicographical order, therefore once neighbors is build then sort it.

Code using edge removal

const buildGraph = tickets => {
    const graph = new Map();
    for (const [u, v] of tickets) {
        if (!graph.has(u)) {
            graph.set(u, []);
        }
        if (!graph.has(v)) {
            graph.set(v, []);
        }
        graph.get(u).push(v);
    }
    for (const [key, value] of graph) {
        graph.get(key).sort();
    }
    return graph;
}
/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
    const graph = buildGraph(tickets);
    const ans = [];
    const dfs = node => {
        while (graph.get(node).length > 0) {
            const neighbor = graph.get(node).shift();;
            dfs(neighbor);
        }
        ans.push(node);
    }
    dfs('JFK');
    return ans.reverse();
};

Code using Hierholzer

const buildGraph = tickets => {
    const graph = new Map();
    for (const [u, v] of tickets) {
        if (!graph.has(u)) {
            graph.set(u, []);
        }
        if (!graph.has(v)) {
            graph.set(v, []);
        }
        graph.get(u).push(v);
    }
    for (const [key, value] of graph) {
        graph.get(key).sort();
    }
    return graph;
}
/**
 * @param {string[][]} tickets
 * @return {string[]}
 */
var findItinerary = function (tickets) {
    const graph = buildGraph(tickets);
    const ans = [];
    const neighbors = new Map();
    for (const [key] of graph) {
        neighbors.set(key, 0);
    }
    const dfs = node => {
        const n = graph.get(node).length;
        while (neighbors.get(node) < graph.get(node).length) {
            const i = neighbors.get(node);
            const neighbor = graph.get(node)[i];
            neighbors.set(node, i + 1);
            dfs(neighbor);
        }
        ans.push(node);
    }
    dfs('JFK');
    return ans.reverse();
};

Hamiltonian Path

A Hamiltonian path is a path in a graph that visits every vertex exactly once. In other words, it’s a route that traverses every node of the graph without repeating any node.

This is an NP-hard problem i.e. exponential cost of O(2^N).

State Space Search

https://leetcode.com/problems/sliding-puzzle/description/

The goal here is to find out the minimum moves required for the state of the board to reach the final state.

Approach

We have following here

  1. Space state: Set of possible states that the board can be in.
  2. Initial state
  3. Goal state
  4. State transition function: Operator or get neighbors
  5. Path cost: Number of moves to get from initial state to goal state.

We can use BFS to find out the shortest path to reach the goal. Each state of the board is treated as a node of the graph. The transition function gives the neighbor of the node.

const swap = (node, zeroIndex, move) => {
    const tokens = node.split('');
    [tokens[zeroIndex], tokens[move]] = [tokens[move], tokens[zeroIndex]];
    return tokens.join('');
}
const getNeighbors = node => {
    const neighbors = [];
    // All the positions 0 can be swapped to in 1-d representation
    const directions = [[1, 3], [0, 2, 4], [1, 5], [0, 4], [1, 3, 5], [2, 4]];
    const zeroIndex = node.indexOf('0');
    for (const move of directions[zeroIndex]) {
        const neighbor = swap(node, zeroIndex, move);
        neighbors.push(neighbor);
    }
    return neighbors;
}
/**
 * @param {number[][]} board
 * @return {number}
 */
var slidingPuzzle = function (board) {
    const target = '123450';
    const start = board.map(row => row.join('')).join('');
    const distance = new Map(); // Use distance to track visited as well
    const queue = [start];
    visited.set(start, 0);
    while (queue.length > 0) {
        const node = queue.shift();
        for (const neighbor of getNeighbors(node)) {
            if (!distance.has(neighbor)) {
                queue.push(neighbor);
                distance.set(neighbor, distance.get(node) + 1);
            }
        }
    }
    return distance.has(target) ? distance.get(target) : -1;
};

Farmer, wolf, goat, cabbage, and crossing the river

Water and Jug Problem

https://leetcode.com/problems/water-and-jug-problem/description/

Happy coding :)

Graph
Algorithms

--

--

Dilip Kumar

Written by Dilip Kumar

345 Followers

With 18+ years of experience as a software engineer. Enjoy teaching, writing, leading team. Last 4+ years, working at Google as a backend Software Engineer.

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams