Các hàm bị comment trong code này. Bạn có thể chuyển sang dùng chúng. Chúng ta cũng đã chuyển class Queue, Stack, PriorityQueue vào các module riêng có thể import bằng câu lệnh import hoặc require. Dưới đây là triển khai hoàn chỉnh của class Graph:
Ví dụ
const Queue = require("./Queue");
const Stack = require("./Stack");
const PriorityQueue = require("./PriorityQueue");
class Graph {
constructor() {
this.edges = {};
this.nodes = [];
}
addNode(node) {
this.nodes.push(node);
this.edges[node] = [];
}
addEdge(node1, node2, weight = 1) {
this.edges[node1].push({ node: node2, weight: weight });
this.edges[node2].push({ node: node1, weight: weight });
}
addDirectedEdge(node1, node2, weight = 1) {
this.edges[node1].push({ node: node2, weight: weight });
}
// addEdge(node1, node2) {
// this.edges[node1].push(node2);
// this.edges[node2].push(node1);
// }
// addDirectedEdge(node1, node2) {
// this.edges[node1].push(node2);
// }
display() {
let graph = "";
this.nodes.forEach(node => {
graph += node + "->" + this.edges[node].map(n => n.node).join(", ") + "\n";
});
console.log(graph);
}
BFS(node) {
let q = new Queue(this.nodes.length);
let explored = new Set();
q.enqueue(node);
explored.add(node);
while (!q.isEmpty()) {
let t = q.dequeue();
console.log(t);
this.edges[t].filter(n => !explored.has(n)).forEach(n => {
explored.add(n);
q.enqueue(n);
});
}
}
DFS(node) {
// Tạo Stack và thêm nút khởi tạo vào
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// Đánh dấu nút đầu tiên đã khám phá
explored.add(node);
// Tiếp tục cho đến khi Stack rỗng
while (!s.isEmpty()) {
let t = s.pop();
// Log mọi phần tử ra khỏi Stack
console.log(t);
// 1. Trong object edges, tìm nút mà nút này kết nối trực tiếp.
// 2. Lọc bỏ nút đã được khám phá.
// 3. Đánh dấu mỗi nút chưa khám phá là đã khám phá và đẩy vào Stack.
this.edges[t].filter(n => !explored.has(n)).forEach(n => {
explored.add(n);
s.push(n);
});
}
}
topologicalSortHelper(node, explored, s) {
explored.add(node);
this.edges[node].forEach(n => {
if (!explored.has(n)) {
this.topologicalSortHelper(n, explored, s);
}
});
s.push(node);
}
topologicalSort() {
// Tạo Stack và thêm nút khởi tạo vào
let s = new Stack(this.nodes.length);
let explored = new Set();
this.nodes.forEach(node => {
if (!explored.has(node)) {
this.topologicalSortHelper(node, explored, s);
}
});
while (!s.isEmpty()) {
console.log(s.pop());
}
}
BFSShortestPath(n1, n2) {
let q = new Queue(this.nodes.length);
let explored = new Set();
let distances = { n1: 0 };
q.enqueue(n1);
explored.add(n1);
while (!q.isEmpty()) {
let t = q.dequeue();
this.edges[t].filter(n => !explored.has(n)).forEach(n => {
explored.add(n);
distances[n] = distances[t] == undefined ? 1 : distances[t] + 1;
q.enqueue(n);
});
}
return distances[n2];
}
primsMST() {
// Khởi tạo graph chứa MST
const MST = new Graph();
if (this.nodes.length === 0) {
return MST;
}
// Chọn nút đầu tiên làm nút bắt đầu
let s = this.nodes[0];
// Tạo Priority Queue và tập explored
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
let explored = new Set();
explored.add(s);
MST.addNode(s);
// Thêm tất cả cạnh từ nút bắt đầu vào PQ lấy trọng số làm priority
this.edges[s].forEach(edge => {
edgeQueue.enqueue([s, edge.node], edge.weight);
});
// Lấy cạnh nhỏ nhất và thêm vào graph mới
let currentMinEdge = edgeQueue.dequeue();
while (!edgeQueue.isEmpty()) {
// Tiếp tục lấy cạnh cho đến khi có cạnh với nút chưa khám phá
while (!edgeQueue.isEmpty() && explored.has(currentMinEdge.data[1])) {
currentMinEdge = edgeQueue.dequeue();
}
let nextNode = currentMinEdge.data[1];
// Kiểm tra lại vì queue có thể rỗng mà không trả về phần tử chưa khám phá
if (!explored.has(nextNode)) {
MST.addNode(nextNode);
MST.addEdge(currentMinEdge.data[0], nextNode, currentMinEdge.priority);
// Lại thêm tất cả cạnh vào PQ
this.edges[nextNode].forEach(edge => {
edgeQueue.enqueue([nextNode, edge.node], edge.weight);
});
// Đánh dấu nút này đã khám phá
explored.add(nextNode);
s = nextNode;
}
}
return MST;
}
kruskalsMST() {
// Khởi tạo graph chứa MST
const MST = new Graph();
this.nodes.forEach(node => MST.addNode(node));
if (this.nodes.length === 0) {
return MST;
}
// Tạo Priority Queue
let edgeQueue = new PriorityQueue(this.nodes.length * this.nodes.length);
// Thêm tất cả cạnh vào Queue:
for (let node in this.edges) {
this.edges[node].forEach(edge => {
edgeQueue.enqueue([node, edge.node], edge.weight);
});
}
let uf = new UnionFind(this.nodes);
// Lặp cho đến khi khám phá hết nút hoặc queue rỗng
while (!edgeQueue.isEmpty()) {
// Lấy dữ liệu cạnh dùng destructuring
let nextEdge = edgeQueue.dequeue();
let nodes = nextEdge.data;
let weight = nextEdge.priority;
if (!uf.connected(nodes[0], nodes[1])) {
MST.addEdge(nodes[0], nodes[1], weight);
uf.union(nodes[0], nodes[1]);
}
}
return MST;
}
djikstraAlgorithm(startNode) {
let distances = {};
// Lưu tham chiếu đến nút trước
let prev = {};
let pq = new PriorityQueue(this.nodes.length * this.nodes.length);
// Đặt khoảng cách đến tất cả nút là infinity trừ startNode
distances[startNode] = 0;
pq.enqueue(startNode, 0);
this.nodes.forEach(node => {
if (node !== startNode) distances[node] = Infinity;
prev[node] = null;
});
while (!pq.isEmpty()) {
let minNode = pq.dequeue();
let currNode = minNode.data;
let weight = minNode.priority;
this.edges[currNode].forEach(neighbor => {
let alt = distances[currNode] + neighbor.weight;
if (alt < distances[neighbor.node]) {
distances[neighbor.node] = alt;
prev[neighbor.node] = currNode;
pq.enqueue(neighbor.node, distances[neighbor.node]);
}
});
}
return distances;
}
floydWarshallAlgorithm() {
let dist = {};
for (let i = 0; i < this.nodes.length; i++) {
dist[this.nodes[i]] = {};
// Với cạnh hiện có gán khoảng cách bằng trọng số
this.edges[this.nodes[i]].forEach(e => (dist[this.nodes[i]][e.node] = e.weight));
this.nodes.forEach(n => {
// Với tất cả nút khác gán là infinity
if (dist[this.nodes[i]][n] == undefined)
dist[this.nodes[i]][n] = Infinity;
// Với cạnh tự thân gán khoảng cách là 0
if (this.nodes[i] === n) dist[this.nodes[i]][n] = 0;
});
}
this.nodes.forEach(i => {
this.nodes.forEach(j => {
this.nodes.forEach(k => {
// Kiểm tra đi từ i đến k rồi k đến j có tốt hơn
// không so với đi trực tiếp từ i đến j. Nếu có thì cập nhật
// giá trị i đến j thành giá trị mới
if (dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
});
});
});
return dist;
}
}
class UnionFind {
constructor(elements) {
// Số thành phần không liên thông
this.count = elements.length;
// Theo dõi các thành phần liên thông
this.parent = {};
// Khởi tạo cấu trúc dữ liệu sao cho tất cả phần tử có chính nó làm parent
elements.forEach(e => (this.parent[e] = e));
}
union(a, b) {
let rootA = this.find(a);
let rootB = this.find(b);
// Root cùng nhau nghĩa là đã liên thông.
if (rootA === rootB) return;
// Luôn làm phần tử có root nhỏ hơn làm parent.
if (rootA < rootB) {
if (this.parent[b] != b) this.union(this.parent[b], a);
this.parent[b] = this.parent[a];
} else {
if (this.parent[a] != a) this.union(this.parent[a], b);
this.parent[a] = this.parent[b];
}
}
// Trả về parent cuối cùng của nút
find(a) {
while (this.parent[a] !== a) {
a = this.parent[a];
}
return a;
}
// Kiểm tra liên thông của 2 nút
connected(a, b) {
return this.find(a) === this.find(b);
}
}