Looking at the implementation of graphs. Covering searching graphs, famous graph algorithms and problem sets.

A graph is a collection of nodes/verticies which are connected to each other through edges. There are no rules with how nodes are connected.

Structure

class Graph {
  constructor() {
    this.nodes = new Map();
  }
  addNode(node) {
    this.nodes.set(node, []);
  }
  addEdge(source, destination) {
    this.nodes.get(source).push(destination);
    this.nodes.get(destination).push(source);
  }
  display() {
    for (let [node, adjacencyList] of this.nodes) {
      console.log(`${node}: ${adjacencyList}`);
    }
  }
}

let graph = new Graph();

Ways of Searching

Breadth First Search

Use Case: Check if there is a path between two nodes

Implementation: Queue (First in First Out FIFO)

breadthFirstSearch(startingNode) {
     let visitedNode = [];
     let queue = [];

     visitedNode[startingNode] = true;
     queue.push(startingNode);

     while (queue.length > 0) {
         const currentNode = queue.shift();

         console.log(currentNode);

         const adjacencyListOfCurrentNode = this.nodes.get(currentNode);

         for (let node of adjacencyListOfCurrentNode) {
             if (!visitedNode[node]) {
                 visitedNode[node] = true;
                 queue.push(node);
             }
         }
     }
 }

Depth First Search

Use Case: Backtracking, complete search, exhausting search

Implementation: Stack (Last in First Out LIFO), can also be done recursively

depthFirstSearch(startingNode) {
   let visitedNode = [];
   this.dfsRecursion(startingNode, visitedNode);
}
dfsRecursion(currentNode, visitedNode) {
   visitedNode[currentNode] = true;

   console.log(currentNode);

   let adjacencyListOfCurrentNode = this.nodes.get(currentNode);

   for (var node of adjacencyListOfCurrentNode) {
       if (!visitedNode[node]) this.dfsRecursion(node, visitedNode);
   }
}

Famous Graph Algorithms

Dijsktra’s Algorithm

function dijkstrasAlgorithm(start, edges) {
  const visitedSet = new Set();
  const minDistance = new Array(edges.length).fill(Infinity);

  const queue = [];
  queue.push(start);
  minDistance[start] = 0;

  while (queue.length) {
    const currNodeIndex = queue.shift();
    if (visitedSet.has(currNodeIndex)) continue;

    const currNode = edges[currNodeIndex];

    for (const [nextNodeIndex, distance] of currNode) {
      const oldDistance = minDistance[nextNodeIndex];
      const newDistance = minDistance[currNodeIndex] + distance;

      minDistance[nextNodeIndex] = Math.min(newDistance, oldDistance);
      queue.push(nextNodeIndex);
    }
    visitedSet.add(currNodeIndex);
  }
  return minDistance.map((distance) => (distance === Infinity ? -1 : distance));
}

The A* Algorithm

A path finding algorithm, which is often used to find the shortest path in the graph.

Heuristic: This gives you the estimated total cost of taking one papth over another

class Node {
  constructor(row, col, value) {
    this.id = row.toString() + "-" + col.toString();
    this.row = row;
    this.col = col;
    this.value = value;
    this.distanceFromStart = Infinity;
    this.estimatedDistanceToEnd = Infinity;
    this.cameFrom = null;
  }
}

function aStartAlgorithm(startRow, startCol, endRow, endCol, graph) {
  const nodes = initaliseNodes(graph);

  const startNode = nodes[startRow][startCol];
  const endNode = nodes[endRow][endCol];

  startNode.distanceFromStart = 0;
  startNode.estimatedDistanceToEnd = calculateManhattanDistance(
    startNode,
    endNode
  );

  const nodesToVisit = new MinHeap([startNode]);

  while (!nodesToVist.isEmpty()) {
    const currentMinDistanceNode = nodesToVisit.remove();

    if (currentMinDistanceNode === endNode) break;

    const neighbors = getNeighboringNodes(currentMinDistanceNode, nodes);
    for (const neighbor of neighbors) {
      if (neighbor.value == 1) continue;

      const tentativeDistanceToNeighbor =
        currentMinDistanceNode.distanceFromStart + 1;

      if (tentativeDistanceToNeighbor >= neighbor.distanceFromStart) continue;

      neighbor.cameFrom = currentMinDistanceNode;
      neighbor.distanceFromStart = tenativeDistanceToNeighbor;
      neighbor.estimatedDistanceToEnd =
        tentativeDistanceToNeighbor +
        calculateManhattanDistance(neighbor, endNode);

      if (!nodesToVisit.containsNode(neighbor)) {
        nodesToVisit.insert(neighbor);
      } else {
        nodesToVisit.update(neighbor);
      }
    }
  }
  return reconstructPath(endNode);
}

