Đồ thị & Tô màu
Welsh-Powell Graph Coloring
ID: #333
Xem trên trang chủ
Thời gian (Time)
O(V log V + V * E)
Không gian (Space)
O(V)
Mô tả nguyên lý
Tô màu các đỉnh đồ thị tham lam theo thứ tự bậc giảm dần để không trùng màu kề.
Cài đặt mẫu (Implementation)
// Sắp xếp đỉnh theo bậc giảm dần và lần lượt gán màu nhỏ nhất chưa bị các đỉnh kề sử dụng.
Đồ thị & Tô màu
Welsh-Powell Graph Coloring Greedy
ID: #283
Xem trên trang chủ
Thời gian (Time)
O(V log V + V * E)
Không gian (Space)
O(V)
Mô tả nguyên lý
Thuật toán tham lam tô màu các đỉnh đồ thị sao cho hai đỉnh kề nhau không trùng màu.
Cài đặt mẫu (Implementation)
// Sắp xếp các đỉnh theo thứ tự bậc giảm dần và lần lượt gán màu nhỏ nhất chưa bị các đỉnh kề sử dụng.