TAILIEUCHUNG - Thuật toán Prim – Tìm cây khung có trọng số nhỏ nhất

Thuật toán Prim Cho G = (X, E) là một đồ thị liên thông có trọng số gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung nhỏ nhất của G. | Thuật toán Prim - Tìm cây khung có trọng số nhỏ nhất cây bao trùm nhũ nhất của đồ thị mặt phang. 3 Thuật toán Prim Cho G X E là một đồ thị liên thông có trọng số gồm n đỉnh. Thuật toán Prim được dùng để tìm ra cây khung nhỏ nhất của G. Bước 1 Chọn tùy ý x0 thuộc X và khởi tạo V x0 T 0. Trong đó X là tập các đỉnh của đồ thị V là tập các đỉnh được chọn vào cây khung nhỏ nhất và T là tập các cạnh của cây này. Bước 2 Trong số những cạnh nối đỉnh x với đỉnh y mà x E V và y E X V ta chọn cạnh e có trọng số nhỏ nhất. Nếu không có cạnh e thỏa yêu câu DỪNG 1 Bước 3 Thêm đỉnh y vào tập V và thêm cạnh e vào tập T. Bước 4 Nếu T đủ n - 1 phần tử thì DỪNG 2 ngược lại làm tiếp tục bước 2. Ghi chú Khi thuật toán dừng theo trường hợp 1 tìm không có cạnh từ V đi ra thì đồ thị không liên thông nên không có cây khung và do đó cũng không có cây khung nhỏ nhất. Cài đặt thuật toán Prim Trong các thuật toán tìm cây khung ngắn nhất chúng ta có thể bỏ đi hướng các cạnh và các khuyên đối với các cạnh song song thì có thể bỏ đi và chỉ để lại một cạnh trọng số nhỏ nhất trong chúng. Vì vậy dữ liệu nhập cho thuật toán thường là ma trận trọng số L được quy ước như sau Lij Trọng lượng cạnh nhỏ nhất nối i đến j nếu có Lij 0 nếu không có cạnh nối i đến j Ma trận có thể tổ chức bằng mảng 2 chiều tĩnh hoặc động trong bộ nhớ. Tập V có thể tổ chức bằng một mảng 1 chiều tĩnh hoặc động lưu các đỉnh hoặc là một mảng dùng để dánh dấu theo kiểu hàm đặc trưng V i 1 nếu i thuộc V và V i 0 nếu ngược lại . Bài tập Sử dụng thuật toán Prim để tìm cây khung nhỏ nhất trong đồ thị vô hướng có trọng số. Cấu trúc file dữ liệu đầu vào Dòng đầu tiên số đỉnh đồ thị N N dòng tiếp theo ma trận kề của đồ thị với quy ước A i j W trọng số của đường nối trực tiếp từ i đến j A i j 0 không có đường nối trực tiếp từ i đến j Các đỉnh được đánh chỉ số từ 0 Cấu trúc file dữ liệu đầu ra Nếu tìm được cây khung nhỏ nhất Dòng đầu chứa số nguyên k là trọng lượng cây khung cực tiểu Dòng tiếp theo là các cạnh u v thuộc cây khung này Nếu .

Nhật Hồng 159 8 pdf

Upload

Bấm vào đây để xem trước nội dung

Tải xuống

TÀI LIỆU LIÊN QUAN

Tổng quan về ứng dụng công nghệ thông tin - truyền thông trong giáo dục

3 401 8

Mô tả công việc Giám đốc công nghệ thông tin

2 390 0

Luận văn: Tính toán hiệu quả chuyển giao công nghệ thông tin thông qua thị trường tin học

76 278 3

Công nghệ thông tin và ứng dụng công nghệ thông tin trong dạy học

8 386 15

Chương trình giáo dục Đại học theo học chế tín chỉ ngành: Công nghệ thông tin

28 289 0

Quyết định 995/QĐ-BTC năm 2013