function initialiseNodes(graph) {
  const nodes = [];

  for (const [i, row] of graph.entries()) {
    nodes.push([]);
    for (const [j, value] of row.entries()) {
      const node = new Node(i, j, value);
      nodes[i].push(node);
    }
  }
  return nodes;
}

function calculateManhattanDistance(currentNode, endNode) {
  const currentRow = currentNode.row;
  const currentCol = currentNode.col;
  const endRow = endNode.row;
  const endCol = endNode.col;

  return Math.abs(currentRow - endRow) + Math.abs(currentCol - endCol);
}

function getNeighboringNodes(node, nodes) {
  const neighbors = [];
  const numRows = nodes.length;
  const numCols = nodes[0].length;
  const row = node.row;
  const col = node.col;

  // down
  if (row < numRows - 1) {
    neighbors.push(nodes[row + 1][col]);
  }

  // up
  if (row > 0) {
    neighbors.push(nodes[row - 1][col]);
  }

  // right
  if (col < numCols - 1) {
    neighbors.push(nodes[row][col + 1]);
  }

  // left
  if (col > 0) {
    neighbors.push(nodes[row][col - 1]);
  }

  return neighbors;
}

function reconstructPath(endNode) {
  if (endNode.cameFrom == null) {
    return [];
  }

  let currentnode = endNode;
  const path = [];

  while (currentNode != null) {
    path.push([currentNode.row, currentNode.col]);
    currentNode = currentNode.cameFrom;
  }

  path.reverse();

  return path;
}

class minHeap {
  construct(array) {
    this.nodePositionInHeap = array.reduce((obj, node, i) => {
      obj[node.id] = i;
      return obj;
    }, {});
    this.heap = this.buildHeap(array);
  }

  isEmpty() {
    return this.heap.length == 0;
  }

  buildHeap(array) {
    const firstParentIdx = Math.floor((array.length - 2) / 2);
    for (let currentIdx = firstParentIdx; currentIdx >= 0; currentIdx--) {
      this.siftDown(currentIdx, array.length - 1, array);
    }
    return array;
  }

  siftDown(currentIdx, endIdx, heap) {
    let childOneIdx = currentIdx * 2 + 1;
    while (childOneIdx <= endIdx) {
      const childTwoIdx =
        currentIdx * 2 + 2 <= endIdx ? currentIdx * 2 + 2 : -1;
      let IdxToSwap;
      if (
        childTwoIdx !== -1 &&
        heap[childTwoIdx].estimatedDistanceToEnd <
          heap[childOneIndex].estimatedDistanceToEnd
      ) {
        idxToSwap = childTwoIdx;
      } else {
        idxToSwap = childOneIdx;
      }
      if (
        heap[idxToSwap].estimatedDistanceToEnd <
        heap[currentIdx].estimateDistanceToEnd
      ) {
        this.swap(currentIdx, idxToSwap, heap);
        currentIdx = idxToSwap;
        childOneIdx = currentIdx * 2 + 1;
      } else {
        return;
      }
    }
  }

  siftUp(currentIdx, heap) {
    let parentIdx = Math.floor((currentIdx - 1) / 2);
    while (
      currentIdx > 0 &&
      heap[currentIdx].estimatedDistancetoEnd <
        heap[parentIdx].estimatedDistancetoEnd
    ) {
      this.swap(currentIdx, parentIdx, heap);
      currentIdx = parentIdx;
      parentIdx = Math.floor((currentIdx - 1) / 2);
    }
  }

