1. Graph Representation
1.1. Graph là gì?
Bạn hãy tưởng tượng một bản đồ giao thông: mỗi thành phố là một vertex (đỉnh), mỗi con đường nối hai thành phố là một edge (cạnh). Đó chính là graph!
Định nghĩa toán học: Graph G = (V, E) gồm:
- V (Vertices): tập hợp các đỉnh
- E (Edges): tập hợp các cạnh, mỗi cạnh nối hai đỉnh
Phân loại graph:
- Undirected Graph (đồ thị vô hướng): cạnh không có chiều, A-B nghĩa là đi được cả hai chiều
- Directed Graph (đồ thị có hướng): cạnh có chiều, A→B không có nghĩa là B→A
- 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 trọng số): các cạnh đều “bình đẳng”
Các khái niệm quan trọng:
- Degree (bậc): số cạnh nối tới một đỉnh. Trong directed graph có in-degree (bậc vào) và out-degree (bậc ra)
- Path (đường đi): dãy các đỉnh liên tiếp nối bởi các cạnh
- Cycle (chu trình): path mà đỉnh đầu trùng đỉnh cuối
- Connected (liên thông): mọi cặp đỉnh đều có path nối chúng
Công thức Euler cho đồ thị phẳng: V - E + F = 2, trong đó F là số mặt (faces).
Handshaking Lemma: Tổng bậc của tất cả các đỉnh = 2 × số cạnh. Tức là: Σ deg(v) = 2|E|.
1.2. Adjacency Matrix (Ma trận kề)
Ý tưởng: Dùng ma trận 2D kích thước V×V. Ô matrix[i][j] = 1 nếu có cạnh từ i đến j, = 0 nếu không.
Ví dụ thực tế: Giống như bảng khoảng cách giữa các thành phố mà bạn thấy trên bản đồ du lịch — hàng là thành phố xuất phát, cột là thành phố đến.
0123
Ma trận kề tương ứng:
0 1 2 3
0 [ 0, 1, 1, 0 ]
1 [ 1, 0, 1, 1 ]
2 [ 1, 1, 0, 1 ]
3 [ 0, 1, 1, 0 ]
class GraphMatrix:
"""Biểu diễn graph bằng adjacency matrix."""
def __init__(self, num_vertices):
self.V = num_vertices
# Khởi tạo ma trận V x V toàn số 0
self.matrix = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
"""Thêm cạnh u-v (undirected)."""
self.matrix[u][v] = weight
self.matrix[v][u] = weight # Bỏ dòng này nếu directed graph
def remove_edge(self, u, v):
"""Xóa cạnh u-v."""
self.matrix[u][v] = 0
self.matrix[v][u] = 0
def has_edge(self, u, v):
"""Kiểm tra cạnh u-v có tồn tại không."""
return self.matrix[u][v] != 0
def get_neighbors(self, v):
"""Lấy danh sách hàng xóm của đỉnh v."""
neighbors = []
for i in range(self.V):
if self.matrix[v][i] != 0:
neighbors.append(i)
return neighbors
def display(self):
"""In ma trận kề."""
print("Adjacency Matrix:")
for row in self.matrix:
print(row)
# === TEST ===
if __name__ == "__main__":
g = GraphMatrix(4)
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.display()
print(f"Hàng xóm của đỉnh 1: {g.get_neighbors(1)}")
print(f"Có cạnh 0-3 không? {g.has_edge(0, 3)}")
print(f"Có cạnh 1-2 không? {g.has_edge(1, 2)}")
Output:
Adjacency Matrix:
[0, 1, 1, 0]
[1, 0, 1, 1]
[1, 1, 0, 1]
[0, 1, 1, 0]
Hàng xóm của đỉnh 1: [0, 2, 3]
Có cạnh 0-3 không? False
Có cạnh 1-2 không? True
1.3. Adjacency List (Danh sách kề)
Ý tưởng: Mỗi đỉnh lưu một danh sách các đỉnh kề với nó. Tiết kiệm bộ nhớ hơn adjacency matrix rất nhiều khi graph thưa (sparse).
Ví dụ thực tế: Danh bạ điện thoại — mỗi người (đỉnh) có một danh sách bạn bè (các đỉnh kề).
from collections import defaultdict
class GraphList:
"""Biểu diễn graph bằng adjacency list."""
def __init__(self, directed=False):
self.adj = defaultdict(list)
self.directed = directed
def add_edge(self, u, v, weight=1):
"""Thêm cạnh u-v."""
self.adj[u].append((v, weight))
if not self.directed:
self.adj[v].append((u, weight))
def remove_edge(self, u, v):
"""Xóa cạnh u-v."""
self.adj[u] = [(node, w) for node, w in self.adj[u] if node != v]
if not self.directed:
self.adj[v] = [(node, w) for node, w in self.adj[v] if node != u]
def has_edge(self, u, v):
"""Kiểm tra cạnh u-v."""
return any(node == v for node, _ in self.adj[u])
def get_neighbors(self, v):
"""Lấy danh sách hàng xóm."""
return [node for node, _ in self.adj[v]]
def display(self):
"""In adjacency list."""
print("Adjacency List:")
for vertex in sorted(self.adj.keys()):
neighbors = [(n, w) for n, w in self.adj[vertex]]
print(f" {vertex} -> {neighbors}")
# === TEST ===
if __name__ == "__main__":
g = GraphList()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(1, 3)
g.add_edge(2, 3)
g.display()
print(f"Hàng xóm của đỉnh 1: {g.get_neighbors(1)}")
print(f"Có cạnh 0-3 không? {g.has_edge(0, 3)}")1.4. Edge List (Danh sách cạnh)
Ý tưởng: Đơn giản nhất — lưu tất cả các cạnh dưới dạng danh sách các tuple (u, v, weight). Thường dùng trong Kruskal’s algorithm.
class GraphEdgeList:
"""Biểu diễn graph bằng edge list."""
def __init__(self, num_vertices):
self.V = num_vertices
self.edges = []
def add_edge(self, u, v, weight=1):
"""Thêm cạnh."""
self.edges.append((u, v, weight))
def display(self):
"""In edge list."""
print("Edge List:")
for u, v, w in self.edges:
print(f" {u} -- {v} (weight: {w})")
# === TEST ===
if __name__ == "__main__":
g = GraphEdgeList(4)
g.add_edge(0, 1, 5)
g.add_edge(0, 2, 3)
g.add_edge(1, 2, 1)
g.add_edge(1, 3, 7)
g.add_edge(2, 3, 2)
g.display()1.5. So sánh các cách biểu diễn
| Tiêu chí | Adjacency Matrix | Adjacency List | Edge List |
|---|---|---|---|
| Bộ nhớ | O(V²) | O(V + E) | O(E) |
| Kiểm tra cạnh (u,v) | O(1) | O(degree(u)) | O(E) |
| Duyệt hàng xóm | O(V) | O(degree(v)) | O(E) |
| Thêm cạnh | O(1) | O(1) | O(1) |
| Xóa cạnh | O(1) | O(degree(v)) | O(E) |
| Graph thưa | Lãng phí nhớ | Tốt nhất | Tốt |
| Graph dày đặc | Tốt | OK | OK |
| Dùng khi nào | Graph nhỏ, cần check cạnh nhanh | Hầu hết mọi trường hợp | Kruskal, sắp xếp cạnh |
Lời khuyên: Trong 90% trường hợp, mình dùng adjacency list vì nó cân bằng giữa bộ nhớ và tốc độ. Adjacency matrix chỉ nên dùng khi graph nhỏ (V < 1000) hoặc cần kiểm tra cạnh O(1) liên tục. Edge list dùng khi cần sắp xếp cạnh theo trọng số (Kruskal).
🔬 Deep Diagnostic & Production Engineering Notes
1. In-Depth State Verification & Invariant Proofs
When deploying algorithms in high-throughput production environments:
- Loop Invariants: State preconditions must be strictly asserted before entering loops. Post-conditions guarantee deterministic state convergence.
- Memory Boundary Defense: Guard against off-by-one errors ( vs ), signed integer overflow (), and empty container operations.
- Asymptotic Amortization: Use aggregate analysis and potential functions to ensure operations maintain their promised average and worst-case bounds.
2. High-Performance Multi-Language Testing Harness
C++20 Micro-Benchmarking Suite
#include <iostream>
#include <vector>
#include <chrono>
#include <numeric>
void BenchmarkSuite(int iterations) {
auto start = std::chrono::high_resolution_clock::now();
long long checksum = 0;
for (int i = 1; i <= iterations; ++i) {
checksum += (i ^ (i << 1));
}
auto end = std::chrono::high_resolution_clock::now();
auto dur = std::chrono::duration_cast<std::chrono::microseconds>(end - start).count();
std::cout << "Executed " << iterations << " iterations in " << dur << " us. Checksum: " << checksum << "\n";
}Python 3.12 Verification Harness
import time
def verify_performance(iterations: int) -> int:
t0 = time.perf_counter_ns()
checksum = sum(i ^ (i << 1) for i in range(1, iterations + 1))
t1 = time.perf_counter_ns()
print(f"Verified {iterations} iterations in {(t1 - t0) / 1_000_000:.3f} ms. Checksum: {checksum}")
return checksumC# (.NET 8) Memory Profiling Harness
using System;
using System.Diagnostics;
public class BenchmarkRunner {
public static void Run(int iterations) {
long memoryBefore = GC.GetTotalMemory(true);
var sw = Stopwatch.StartNew();
long checksum = 0;
for (int i = 1; i <= iterations; i++) {
checksum += (i ^ (i << 1));
}
sw.Stop();
long memoryAfter = GC.GetTotalMemory(false);
Console.WriteLine($"[C# .NET 8] {iterations} iterations completed in {sw.ElapsedMilliseconds} ms. Memory delta: {memoryAfter - memoryBefore} bytes.");
}
}🔗 Graph-Linked Knowledge Base
- 📖 Subcategory Hub: 12_Graphs Overview