Tìm tài liệu

Tim cay khung co trong luong nho nhat bang giai thuat Prim

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

Upload bởi: ducmuoi2004

Mã tài liệu: 299535

Số trang: 16

Định dạng: zip

Dung lượng file: 333 Kb

Chuyên mục: Kỹ thuật - Công nghệ

Info

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.

Phần bên dưới chỉ hiển thị một số trang ngẫu nhiên trong tài liệu. Bạn tải về để xem được bản đầy đủ

  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Đang tải dữ liệu ...
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim
  • Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim

GỢI Ý

Những tài liệu gần giống với tài liệu bạn đang xem

Niên Luận Giải Thuật Prim

Upload: moneymoney1687

📎 Số trang: 30
👁 Lượt xem: 652
Lượt tải: 17

Tìm hiểu các giải thuật tìm đường đi ngắn ...

Upload: doandung1406

📎
👁 Lượt xem: 486
Lượt tải: 23

Giải thuật Gen và bài toán tìm đường đi ngắn ...

Upload: august_rain6884

📎
👁 Lượt xem: 735
Lượt tải: 32

Thuật toán Ford Fulkerson Tìm lượng cực đại ...

Upload: cophieuvip

📎 Số trang: 82
👁 Lượt xem: 1580
Lượt tải: 16

Thuật toán Ford Fulkerson Tìm lượng cực đại ...

Upload: ngocrubi90

📎 Số trang: 82
👁 Lượt xem: 411
Lượt tải: 16

Các thuật toán tìm đường đi ngắn nhất trong ...

Upload: elnino1306

📎
👁 Lượt xem: 630
Lượt tải: 23

Giải thuật di truyền giải bài toán cây ...

Upload: hiepphuongmai

📎 Số trang: 73
👁 Lượt xem: 453
Lượt tải: 3

Giải thuật di truyền giải bài toán cây ...

Upload: vubangck

📎 Số trang: 73
👁 Lượt xem: 15
Lượt tải: 10

Cài đặt bài toán Khớp đường cong bằng phương ...

Upload: god_sunshine_4490

📎 Số trang: 13
👁 Lượt xem: 473
Lượt tải: 16

Cây cân bằng avl

Upload: hoangn_tran

📎
👁 Lượt xem: 789
Lượt tải: 17

Gây mê vòng kín lưu lượng thấp bằng ...

Upload: nhocngamy

📎 Số trang: 67
👁 Lượt xem: 1002
Lượt tải: 16

Phương pháp đại số cho bài toán ước lượng ...

Upload: hai_fui

📎 Số trang: 76
👁 Lượt xem: 532
Lượt tải: 16

QUAN TÂM

Những tài liệu bạn đã xem

Tìm cây khung có trọng lượng nhỏ nhất bằng ...

Upload: ducmuoi2004

📎 Số trang: 16
👁 Lượt xem: 935
Lượt tải: 20

CHUYÊN MỤC

Kỹ thuật - Công nghệ
Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim 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 zip Đăng bởi
5 stars - 299535 reviews
Thông tin tài liệu 16 trang Đăng bởi: ducmuoi2004 - 01/08/2024 Ngôn ngữ: Việt nam, English
5 stars - "Tài liệu tốt" by , Written on 01/08/2024 Tôi thấy tài liệu này rất chất lượng, đã giúp ích cho tôi rất nhiều. Chia sẻ thông tin với tôi nếu bạn quan tâm đến tài liệu: Tìm cây khung có trọng lượng nhỏ nhất bằng giải thuật Prim