Tiểu Luận Tìm cây khung nhỏ nhất bằng giải thuật Kruscal viết bằng C++ có đồ họa chi tiết

MỤC LỤC
Tổng quan 4

Phần I: CƠ SỞ LÝ THUYẾT
Chương 1: Một số khái niệm về lý thuyết đồ thị . 5
1.1. Một số khái niệm về đồ thị . 5
1.1.1. Đồ thị 5
1.1.2. Đồ thị có hướng . 5
1.1.3. Đồ thị vô hướng . 6
1.2. Tính liên thông của đồ thị . 6
1.2.1. Đường đi và chu trình 6
1.2.2. Đồ thị liên thông - Bộ phận liên thông . 6
1.3. Biểu diển đồ thị trong máy tính
Dùng ma trận kề Đỉnh – Đỉnh . 7
Chương 2: Khái niệm về cây khung và tìm cây khung nhỏ nhất . 8
1.1. Cây khung của đồ thị . 8
1.2. Các phương pháp xây dựng cây khung 8
1.3. Bài toán tìm cây khung nhỏ nhất 9
1.4. Thuật toán tiêu biểu để tìm cây khung nhỏ nhất 10
Chương 3: Thuật toán Kruscal . 11
1. Nội dung thuật toán 11
2. Lưu đồ thuật toán . 14
3. Mô tả bằng ngôn ngữ giả 15

Phần II: CHƯƠNG TRÌNH DEMO 16
Chương 1: Giới thiệu chương trình . 16
Chương 2: Cài đặt demo 17
1. Tổ chức dữ liệu . 17

Phần III: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN . 19

Phụ Lục HƯỚNG DẪN SỬ DỤNG 20

Tài liệu tham khảo . 27

TỔNG QUAN

Trong cuộc sống, người ta luôn phải tính toán làm thế nào để công việc của mình đạt hiệu quả cao nhất. Ví dụ: người giao hàng phải tính làm sao để thời gian chuyển hàng là nhanh nhất hay với chi phí thấp nhất, hoặc xây dựng hệ thống đường một chiều trong thành phố mà vẩn đảm bảo lưu thông giữa hai nút giao thông bất kì
Ngày nay, với việc ứng dụng lý thuyết đồ thị, những vấn đề trên trở nên đơn giản hơn. Đối với sinh viên ngành Tin Học, việc tìm hiểu, nghiên cứu một số bài toán lý thuyết đồ thị ứng dụng trong Tin Học là rất cần thiết. Tuy nhiên, trong giới hạn của đề tài này, chỉ trình bày một số khái niệm liên quan đến lý thuyết đồ thị và phương pháp tìm cây khung có trọng số nhỏ nhất bằng giải thuật Kruscal.

Mục tiêu:
· Về lí thuyết: Nắm vững một số khái niệm đồ thị, tính liên thông của đồ thị, biểu diễn đồ thị trên máy tính, giải thuật tìm cây có trọng số nhỏ nhất. Các thao tác về đồ họa, các hàm, lệnh và cấu trúc dữ liệu của ngôn ngữ lập trình C++.
· Về chương trình: Vận dụng kiến thức về đồ thị, về ngôn ngữ lập trình để nhập dữ liệu đồ thị vào máy tính, biểu diễn đồ thị trên màn hình và tìm kiếm cây khung nhỏ nhất dựa trên nội dung của giải thuật Kruscal.
Yêu cầu về chương trình:
· Nhập, xuất dữ liệu: Đọc dữ liệu nhập vào từ bàn phím và xuất kết quả lên màn hình.
· Biểu diễn đồ thị: Vẽ đồ thị bằng đồ họa trên màn hình với các thông số rõ ràng, chi tiết, minh họa từng cạnh được lựa chọn để đưa vào cây khung nhỏ nhất.
· Kết quả: In nội dung đầu vào của người sử dụng đã nhập. In các cạnh cùng với trọng số và tổng trọng số của cây khung nhỏ nhất (kèm hình ảnh) trên màn hình. Thật sinh động và đầy đủ.
Hướng giải quyết:
· Về lí thuyết: Tìm hiểu các khái niệm về đồ thị, giải thuật được yêu cầu trong đề tài.
· Về chương trình: sử dụng ngôn ngữ lập trình C++ để giải quyết bài toán.

VUi lòng liên hệ với tác giả để nhận đầy đủ source code của chương trình!