intTypePromotion=1

Tài liệu hướng dẫn thực hành Bài toán tô màu

Chia sẻ: Huy Đạt | Ngày: | Loại File: PDF | Số trang:2

0
68
lượt xem
7
download

Tài liệu hướng dẫn thực hành Bài toán tô màu

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Thuật toán Bước 1. Tìm đỉnh k có bậc cao nhất và chưa được tô. Bước 2. Nếu không tìm được k thì dừng, ngược lại qua bước 2. Bước 2. Tô màu m cho đỉnh k (m là màu nhỏ nhất chưa bị cấm khi tô đỉnh k). Bước 3. Hạ bậc các đỉnh có cung nối với k. Bước 4. Quay lại bước 1.

Chủ đề:
Lưu

Nội dung Text: Tài liệu hướng dẫn thực hành Bài toán tô màu

  1. Tài liệu hướng dẫn thực hành BÀI TOÁN TÔ MÀU Văn Chí Nam – Nguyễn Đức Hoàng Hạ Lu Boun Vinh – Nguyễn Anh Tuấn Khoa Công nghệ Thông tin, trường ĐH Khoa học Tự nhiên TP.HCM Phiên bản cập nhật ngày 18/10/2004 Thuật toán Bước 1. Tìm đỉnh k có bậc cao nhất và chưa được tô. Bước 2. Nếu không tìm được k thì dừng, ngược lại qua bước 2. Bước 2. Tô màu m cho đỉnh k (m là màu nhỏ nhất chưa bị cấm khi tô đỉnh k). Bước 3. Hạ bậc các đỉnh có cung nối với k. Bước 4. Quay lại bước 1. Cấu trúc dữ liệu đề nghị1 typedef struct { int Bac; int MauTo; int MauCam[MAXMAU]; }DINH; DINH D[MAX]; int n; int A[MAX][MAX]; Ý nghĩa: Bac: bậc của đỉnh MauTo: nếu MauTo = -1 thì đỉnh chưa được tô. Ngược lại đỉnh được tô bằng MauTo. MauCam[]: - MauCam[i] = 0: đỉnh không bị cấm tô màu i. - MauCam[i] = 1: đỉnh bị bị cấm tô màu i. D[]: Mảng các đỉnh. n: số đỉnh. A[][]: Ma trận kề biểu diễn quan hệ giữa các đỉnh. 1 Cấu trúc dữ liệu nêu trong bài viết này chỉ là cấu trúc dữ liệu đơn giản để cài đặt cơ bản thuật toán. Có thể tự đề nghị cấu trúc dữ liệu thích hợp để giải quyết bài toán. 1
  2. Tài liệu hướng dẫn thực hành Các hàm thực hiện chính Hàm khởi tạo các biến void KhoiTao(DINH D[MAX], int n) { Khởi tạo cho mỗi đỉnh i: Tính D[i].Bac D[i].MauTo = -1 D[i].MauCam[j] = 0 , j = 0 .. MAXMAU } Hàm tìm đỉnh bậc lớn nhất chưa tô int DinhBacMax(DINH D[MAX], int n) { Trả về đỉnh có bậc lớn nhất chưa tô. } Hàm tô màu 1 đỉnh void ToMau1Dinh(DINH D[MAX], int n, int i, int A[MAX][MAX]) { m là màu nhỏ nhất mà D[i].MauCam[m]=0 Tô màu đỉnh i: D[i].MauTo = m Hạ bậc và cấm tô màu m các đỉnh có quan hệ với i. } Hàm tô màu các đỉnh void ToMau(DINH D[MAX], int n, int A[MAX][MAX]) { KhoiTao(...) while (còn đỉnh chưa tô) { k = đỉnh chưa tô có bậc lớn nhất. Tô màu đỉnh k. } } Mở rộng - Áp dụng kết hợp với phương pháp Greedy. - Cải tiến cài đặt cho trường hợp đồ thị lớn (n>200). - Cài đặt giao diện cho ứng dụng. 2
ADSENSE
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

 

Đồng bộ tài khoản
2=>2