Đồ thị & Tô màu

Danh sách đầy đủ các thuật toán trong nhóm (Tổng: 2)

Đồ thị & Tô màu

Welsh-Powell Graph Coloring

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

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.