Mô phỏng quá trình tìm cây khung nhỏ nhất theo thuật toán PRIM
Mô phỏng quá trình tìm cây khung nhỏ nhất theo thuật toán PRIM
TÊN ĐỀ TÀI: MÔ PHỎNG QUÁ TRÌNH TÌM CÂY KHUNG NHỎ NHẤT THEO THUẬT TOÁN PRIM
MỤC LỤC……...................................…………………….1
Lời nói đầu…………………………………………………2
Chương 1. Tổng quan về bài toán cây khung nhỏ nhất…3
1. Cây khung của đồ thị……………………………………..3
2. Bài toán cây khung nhỏ nhất……………………………...3
3. Các thuật toán tiêu biểu để tìm cây khung nhỏ nhất………4
3.1 Thuật toán Kruskal………………………………………4
3.2 Thuật toán Prim………………………………………….4
Chương 2. Thuật toán Prim…….……………………….....5
1. Ý tưởng thuật toán…………………………………………5
2. Cài đặt chương trình ………………………………………16
Chương 3. Ứng dụng thực tế của thuật toán………………14
Lời nói đầu…………………………………………………2
Chương 1. Tổng quan về bài toán cây khung nhỏ nhất…3
1. Cây khung của đồ thị……………………………………..3
2. Bài toán cây khung nhỏ nhất……………………………...3
3. Các thuật toán tiêu biểu để tìm cây khung nhỏ nhất………4
3.1 Thuật toán Kruskal………………………………………4
3.2 Thuật toán Prim………………………………………….4
Chương 2. Thuật toán Prim…….……………………….....5
1. Ý tưởng thuật toán…………………………………………5
2. Cài đặt chương trình ………………………………………16
Chương 3. Ứng dụng thực tế của thuật toán………………14
Kết luận………………………………………………………20
Chương 1. Tổng quan về bài toán cây khung nhỏ nhất1. Cây khung của đồ thịCây là một đồ thị vô hướng liên thông, không chứa chu trình và có ít nhất hai đỉnh. Một đồ thị vô hướng không chứa chu trình và có ít nhất hai đỉnh gọi là một rừng (hợp của nhiều cây). Trong một rừng, mỗi thành phần liên thông là một cây.
......
Nhận xét