  remove() {
    if (this.isEmpty()) return;
    this.swap(0, this.heap.length - 1, this.heap);
    const node = this.heap.pop();
    delete this.nodePositionsInHeap[node.id];
    this.siftDown(0, this.heap.length - 1, this.heap);
    return node;
  }

  insert(node) {
    this.heap.push(node);
    this.nodePositionsInHeap[node.id] = this.heap.length - 1;
    this.siftUp(this.heap.length - 1, this.heap);
  }

  swap(i, j, heap) {
    this.nodePositionsInHeap[this.heap[i].id] = j;
    this.nodePositionsInHeap[this.heap[j].id] = i;
    const temp = heap[j];
    heap[j] = heap[i];
    heap[i] = temp;
  }

  containsNode(node) {
    return node.in in this.nodePositionsInHeap;
  }

  update(node) {
    this.siftUp(this.nodePositionsInHeap[node.id], this.heap);
  }
}

Disjointed Sets

Checking if two vertices are connected, either directly or in-directly. The array index is the vertext and the array element is the parent vertext. To check connectivity, find the root nodes of each (the array value and the array index will be the same). The find function will find the root node of a given vertext. The unnion function unions two vertices and makes their root nodes the same.

Quick Find

Store the root node as an element in the array. In the find functionm you can find the root node. Instead of storing the parent node in array value, you will need to store the root node instead. There is an extra step in union, tarverse the entire array and the root node.

Quick Union

Need a root array and the element of an array with be the root node. Connect the element directly to the root node instead. Traverse the parent nodes until it’s parent node is equal to itself.

Example Code

var set = disjointSet(); // instantiate disjoint-set data structure

var person1 = {
  name: "oneName",
  surname: "oneSurname",
};
var person2 = {
  name: "twoName",
  surname: "twoSurname",
};
var person3 = {
  name: "threeName",
  surname: "threeSurname",
};
var person4 = {
  name: "fourName",
  surname: "fourSurname",
};
var person5 = {
  name: "fiveName",
  surname: "fiveSurname",
};
var person6 = {
  name: "sixName",
  surname: "sixSurname",
};

// add objects to the set
set
  .add(person1)
  .add(person2)
  .add(person3)
  .add(person4)
  .add(person5)
  .add(person6);

// connect some objects to each other
set.union(person1, person2);
set.union(person2, person3);
set.union(person3, person4);
set.union(person5, person6);

// check connections
console.log(set.connected(person1, person2)); // returns true. Direct connection
console.log(set.connected(person1, person4)); // returns true. Indirect connection
console.log(set.connected(person5, person6)); // returns true. Another direct connection
console.log(set.connected(person4, person5)); // returns false. No connection

/**
 * returns two arrays grouped by connection:
 * [
 *     [person1, person2, person3, person4],
 *     [person5, person6]
 * ]
 */
console.log(set.extract());

Problem Sets

Easy

      A
    / | \
   B  C  D
  / \   / \
 E   F G   H
    / \ \
   I   J  K

["A", "B", "E", "F", "I", "J", "C", "D", "G", "K", "H"]

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

  addChild(name) {
    this.children.push(new Node(name));
    return this;
  }

  depthFirstSearch(array) {}
}

class Node {
  constructor(name) {
    this.name = name;
    this.children = [];
  }

  addChild(name) {
    this.children.push(new Node(name));
    return this;
  }

  depthFirstSearch(array) {
    array.push(this.name);
    for (const child of this.children) {
      child.depthFirstSearch(array);
    }
    return array;
  }
}

Medium

matrix = [
  [1, 0, 0, 0, 0, 0],
  [0, 1, 0, 1, 1, 1],
  [0, 0, 1, 0, 1, 0],
  [1, 1, 0, 0, 1, 0],
  [1, 0, 1, 1, 0, 0],
  [1, 0, 0, 0, 0, 1],
]

