Đề tài Giải thuật Prim

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 tôi 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 phải 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ết và danh sách cạnh để biểu diễn cho đồ thị vô hướng tỏ ra không hiệu quả trong việc tìm kiếm các đỉnh, cạnh cũng như trong việc them hay xóa một đỉnh ( hoặc một cạnh) ra khỏi đồ thi. Vì vậy, trong phần này chúng ta chỉ xét hai phương pháp biểu diễn đồ thj trên máy tính bởi các cấu trúc dữ liệu : Dùng ma trận kề. Dùng ma trận trọng số. I.3.1. Biểu diễn ma trận bởi ma trận kề : Được dùng để biểu diễn cho đồ thị không có trọng số. Trong cách biểu diễn này, đồ thị vô hướng G =(V, E) với tập các đỉnh V = {1, 2, …, n} và tập các cạnh E ={e1, e2, …, em}sẽ được lưu trữ trong một mảng hai chiều A = [1..n,1..n] A[i,j] = 0 nếu (i,j) Ï E 1 nếu (i,j) Î E " i,j = 1,n Trong đó : Mảng A như trên được gọi là ma trận kề của đồ thị. Ta nhận thấy trong đồ thị vô hướng canh (i,j) và cạnh (j,i) biểu diễn cho cùng một cạnh của đồ thị nên ma trận kề của đồ thị vô hướng là ma trận đối xứng qua đường chéo chính. Ví dụ: Đồ thị trong hình I.3a được biểu diễn bởi ma trận kề trong hình I.3b ( a ) ( b ) 4 3 2 1 5 A = 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 1 1 0 0 1 1 0 0 0 Hình I.3 biểu diễn đồ thị bằng ma trận kề  I.3.2. Biểu diễn đồ thị bởi ma trận trọng số : Được dùng để biểu diễn cho đồ thị có trọng số. Tương tự như trong cách biểu diễn đồ thị bằng ma trận kề, để biểu diễn cho đồ thị vô hướng G= (V,E) với tập đỉnh V = {1, 2, …,n} và tập cạnh E = {e1, e2, …, em}, trong đó mỗi cạnh có một giá trị (trọng số), cũng được lưu trữ bằng một mảng hai chiều A = [1..n,1..n] với : A[i,j] = w nếu (i,j) Î E q nếu (i,j) Ï E " i,j = 1,n Mảng A như trên được gọi là ma trận trọng số của đồ thị. Trong đó,q có thể có giá trị 0, +¥, -¥ tùy thuộc từng trường hợp cụ thể. Giá trị A[i,j] = w, w Î (0,+¥), được gọi là trọng số của cạnh e. Ví dụ: Đồ thị trong hình I.4 được biểu diễn bởi ma trận kề trong hình I.4b ( b ) A = 0 0 0 3 7 0 0 12 5 15 0 12 0 13 0 3 5 13 0 0 17 3 0 0 0 ( a ) 4 3 2 1 5 13 5 3 7 15 12 Hình I.4 biểu diễn ma trận có trọng số Chương 2 TÌM KIẾM TRÊN ĐỒ THỊ Có rất nhiều thuật toán về đồ thị được xây dựng trên cơ sở duyệt tất cả các đỉnh sao cho mỗi đỉnh của đồ thị chỉ được xét (ghé thăm) đúng một lần. Những thuật toán được xây dựng dựa trên cơ sỏ nêu trên được gọi là các thuật toán tìm kiếm trên đồ thị, các thuật toán này có vai trò quan trọng việc thiết kế các thuật toán khác trên đồ thị như tìm đường đi ngắn nhất, tìm cây trọng lượng nhỏ nhất … Trong chương này ta sẽ đề cập đến ba thuật toán tìm kiếm cơ bản thường được sử dụng trên đồ thị là : Thuật toán tìm kiếm theo chiều sâu - (Depth First Search - DFS) . Thuật toán tìm kiếm theo chiều rộng- (Breadth First Search - DFS) . Tìm số thành phần liên thông . II.1. TÌM KIẾM THEO CHIỀU SÂU : (Depth First Search - DFS) Ý tưởng của thuật toán này có thể được trình bày như sau : Ta sẽ bắt đầu tìm từ một đỉnh vo nào đó của đồ thị, sau đó chọn u là một đỉnh tùy ý kề với vo và lặp lại quá trình trên với đỉnh u. Tại bước tổng quát ta đang xét đỉnh v. Nếu trong số các đỉnh kề của v ta tìm được một đỉnh w là chưa xét thì ta sẽ xét đỉnh này ( đặt w là đỉnh đã xét) và từ đó tiếp tục quá trình tìm kiếm, ngược lại nếu không còn đỉnh nào kề với v là đỉnh chưa xét thì ta sẽ quay lại tìm kiếm từ đỉnh mà trước đó ta đến được đỉnh v, khi đó đỉnh v được gọi là đỉnh đã duyệt xong. Việc tìm kiếm được dừng lại khi gặp lại đỉnh xuất phát và không thể đi sâu được nữa ( khi đỉnh xuất phát là đỉnh đã duyệt xong). Thuật toán DFS được mô tả trong thủ tục sau : Procedure DFS(v); Begin Chuaxet[v] := false; Ví dụ xét đồ thị hình II.1 Đỉnh xuất phát: đỉnh A Với thuật toansDFS thứ tự các đỉnh lần lượt được xét là : A, B, D, E, G, H, I, C, F Hoặc: A, C, F, B, E, G, H, I, D … … … A F C D B G I H E Hình I.1 For u Î Ke(v) do If chuaxet[u] then DFS(u); End; II.2. TÌM KIẾM THEO CHIỀU RỘNG : (Breadth First Search - BFS) Trong thuật toán tìm kiếm theo chiều sâu, ta chọn một đỉnh v và thăm đỉnh đó ( đặt v là đỉnh đã xét và đưa đỉnh v vào trong hàng đợi ). Tại bước tổng quát, ta lấy đỉnh v đã được thăm ra khỏi hàng đợi, lần lượt xét tất cả các đỉnh u chưa được thăm nằm kề với v (đặt u là đỉnh đã xét và đưa đỉnh u vào hàng đợi). Quá trình trên sẽ được tiếp tục cho đến khi hàng đợi rỗng (không thể đến thăm đỉnh nào nữa). Quá trình trên có thể được mô tả bơi thủ tục sau: Procedure BFS(v); Begin Empty(hangdoi); Hangdoi <= v; Chuaxet[v] := false While hangdoif do Begin p <= hangdoi; For u Î Ke(v) do If chuaxet[u] then Begin hangdoi <= u; chuaxet[u] := false; End; End; End; Ví dụ: Xét đồ thị trong hình II.1 Đỉnh xuất phát : A Sau khi áp dụng giải thuật BFS, thứ tự các đỉnh được xét lần lượt là: A, B, C, D, E, F, G, I hoặc: A, C, B, F, E, D, G, H, I .... Ta nhận thấy, thuật toán DFS (hay BFS) có thể cho nhiều kết quả tùy thuộc vào cách xét đỉnh kề. Sau khi kết thúc thủ tục DFS (hay BFS) nếu tất cả các đỉnh của đồ thị đều được xét thì đồ thị là liên thông, ngược lại đồ thị có bộ phận liên thông. Thuật toán DFS và BFS sẽ được trình bày kỹ hơn trong chương 2 phần II. I.3TÌM CÁC THÀNH PHẦN LIÊN THÔNG CỦA ĐỒ THỊ. Ta nhận thấy thủ tục DFS(v) và DFS(v) cho phép ta thăm tất cả các đỉnh cùng thuộc một thành phần liên thông với đỉnh v. Do đó, số thành phần liên thông của đồ thị chính là số lần gọi đến thủ tục này. Vì vậy, nếu số lần gọi thủ tục là 1 thì ta có đồ thị liên thông, nếu số lần gọi thủ tục là n (n>1) thì đồ thị có n bộ phận liên thông. Chương 3: GIẢI QUYẾT MỘT SỐ BÀI TOÁN BẰNG LÝ THUYẾT ĐỒ THỊ III.1. BÀI TOÁN CÂY KHUNG NHỎ NHẤT III.1.1. Phát biểu bài toán : Bài toán cây khung nhỏ nhất của đồ thị là một trong những bài toán tối ưu trên đồ thị tìm được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Nội dung của bài toán được thể hiện như sau : Cho đồ thị vô hướng liên thông G =(V,E) với các tập đỉnh V = {1, 2, …, n} và tập các cạnh E = {e1, e2, …, em}, mỗi cạnh e được gán cho một giá trị trọng số không âm. Bài toán đặt ra là trong tập các cây khung của đồ thị G hãy tìm ra một cây khung với độ dài nhỏ nhất. Cây khung như vậy được gọi là cây khung nhỏ nhất và bài toán như trên được gọi là bài toán cây khung nhỏ nhất. Để minh họa cho bài toán trên, ta hãy xét một trong những mô hình tiêu biểu của bài toán này: bài toán nối mạng máy tính : Ta cần nối mạng một hệ thống gồm n máy tính, các máy được đánh số từ 1 đến n. Biết chi phí nối máy i với máy j là a[I,j], (I,j=1_n). Hãy tìm cách nối mạng sao cho tổng chi phí nối mạng là nhỏ nhất. Để giải bài tán cây khung nhỏ nhất, chúng ta có thể liệt kê tất cả các cây khung của đồ thị và chọn ra một cây khung có trọng lượng nhỏ nhất. Tuy nhiên, trong trường hợp đồ thị đầy đủ thì cách này đòi hỏi một thời gian thực hiện rất lớn. Trong trường hợp này, thuật toán Prim tỏ ra rất hiệu quả để giải bài toán trên. III.1.2. Thuật toán Prim : Trong thuật toán Prim, ta gọi U là tập đỉnh kề của cạnh trong T (T – tập các cạnh của cây khung nhỏ nhất). Ban đầu U chứa một đỉnh tùy ý trong G, còn T là tập cạnh rỗng. Ở mỗi bước ta sẽ chọn (u,v) ngắn nhất sao cho u Î U và vÎ V-U, sau đó thêm u vào U và thêm (u,v) vào T. Điều này đảm bảo rằng sau mỗi bước T luôn là một cây. Ta tiếp tục lặp lại bước như trên cho đến khi U=V, lúc đó T trở thành cây có trọng lượng nhỏ nhất của đồ thị G=(V,E). Thuật toán Prim miêu tả giải thuật như sau: Procedure Prim; Var U,V : tập các đỉnh; u,v : các đỉnh; Begin U := {một đỉnh tùy ý nằm trong G}; T := f; Repeat Chọn cạnh (u,v) ngắn nhất với u Î U, v Î V – U; U = U + {v}; T := T + {(u,v)}; Until U = V; End; Ví dụ: Xác định cây trọng lượng nhỏ nhất cho đồ thị III.1 dưới đây. 1 3 2 4 6 5 13 4 10 9 8 1 15 3 Hình III.1 Bước 1 : (Khởi tạo) U := {1}; T := f; Böôùc 2 : (bước lặp) B1: Tập U = {1}; J = {3,2} (J : Tập các đỉnh kề với các đỉnh nằm trong U, J Î V - U) Trọng số các cạnh : (1,3) = 4; (1,2) = 10; Þ chọn cạnh (1,3) U = U È {3} = {1,3}; T = T È {(1,3)} = {(1,3)} B2: Tập U = {1,3}; J = {2,5,6} Trọng số các cạnh : (1,2) = 10; (3,2) = 9; (3,5) = 8; (3,6) = 13 Þ Chọn cạnh (3,5) U = U È {5} = {1,3,5}; T = T È {(3,5)} = {(1,3), (3,5)} B3: Tập U = {1,3,5}; J = {2,4} Trọng số các cạnh : (1,2) = 10; (3,2) = 9; (5,2) = 3 Þ Chọn cạnh (5,2) U = U È {2} = {1,2,3,5}; T = T È {(5,2)} = {(1,3), (3,5), (5,2)} B4: Tập U = {1,2,3,5}; J = {4,6} Trọng số các cạnh : (3,6) = 13; (5,4) = 15 Þ Chọn cạnh (3,6) U = U È {6} = {1,2,3,5,6}; T = T È {(3,6)} = {(1,3), (3,5), (3,6), (5,2)} B5: Tập U = {1, 2, 3, 5, 6}; J = {4} Trọng số các cạnh : (5,4) = 15; (6,4) = 1 Þ Chọn cạnh (6,4) U = U È {4} = {1, 2, 3, 4, 5, 6}; T = T È {(6,4)} = {(1,3), (3,5), (3,6), (5,2), (6,4)} U = V Þ kết thúc. 1 3 2 4 6 5 13 4 8 1 3 Cây khung nhỏ nhất của đồ thị hình III.1 PHẦN II CHƯƠNG TRÌNH MINH HỌA Chương 1 : Giới thiệu chương trình 14 Chương 2 :Phân tích giải thuật và cài đặt chương trình 16 Chương 3 : Hướng dẫn sử dụng 23 Chương 1 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. I.1 TỔ CHỨC DỮ LIỆU Cấu trúc dữ liệu được sử dụng trong chương trình bao gồm các loại dữ liệu có sẵn của VISUAL .NET I.2 TỔ CHỨC CHƯƠNG TRÌNH Chương trình Demo bao gồm các File như sau: AboutBox1.vb, Canh_Do_Thi.vb, Dinh_Do_Thi.vb, Ham_Doc_Lap.vb, Form_Main.vb, Form_Nhap_Nhan.vb, Form_Sua_Nhan.vb, Form_Sua_Trong_So.vb, Form_Xoa_Dinh.vb, Form_Xoa_Canh.vb Trong đó : Form_Main.vb : Là tập tin chính của chương trinh Demo, có nhiệm vụ khởi tạo và gọi các chương trình con khác. Canh_Do_Thi.vb: Là chương trình con cho phép tạo cạnh một đồ thi. Dinh_Do_Thi.vb: Là chương trình con cho phép tạo một đỉnh của đồ thị. Ham_Doc_Lap.vb : Chứa các khai báo hàm và biến. Form_Nhap_Nhan.vb : Là chương trình con cho phép nhập nhãn của đỉnh đồ thị. Form_Sua_Nhan.vb : Là chương trình con cho phép sữa nhãn hoặc đặt tên mới của đỉnh đồ thị. Form_Sua_Trong_So.vb : Là chương trình con cho phép thay đổi trọng số giữa các cạnh. Form_Xoa_Canh.vb : Là chương trình con cho phép cho một cạnh bất kỳ. Form_Xoa_Dinh.vb : Là chương trình con cho phép xóa một đỉnh hoặc tất cả các đỉnh của đồ thị. AboutBox1.vb : Hoạt động của chương trình có thể được mô tả thông qua lưu đồ sau : Khởi tạo hhành công Kết thúc Khởi tạo các giá trị ban đầu Thực hiện công việc đã chọn Thoát chương trình Bắt đầu Chọn công việc cần thực hiện Đúng Đúng Sai Sai LƯU ĐỒ HOẠT ĐỘNG 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 II.1. GIẢI THUẬT DFS, BFS VÀ TÌM THÀNH PHẦN LIÊN THÔNG: Ta nhận thấy thủ tục DFS(V) và BFS(v) chỉ cho phép ta xác định được tất cả đỉnh thuộc cùng một miền liên thông với đỉnh v. Tuy nhiên, đối với đồ thị không liên thông, vấn đề đặt ra là làm sao để xác định được tất cả các thành phần liên thông của đồ thị. END u <= n Đúng chuaxet[v] := false u := 1 Inc(u) (có đường đi từ u à v) và (ChuaXet[u]) Đúng Sai DFS(u) START Sai LƯU ĐỒ GIẢI THUẬT DFS(v) Trước hết, ta xết lưu đồ hai giải thuật DFS(v) và BFS(v) : END QUEUE <= u chuaxet[u]:= false Inc(u) QUEUE := v ChuaXet[v] := false Sai START QUEUEf Đúng p <= QUEUE u := 1 Sai u <= n Ñuùng Đúng Sai (có đường đi từ u à v) và (ChuaXet[u]) LƯU ĐỒ GIẢI THUẬT BFS(v) Ta thấy rằng, trong hai lưu đồ trên chúng ta đều sử dụng một mảng ChuaXet để xác định một đỉnh nào đó đã được xét hay chưa. Giải thuật BFS(v) và DFS(v) được cài đặt cụ thể bằng ngôn ngữ Pascal như sau: Giải thuật BFS(v) : Procedure BFS(v); Begin Empty(hangdoi); Push(Hangdoi,v); LienThong[v] := SttLienThong; While Not(hangdoi) do Begin Pop(hangdoi,p); For u :=1 to n do If (A[p,u] 0) And (LienThong[u] = 0) then Begin Push(hangdoi,u);LienThong[u] := SttLienThong; End; End; End; Giải thuật BDS(v) Procedure DFS(v); Begin LienThong[v] := SttLienThong; For j := 1 to n do If (A[v,j] 0) And (LienThong[v] = 0) Then DFS(j); End; Khi đó, ta có thể xây dựng hàm để xác định một đồ thị có liên thông hay không, nếu không thì xác định các bộ phận liên thông của chúng, như sau: Function TestLienThong:Boolean; Begin For j := 1 to n do LienThong[j] := 0; SttLienThong := 0; For j := 1 to n do If LienThong[j] = 0 then Begin Inc(SttLienThong); DFS(v); (*hoaëc BFS(s)*) End; TestLienThong := (SttLienThong = 1); End; END u <= n Đúng chuaxet[v] := false u := 1 Inc(u) (Có đường đi từ u à v) và (ChuaXet[u]) Đúng Sai DFS(u) START Sai LƯU ĐỒ GIẢI THUẬT DFS(v) Kiểu Boolean để xác định một đỉnh nào đó đã được xét hay chưa. Vì vậy, ở đây ta có thể thay mãng ChuaXet kiểu Boolean bằng mãng LienThong[1..n] và biến SttLienThong (biến toàn cục) kiểu Interger trong đó : LienThong[v] = 0 : đỉnh v chưa được xét SttLienThong : v thuộc miền liên thông SttLienThong Khi kết thúc chương trình con này, nếu biến TestLienThong =1 thì đồ thị liên thông, ngược lại LienThong sẽ chứa các thành phần liên thông. II.2. GIẢI THUẬT PRIM: Thuật toán Prim được mô tả lại như sau : Khởi tạo : T = f; (T : tập các cạnh của cây khung). U = {1} (U : Tập các đỉnh đã xét thuộc cây khung). Bước lặp : chọncạnh (u,v)ngắn nhất với u Î U, v Î V – U; U := U + {v}; T := T + {(u,v)}; Lặp lại bước trên cho đến khi U = V Trong thuật toán Prim, để xác định một cạnh (u,v) ngắn nhất với u Î U, v Î V – U ta có thể mô phỏng phương pháp đánh dấu và gán nhãn trong giải thuật Dijkstra, ở đây chúng ta sử dụng hai mảng Weight[1..n] và mảng Near[1..n] kiểu Interger để đánh dấu cho một đỉnh .Trong đó, tại mỗi bước ta xác định : Near[v] = u : là đỉnh u gần đỉnh v nhất (với u Î U, v Î V – U) Weight[v] : là độ dài cạnh (v,near[v]). Weight[v] ³ 0: đỉnh v Î V – U, ngược lại đỉnh v Î U. Và sử dụng mảng Trươc[1..n] kiểu interger để xác định tập cạnh của cây khung : Truoc[v] = u Nếu (u,v) là cạnh của cây khung (v#0) Ta có thể mô tả chương trình cụ thể giải thuật Prim như sau : Procedure Prim; Begin For j := 2 to n do Begin Near[j] := 1; Weight[v] := A[1,j]; Truoc[j] := 1; End; Weitgh[1] := -1; Truoc[1] := 1; For i := 2 to n do Begin Min := MaxInt; (* Tìm cây có trọng lượng nhỏ nhất *) For j := 2 to n do Begin If (Weight[j]>=0) and (Weight<Min) then Begin Min := Weight[j]; v := j; u := Near[j]; End; End; (* Thêm v vào U, thêm cạnh (u,v) vào T *) Truoc[v] := u; Weight[v] := -1; (* Cập nhật lại các nhãn *) For i := 2 to n do If A[v,j] <. Weight[j] then Begin Weight[j] := A[v,j]; Near[j] := v; End; End; End; Ta có thể mô tả giải thuật Prim thông qua lưu đồ: Near[v]=1; Weight[v]=A[1,v] (vôùi "v = 2..n); j := 2; j <= n k <= n Min = ¥; k := 2 (Weight[k]<Min) vaø kÎ(V-U) Min = Weight[k]; v = k; u = Near[k]; Inc(k) Weight[v] = -1; Truoc[v] = u; k = 2 k <= n Weight[v]>A[v,k] Weight[k]=A[v,k]; Near[k] = v; Inc(k) Inc(k) END START Sai Đúng Đúng Đúng Đúng Ñuùng Sai Sai Sai Sai LƯU ĐỒ GIẢI THUẬT PRIM Chương 3 : HƯỚNG DẪN SỬ DỤNG Sau khi thực thi chương trình, ta có giao diện chương trình chính trong (HìnhIII.1). Thao tác với tập tin Công cụ chỉnh sủa Thuật toán trên đồ thị Giới thiệu Hình III.1 Giao diện chính cảu chương trình Trong bốn công cụ trên : Biểu đồ, chỉnh sửa, Công cụ, Giới thiệu mỗi công cụ trên đều có Menu đọc. Hình III.2 Biểu đồ: bao gồm các thư mục như trong hình III.2, chức năng mỗi mục được mô tả cụ thể thông qua tên thao tác muốn chọn. Chỉnh sửa: bao gồm xóa và thay đổi các cạnh, đỉnh và trọng số.(Hình III.3) Hình III.3 Công cụ : bao gồm thuật toán được áp dụng trên đồ thị (Hình III.4) Hình III.4 Giới thiêu : mô tả sơ lược về đề tài (hình III.5) Hình III.5 * Làm việc với tập tin có sẵn: Với một tập tin đã có sẵn ta thao tác trong chương trình như sau: Biểu đồ >> Mở tập tin >> Chọn đường dẫn >> OK (hình III.6) (Hình III.6) * Làm việc với tập tin mới: Với tập tin mới ta thực hiện các thao tác như sau: Biểu đồ >> Tạo mới >> Vẽ các đỉnh >> Trọng số các cạnh >> Duyệt đồ thị…( việc vẽ các đỉnh và điền trọng số các cạnh ta có thể chỉnh sửa) (hình III.7) (Hình III.7) Sau khi vào Biểu đồ >> Tạo mới, ta di chuyển chuột và click chuột trái trên màn hình nơi cần vẻ đỉnh đồ thị và nhập nhãn vào (hình III.7). Kế tiếp ta điền trọng số của các cạnh: Với những đỉnh đã tạo ta điền trọng số giữa các cạnh bằng cách chọn Đỉnh đầu, Đỉnh cuối, Trọng số (hình III.8) (Hình III.8) Sau đó ta vào menu Công cụ và tiến hành duyệt đồ thị.(hình III.9) kết quả sẽ cho ta cây trọng số nhỏ nhất. (Hình III.9) Hình III.9 Kết quả được trả về khi kết thúc chương trình PHẦN III KẾT LUẬN & HƯỚNG PHÁT TRIỂN I.KẾT QUẢ ĐẠT ĐƯỢC Hiểu và cài đặt tốt giải thuật đã yêu cầu bằng ngôn ngữ VISUAL .NET Giải thuật Prim. Chương trình chạy ổn định, kết quả thực hiện giải thuật sau khi cài đặt và chạy chương trình đúng với kết quả của phần lý thuyết. Giao diện được thiết kế rất thân thiện với người dùng và dễ dàng sử dụng. Chương trình được thiết kế dễ dàng cho việc phát triển hay sửa chữa chương trình khi có yêu cầu. II.HẠN CHẾ Mặc dù đã cố gắng hoàn thành Niên Luận 1, nhưng đây là lần đầu tiên viết một chương trình hoàn chỉnh nên vẫn còn thiếu kinh nghiệm trong kỹ thuật lập trình, tổ chức dữ liệu… cũng như chương trình nguồn còn dài. Mặt khác, do thời gian hạn chế nên chương trình vẫn còn có một số sai sót ngoài ý muốn. Do kiến thức còn hạn chế nên một số hàm trong chương trình chính và chương trình con sử dụng thiếu hiệu quả. Chương trình VISUAL .NET còn quá mới mẻ nên không thể tận dụng tối đa ưu điểm của ngôn ngữ này. III.HƯỚNG PHÁT TRIỂN Giao diện chương trình cần được thiết kế cho thân thiện với người dùng hơn, cần tối ưu chương trình để chương trình ngắn hơn và chạy tốt hơn… TÀI LIỆU THAM KHẢO ------- – J — ------- 1. Phan Tấn Tài Bài giảng : QUY HOẠCH TUYẾN TÌNH