Đồ thị là biểu diễn hình ảnh của một tập hợp đối tượng nơi một số cặp đối tượng được nối bởi các liên kết. Các đối tượng liên kết được biểu diễn bằng điểm gọi là vertices (đỉnh), và các liên kết nối các đỉnh gọi là edges (cạnh).
Chính thức, đồ thị là một cặp tập hợp (V, E), trong đó V là tập hợp đỉnh và E là tập hợp cạnh, nối các cặp đỉnh. Xem đồ thị sau:
Trong đồ thị trên:
V = {a, b, c, d, e}
E = {ab, ac, bd, cd, de}
Thuật ngữ
Đồ thị toán học có thể biểu diễn trong cấu trúc dữ liệu. Ta có thể biểu diễn đồ thị bằng mảng đỉnh và mảng hai chiều cạnh. Trước khi tiến xa hơn, hãy làm quen với một số thuật ngữ quan trọng:
Vertex (Đỉnh) - Mỗi nút của đồ thị được biểu diễn như một vertex. Trong ví dụ sau, hình tròn có nhãn đại diện cho vertices. Do đó A đến G là vertices. Ta có thể biểu diễn chúng bằng mảng như hình sau. A có thể xác định bằng chỉ số 0. B bằng chỉ số 1, v.v.
Edge (Cạnh) - Edge biểu diễn đường đi giữa hai đỉnh hoặc đường nối hai đỉnh. Trong ví dụ sau, đường từ A đến B, B đến C, v.v. đại diện cho edges. Ta có thể dùng mảng hai chiều để biểu diễn như hình sau. AB có thể biểu diễn là 1 tại hàng 0, cột 1, BC là 1 tại hàng 1, cột 2, v.v., giữ các tổ hợp khác là 0.
Adjacency (Kề nhau) - Hai nút hoặc đỉnh kề nhau nếu chúng được nối với nhau qua một cạnh. Trong ví dụ sau, B kề với A, C kề với B, v.v.
Path (Đường đi) - Path biểu diễn chuỗi các cạnh giữa hai đỉnh. Trong ví dụ sau, ABCD đại diện cho đường đi từ A đến D.
Dưới đây là triển khai hoàn chỉnh của class Graph bằng JavaScript.
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);
}
}