Download miễn phí Đề tài Giải thuật Prim



GIỚI THIỆU CHƯƠNG TRÌNH
 
Chương trình được thực hiện để đáp ứng các yêu cầu sau :
• Thực hiện các thao tác với đồ thị bằng chuột cũng như bằng phím như thêm hay xóa một đỉnh, thêm hay xóa một đỉnh, điều chỉnh giá trị trọng số, thay đổi vị trí của đỉnh
• Thực hiện các thao tác vào ra với file dữ liêu, vẽ đồ thị từ file dữ liệu.
• Xác định các bộ phận liên thông (nếu đồ thị không liên thông).
• Vẽ cây trọng lượng nhỏ nhất, vẽ đường đi ngắn nhất giữa hai đỉnh cho trước.
 


http://s1.liketly.com/flash/edoc/jh2i1fkjb33wa7b577g9lou48iyvfkz6-swf-2013-04-10-de_tai_giai_thuat_prim.Q7B7zqDplg.swf /tai-lieu/de-tai-ung-dung-tren-liketly-5952/
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí

Tóm tắt nội dung tài liệu:

từ khi những tư tưởng cơ bản của lý thuyết đồ thị được đề xuất thì việc giải các bài toán trên đã trở nên dễ dàng hơn, đặc biệt là một số bài toán có ứng dụng vào thực tế.
Một trong những bài toán trong thực tế ta thường gặp là: làm thế nào để xây dựn một hệ thống giao thông với chi phí thấp nhất; làm thế nào để tìm phương án vận chuyển hàng hóa với thời gian ngắn nhất hay với chi phí thấp nhất… và những bài toán trên có thể tìm ra lời giải dễ dàng bằng cách đưa về mô hình đồ thị.
Hiểu rõ và cài đặt được các thuật toán, cũng như tìm ra lời giải tối ưu cho một bài toán nào đó dựa trên những mô hình về đồ thị đã học là một yêu cầu không thể thiếu đối với sinh viên nghành Tin học. Tuy nhiên, trong giới hạn của đề tài, em không thể trình bày tất cả các thuật toán có liên quan đến đồ thị mà ở đây tui chỉ trình bày “Giải thuật Prim”. Đây cũng là nội dung chính của đề tài em đã chọn.
Mục tiêu:
Nắm vững các khái niệm về đồ thị, các cách biểu diễn đồ thị trên máy tính và tình liên thông.
Nắm vững thuật toán tìm kiếm trên đồ thị “Giải thuật Prim”.
Yêu cầu cần đạt:
Cập nhật dữ liệu: tạo file dữ liệu mới, diều chỉnh dữ liệu của file cũ.
Biểu diễn được đồ thị từ các file dữ liệu trên.
Kiểm tra tính liên thông và xác định bộ phận liên thông của đồ thị.
Xác định cây trọng lượng nhỏ nhất ( nếu đồ thị liên thông), ngược lại thì báo đồ thị không liên thông. Xác định đường đi ngắn nhất giữa hai đỉnh của một đồ thị (nếu hai đỉnh thuộc cùng một bộ phận liên thông), ngược lại thông báo không tìm thấy đường đi.
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ữ Visual Basic .Net ( Visual Basic 2008) để viết chương trình, cài đặt thuật toán cũng như thực hiện các yêu cầu vẽ biểu diễn đồ thị trên màn hình đồ họa.
Nội dung của Niên luận 1 được chia thành ba phần cụ thể như sau:
Phần I: Cơ sở lý thuyết
Chương 1: Một số khái niệm cơ bản về lý thuyết đồ thị:
Trong chương này sẽ giới thiệu cho chúng ta nắm được một số khái niệm cơ bản về đồ thị cũng như một số khái niệm có liên quan.
Chương 2: Tìm kiếm trên đồ thị:
Giới thiệu cho chúng ta một số phương pháp tìm kiếm trên đồ thị như tìm theo chiều rộng, tìm theo chiều sâu…
Chương 3: Giải quyết một số bài toán bằng đồ thị:
Nội dung chương này sẽ trình bày một số bài toán trong thực tế được đưa về đồ thị và các giải thuật để giải các bài toán đó.
Phần II: Chương trình minh họa
Chương 1: Giới thiệu chương trình:
Chương này sẽ giới thiệu cho chúng ta biết về ngôn ngữ sử dụng để lập trình cũng như cách tổ chức dữ liệu của chương trình.
Chương 2: Phân tích giải thuật và cài đặt chương trình:
Phân tích lại một số giải thuật và cài đặt chương trình.
Chương 3: Hướng dẫn sử dụng:
Hướng dẫn sử dụng chương trình và thực hiện một số
ví dụ minh họa.
Phần III: Kết luận và đánh giá
Đánh giá những kết quả đã đạt được cũng như các hạn chế và
đưa ra hướng phát triển của Niên Luận 1.
Dù không tránh khỏi những khiếm khuyết do hạn chế về mặt thời gian cũng
như kiến thức nhưng em đã nỗ lực hết sức. Sau hơn 1 tháng thực hiện, Niên luận 1 của em đã hoàn thành, đáp ứng được các yêu cầu của đề tài và đã cố gắng phát triển đề tài này trong phạm vi có thể. Em rất mong nhận được những ý kiến đóng góp quý báu của quý thầy cô và bạn bè để đề tài này được hoàn thiện hơn.
PHẦN 1
CƠ SỞ LÝ THUYẾT
Chương 1: Một số khái niệm về lý thuyết đồ thị 4
Chöông 2 : Caùc thuaät toaùn tìm kieám treân ñoà thò 8
Chương 3 : Giải quyết các bài toán bằng đồ thị 10
Chương I : MỘT SỐ KHÁI NIỆM
VỀ LÝ THUYẾT ĐỒ THỊ
I.1. MỘT SỐ KHÁI NIỆM VỀ ĐỒ THỊ :
I.1.1 Đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Ký hiệu: G=(V,E)
Trong đó : V : tập các đỉnh của đồ thị
E : tập các cạnh của đồ thị
Chúng ta phân biệt các loại đồ thị khác dựa trên 2 tiêu chuẩn :
Kiểu .
Số lượng cạnh nối 2 đỉnh nào đó của đồ thị.
Trong phần này chúng ta đề cập đến hai loại đồ thị :
Đồ thị có hướng .
Đồ thị vô hướng .ư
Ví dụ. Hình I.1 là một số dạng đồ thị
Hình I.1 biểu diễn đồ thị vô hướng (a) và đồ thị có hướng (b)
a
b
4
3
2
1
5
4
3
2
1
5
I.1.2. Đồ thị vô hướng :
Đồ thị vô hướng G = (V, E) bao gồm :
V là đỉnh của đồ thị .
E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi la các cạnh, tức là (u, v) = (v,u).
Ví dụ: Đồ thị Hình I.1 a là một đồ thị vô hướng với :
Tập hợp các đỉnh : [ 1, 2, 3, 4, 5 ]
Tập các cạnh : [ (1,4), (1,5), (2,4), (2.5), (3,4), (3,2) ]
I.1.3 Đồ thị có hướng :
Đồ thị có hướng G = ( V, E ) bao gồm :
V là tập các đỉnh của đồ thị
E là tập các cặp có thứ tự gồm hai phần tử khác nhau thuộc V được gọi là các cung, tức là (u,v) ¹ (v,u). Cung (u,v) được gọi là cung đi từ đỉnh u đến đỉnh v, ký hiệu : u à v .
Ví dụ: Đồ thị Hình I.1b là một đồ thị có hướng với :
Tập các đỉnh : { 1, 2, 3, 4, 5}
Tập các cung : {(1,5), (2,5), (3,5), (4,1), (4,2)}.
Trong giới hạn của đề tài, từ đây về sau khi nói đến đồ thị thì chúng ta sẽ hiểu đố là đồ thị vô hướng.
I.2. ĐƯỜNG ĐI VÀ TÍNH LIÊN THÔNG
I.2.1 Đường đi và chu trình :
Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, tên đồ thị ( có hướng ) G = (V,E) là dãy : x0, x1, x2, …, xn-1, xn.
Trong đó u=x0, v=xn, (xi, xi+1) Î E, i = 0, 1, 2, …, n-1.
Chu trình là đường đi có đỉnh đầu trùng đỉnh cuối .
Ví dụ: Xét đồ thị trong hình I.1a :
1, 5, 2, 4, 3 : là đường đi độ dài 5 đỉnh 1 đến đỉnh 3.
1, 4, 2 , 5,1 : là một chu trình.
1, 3, 2, 5 : không là đường đi vì (1, 3) không phải là cạnh của đồ thị ( không thuộc E).
I.2.2. Tính liên thông :
Đồ thị có hướng G = (V, E) được gọi là liên thông nếu tìm được đường đi giữa hai đỉnh bất kỳ của nó.
I.2.3. Cây và cây khung:
Cây là đồ thị vô hướng liên thông không có chu trình.
Giả sử đồ thị G =(V, E) là đồ thị liên thông. Cây T =(V, F)với F Ì E được gọi là cây khung của đồ thị G.
Hình I.2 : biểu diễn đồ thị vô hướng a và cây khung b, c
(a)
4
3
2
1
5
(c)
4
3
2
1
5
(b)
4
3
2
1
5
Ví dụ: Đồ thị hình I.2a có cây khung hình I.2b, I.2c
I.3. BIỂU DIỄN ĐỒ THỊ TRONG MÁY TÍNH
Để cài đặt các giải thuật và giải quyết các bài toán về đồ thị bằng máy tính, chúng ta cần tìm những cấu truc dữ liệu thích hợp để biểu diễn đồ thị. Việc chọn một loại cấu trúc nào đó để biểu diễn đồ thị có ảnh hưởng rất lớn đến hiệu quả thực hiện của thuật toán, vì vậy việc chọn lựa một loại cấu trúc dữ liệu để biểu diễn đồ thị phải dựa vào từng tình huống cụ thể của bài toán.
Có rất nhiều phương pháp để biểu diễn một đồ thj bằng cấu trúc dữ liệu như: dùng ma trận kề, dùng ma trận trọng số, dùng danh sách liên kết, danh sách cạnh…
Tuy nhiên, việc dùng danh sách liên k

---