5 277 0

Bài giảng Chương 2 - Thiết kế và quản lý dự án Công nghệ thông tin - PGS.TS Nguyễn Văn Định

26 310 1

Bài giảng Đại cương Công nghệ thông tin và truyền thông - ThS. GV. Phạm Quang Quyền

118 287 3

Giáo trình Tiếng Anh chuyên ngành Công nghệ thông tin

47 1247 85

Ebook Tìm hiểu Luật Công nghệ thông tin và các Nghị định hướng dẫn thi hành - NXB Bưu điện

74 359 6

TÀI LIỆU XEM NHIỀU

Một Case Về Hematology (1)

8 461857 55

Giới thiệu :Lập trình mã nguồn mở

14 22603 58

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10882 529

Câu hỏi và đáp án bài tập tình huống Quản trị học

14 10049 445

Phân tích và làm rõ ý kiến sau: “Bài thơ Tự tình II vừa nói lên bi kịch duyên phận vừa cho thấy khát vọng sống, khát vọng hạnh phúc của Hồ Xuân Hương”

3 9513 104

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8268 1124

Tiểu luận: Nội dung tư tưởng Hồ Chí Minh về đạo đức

16 8224 423

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7862 2220

Đề tài: Dự án kinh doanh thời trang quần áo nữ

17 6669 253

Vật lý hạt cơ bản (1)

29 5765 85

TỪ KHÓA LIÊN QUAN

TÀI LIỆU MỚI ĐĂNG

Bibliography on Medieval Women, Gender, and Medicine 1980-2009

82 207 0 24-04-2024

Trading Strategies Profit Making Techniques For Stock_3

23 183 0 24-04-2024

Bơm máy nén quạt trong công nghệ part 1

20 249 2 24-04-2024

Magnetic Bearings Theory and Applications phần 2

14 170 0 24-04-2024

TƯƠNG QUAN GIỮA MÔ HỌC, GIẢI PHẪU VÀ HÌNH ẢNH CỦA CÁC KHỐI U PHẦN PHỤ

3 167 0 24-04-2024

Bơm máy nén quạt trong công nghiệp part 8

20 198 2 24-04-2024

Công nghiệp gang thép Việt Nam : Một giai đoạn phát triển và chuyển đổi chính sách mới part 5

6 194 0 24-04-2024

THE ANTHROPOLOGY OF ONLINE COMMUNITIES BY Samuel M.Wilson and Leighton C. Peterson

19 138 0 24-04-2024

báo cáo hóa học:" Endoscopic decompression for intraforaminal and extraforaminal nerve root compression"

7 107 0 24-04-2024

Data Structures and Algorithms - Chapter 9: Hashing

54 113 0 24-04-2024

TÀI LIỆU HOT

Mẫu đơn thông tin ứng viên ngân hàng VIB

8 7862 2220

Giáo trình Tư tưởng Hồ Chí Minh - Mạch Quang Thắng (Dành cho bậc ĐH - Không chuyên ngành Lý luận chính trị)

152 5678 1349

Ebook Chào con ba mẹ đã sẵn sàng

112 3757 1230

Ebook Tuyển tập đề bài và bài văn nghị luận xã hội: Phần 1

62 5309 1135

Ebook Facts and Figures – Basic reading practice: Phần 1 – Đặng Tuấn Anh (Dịch)

249 8268 1124

Giáo trình Văn hóa kinh doanh - PGS.TS. Dương Thị Liễu

561 3489 642

Tiểu luận: Tư tưởng Hồ Chí Minh về xây dựng nhà nước trong sạch vững mạnh

13 10882 529

Giáo trình Sinh lí học trẻ em: Phần 1 - TS Lê Thanh Vân

122 3678 525

Giáo trình Pháp luật đại cương: Phần 1 - NXB ĐH Sư Phạm

274 4040 514

Bài tập nhóm quản lý dự án: Dự án xây dựng quán cafe

35 4120 480