The following code snippet shows an implementation of a Graph in JS
class Graph {
verticies = {};
add(vertix, adjacencies) {
if (!this.verticies[vertix]) this.verticies[vertix] = new Set();
for (const adjacent of adjacencies) {
if (vertix == adjacent) continue;
if (!this.verticies[adjacent]) this.verticies[adjacent] = new Set();
this.verticies[vertix].add(adjacent);
this.verticies[adjacent].add(vertix);
}
}
}Union Find is an algorithm that can be used to find disjoint sets, and cycles in a graph. Below are two implementations of this algorithm.
class UnionFind {
// Time Complexity: find: O(n), union: O(n)
constructor(n) {
this.n = n;
this.root = new Array(n).fill().map((v, i) => i);
}
find(node) {
if (this.root[node] == node) return node;
return (this.root[node] = this.find(this.root[node]));
}
union(a, b) {
const u = this.find(a),
v = this.find(b);
if (u == v) return false; // Cycle
this.root[u] = v;
}
disjointSets() {
const set = new Set();
for (let i = 0; i < this.n; i++) set.add(this.find(i));
return set.size;
}
}2. Optimized (Ranked)
class UnionFind {
// Time Complexity: find: O(n), union: O(n)
constructor(n) {
this.n = n;
this.root = new Array(n).fill().map((v, i) => i);
this.rank = new Array(n).fill(1);
}
find(node) {
if (this.root[node] == node) return node;
return (this.root[node] = this.find(this.root[node]));
}
union(a, b) {
const u = this.find(a),
v = this.find(b);
if (u == v) return false;
if (this.rank[u] > this.rank[v]) {
this.root[v] = u;
this.rank[u] += this.rank[v];
} else {
this.root[u] = v;
this.rank[v] += this.rank[u];
}
return true;
}
disjointSets() {
const set = new Set();
for (let i = 0; i < this.n; i++) set.add(this.find(i));
return set.size;
}
}
| Case | /^\d+$/ .test(variable) | /^[0-9]+$/ .test(variable) | !isNaN (variable) | typeof variable |
|---|---|---|---|---|
| “123” | True | True | True | string |
| ” “ | False | False | True | string |
| 123 | True | True | True | number |
| “1.23” | False | False | True | string |
| 1.23 | False | False | True | number |
| “abc” | False | False | False | string |