Báo Cáo Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim

TÊN ĐỀ TÀI: Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim

Information

[TABLE]

[TR]

[TD="width: 5%"][/TD]

[TD="width: 90%"]

NHẬN XÉT CỦA GIÁO VIÊN 2

MỤC LỤC 3

TỔNG QUAN 4

I. Các mục tiêu cần đạt được 4

II. Hướng giải quyết 4

III. Kế họach thực hiện 5

LÝ THUYẾT 6

I. Các khái niệm chính 6

II. Các cách biểu diễn đồ thị 7 III. Duyệt các đỉnh của đồ thị 8

IV .Giải thuật Prim 8

Ứng Dụng 10

I. Lưu đồ giải thuật Prim 10

II. Lưu đồ duyệt cây theo chiều sâu tại đỉnh i 11

III. Lưu đồ duyệt cây theo chiều rộng tại đỉnh i 11

IV. Giới thiệu chương trình 12

KẾT LUẬN- ĐÁNH GIÁ 16

I. Kết quả đạt được 16

II. Hạn chế của chương trình 16

III. Hướng phát triển. 16

PHỤ LỤC 17

Hướng dẫn sử dụng 17

Các tài liệu tham khảo 17

















TỔNG QUAN



Tìm cây bao trùm nhỏ nhất (tiếng Anh: minimum spanning tree) là bài tốn tối ưu có nhiều ứng dụng trong thực tế. Nó là bài tốn tìm hệ thống liên thông với chi phí nhỏ nhất. Hai thuật tốn tìm cây bao trùm nhỏ nhất thường được nhắc đến là thuật tốn Prim và thuật tốn Krusskal.

Cho G=(X,E) là một đồ thị liên thông. Ngồi ra, một hàm trọng số W(e), xác định trên tập các cạnh E của G. Cả hai thuật tốn Prim và Kruskal đều dựa trên tư tưởng của các giải thuật tham ăn : Ở mỗi bước của thuật tốn ta chọn và bổ sung vào cây cạnh có trọng số nhỏ nhất có thể. Ở đây ta chỉ đề cập đến thuật tốn Prim

Giải thuật Prim

Vài nét về R. C. Prim

Robert Clay Prim (sinh 1921 tại Sweetwater, Texas) là một nhà tốn học và khoa học máy tính Mỹ. Năm 1941 ông đã lấy bằng cử nhân ở khoa kỹ thuật điện đại học Princeton. Sau này năm 1949, ông nhận bằng Ph.D. về tốn học cũng tại đây. Giải thuật mang tên Prim được tìm ra từ năm 1930 bởi nhà tốn học Vojtěch Jarník và do Prim hồn thiện vào năm 1957. asd

Mô tả

Gọi T là cây bao trùm sẽ xây dựng

1. Chọn một đỉnh s bất kỳ của G cho vào cây T. Khi đó T là một cây chỉ có một đỉnh và chưa có cạnh nào.

2. Nếu T đã gồm tất cả các đỉnh của G thì T là cây bao trùm cần tìm. Kết thúc.

3. Nếu G còn có các đỉnh không thuộc T, vì G liên thông nên có các cạnh nối một đỉnh trong T với một đỉnh ngồi T, chọn một cạnh có trọng số nhỏ nhất trong số đó cho vào T.

4. Quay lại 2.



I. Các mục tiêu cần đạt được:



- Dữ liệu được nhập từ bàn phím là một ma trận trọng số.

- Thiết kế giải thuật Prim và xuất ra màn hình cây khung có trọng lượng nhỏ nhất.



II. Hướng giải quyết:

- Viết chương trình nhập vào 1 ma trận trọng số.

- Sử dụng giải thuật Prim để tìm được cây khung có trọng lượng nhỏ nhất.

- Xuất ra màn hình đồ họa các bước trong trong giải thuật Prim.[/TD]

[/TR]

[/TABLE]