[
  [1, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 1, 1],
  [0, 0, 0, 0, 1, 0],
  [1, 1, 0, 0, 1, 0],
  [1, 0, 0 ,0, 0, 0],
  [1, 0, 0, 0, 0, 1],
]

/*
  islands removed
  [
    [ , , , , , ],
    [ ,1, , , , ],
    [ , ,1, , , ],
    [ , , , , , ],
    [ , ,1,1, , ],
    [ , , , , , ],
  ]
*/

function removeIslands(matrix) {
  for (let i = 0; i < matrix[0].length; i++) {
    traverseNeighbors(0, i, matrix);
    traverseNeighbors(matrix.length - 1, i, matrix);
  }
  for (let j = 0; j < matrix.length; j++) {
    traverseNeighbors(j, 0, matrix);
    traverseNeighbors(j, matrix[0].length - 1, matrix);
  }

  for (let j = 0; j < matrix.length; j++) {
    for (let i = 0; i < matrix[0].length; i++) {
      const value = matrix[j][i];
      if (value == 1) {
        matrix[j][i] = 0;
      } else if (value == 2) {
        matrix[j][i] = 1;
      }
    }
  }

  return matrix;
}

function traverseNeighbors(j, i, matrix) {
  const current = matrix[j][i];

  if (current == 1) {
    matrix[j][i] = 2;
    if (j + 1 < matrix.length) {
      traverseNeighbors(j + 1, i, matrix);
    }
    if (j - 1 >= 0) {
      traverseNeighbors(j - 1, i, matrix);
    }
    if (i + 1 < matrix[0].length) {
      traverseNeighbors(j, i + 1, matrix);
    }
    if (i - 1 >= 0) {
      traverseNeighbors(j, i - 1, matrix);
    }
  }
}

Hard

board = [
  ["t", "h", "i", "s", "i", "s", "a"],
  ["s", "i"m "m", "p", "l", "e", "x"],
  ["b", "x", "x", "x", "x", "e", "b"],
  ["x", "o", "g", "g", "l", "x", "o"],
  ["x", "x", "x", "D", "T", "r", "a"],
  ["R", "E", "P", "E", "A", "d", "x"],
  ["x", "x", "x", "x", "x", "x", "x"],
  ["N", "O", "T", "R", "E", "-", "P"],
  ["x", "x", "D", "E", "T", "A", "E"],
]

words = [
  "this", "is", "not", "a", "simple", "boggle", "board", "test", "REPEATED", "NOTRE=PEATED",
]

["this", "is", "a", "simple", "boggle", "board", "NOTRE-PEATED"]

function boggleBoard(board, words) {}

function boggleBoard(board, words) {
  const result = new Set();
  const map = {};

  for (let word of words) {
    const letter = word[0];
    if (map[letter] === undefined) map[letter] = [];
    map[letter].push(word);
  }

  for (let j = 0; j < board.length; j++) {
    for (let k = 0; k < board[0].length; k++) {
      const letter = board[j][k];
      if (map[letter] !== undefined) {
        map[letter].forEach((word) => {
          if (!result.has(word) && findWord(j, k, board, word, 0)) {
            result.add(word);
          }
        });
      }
    }
  }
  return Array.from(result);
}

const findWord = (row, col, matrix, word, index) => {
  if (
    row < 0 ||
    col < 0 ||
    row >= matrix.length ||
    col >= matrix[0].length ||
    matrix[row][col] !== word[index]
  )
    return false;

  if (index === word.length - 1) return true;

  const temp = matrix[row][col];
  matrix[row][col] = "*";

  const wordFound =
    findWord(row + 1, col, matrix, word, index + 1) ||
    findWord(row - 1, col, matrix, word, index + 1) ||
    findWord(row, col + 1, matrix, word, index + 1) ||
    findWord(row, col - 1, matrix, word, index + 1) ||
    findWord(row + 1, col + 1, matrix, word, index + 1) ||
    findWord(row - 1, col - 1, matrix, word, index + 1) ||
    findWord(row + 1, col - 1, matrix, word, index + 1) ||
    findWord(row - 1, col + 1, matrix, word, index + 1);

  matrix[row][col] = temp;

  return wordFound;
};