Giới thiệu
Graph là một cấu trúc dữ liệu gồm:
- Các đỉnh (Vertices hoặc Nodes)
- Các cạnh (Edges): Kết nối các đỉnh
Các loại graph
| Loại | Đặc điểm |
|---|---|
| Directed graph (Đồ thị có hướng) | Cạnh có hướng (A→B). |
| Undirected graph (Đồ thị vô hướng) | Cạnh không có hướng (A↔B). |
| Weighted Graph (Độ thị có trọng số) | Mỗi cạnh có một giá trị (khoảng cách, chi phí). |
| Unweighted Graph (Độ thị không có trọng số) | Các cạnh không có giá trị gắn kèm. |
Biểu diễn Graph
Adjacency Matrix (ma trận kề)
// A B C D
// 0 1 2 3
const matrix = [ [0, 1, 1, 0], // A [1, 0, 0, 1], // B [1, 0, 0, 0], // C [0, 1, 0, 0], // D
];
Dựa vào ma trận trên ta thấy:
- A kết nối với B, D (do
matrix[0][1]=1vàmatrix[0][2]=1). - B Kết nối với A, D.
Adjacency List (danh sách kề)
const graph = { A: ["B", "C"], B: ["A", "D"], C: ["A"], D: ["B"]
};
Ta thấy:
- A kết nối với B, C.
- B kết nối với A, D.
Khởi tạo
class Graph { adjacencyList; constructor() { this.adjacencyList = {}; }
}
Khởi tạo các method
addVertex
addVertex(vertex) { if (!this.adjacencyList[vertex]) { this.adjacencyList[vertex] = []; } }
addEdge
addEdge(v1, v2) { this.adjacencyList[v1].push(v2); this.adjacencyList[v2].push(v1); }
removeVertex
removeVertex(vertex) { while (this.adjacencyList?.[vertex]?.length) { const vertexIn = this.adjacencyList[vertex].pop(); this.removeEdge(vertex, vertexIn); } delete this.adjacencyList[vertex]; }
removeEdge
removeEdge(v1, v2) { this.adjacencyList[v1] = this.adjacencyList[v1]?.filter((v) => v !== v2); this.adjacencyList[v2] = this.adjacencyList[v2]?.filter((v) => v !== v1); }