zunia.vn

Tuyển sinh 2024 dành cho Gen-Z

zunia.vn

» Công Nghệ Thông Tin

» Kỹ thuật lập trình

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

Báo xấu

82
lượt xem 9
download

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ủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

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

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
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

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN

TRỢ GIÚP

HỖ TRỢ KHÁCH HÀNG

Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.