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.
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();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);
}
}
}
}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);
}
}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));
}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);
}
}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.
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.
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.
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());You’re given a Node class that has a name and array of optional children nodes. When put together, nodes form an acyclic tree-like structure.
Implement the depthFirstSearch method on the Node class, which takes in an empty array, traverses the tree using the Depth-first Search approach(specifically navigating the tree from left to right), stores all the nodes’ names in the input array, and returns in.
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;
}
}You’re given a two-dimensional array (a matrix) of potentially unequal height and width containing only Os and 1s. The matrix represents a two-toned image, where each 1 represents black and each 0 represents white. An siland is defined as any number of 1s that are horizontally or vertically adjacent (but not diagonally adjacent) and that don’t touch the border of the image. In other words, a group of horizontally or vertically adjacent 1s isn’t an island if any of those 1s are in the first row, last row, first column or last column of the input matrix.
You can think of islands as patches of black that don’t touch the border of the two-toned image.
Write a function that returns a modified version of the input matrix, where all of the islands are removed. You remove an island by replacing it with 0s.
You’re allowed to mutate the input matrix.
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);
}
}
}You are given a two-dimensoinal array(a matrix) of potentially unequal height and width containing letters; this matrix represents a boggle board. You’re also given a list of words.
Write a function that reutrns an array of all the words contained in the boggle board. The final words don’t need to be in any particular order.
A word is constructed in the boggle board by connecting adjacent (horizontally, vertically or diagonally) letters, without using any single letter at a given position more than once; while a word can of course have repeated letters. Those repeated letters must come from different positions in the boggle board in order for the word to be contained in the board. Note that two or more words are allowed to overlap and use the same letters in the boggle board.
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;
};