Đề tài Mô phỏng một số thuật toán đồ thị

MỤC LỤC Mục lục 1. Lý do chọn đề tài …………………………………………………………….3 2. Những kiến thức cơ sở ………………………………………………………3 2.1. Khái niệm thuật toán ……………………………………………….3 2.2. Các đặc trưng của thuật toán ……………………………………….4 2.3. Độ phức tạp thuật toán ……………………………………………..4 3. Tổng quan về mô phỏng thuật toán ………………………………………….4 3.1. Khái niệm mô phỏng thuật toán ……………………………………4 3.2. Lịch sử mô phỏng thuật toán ……………………………………….5 3.3. Tác dụng của mô phỏng thuật toán trong dạy học………………….6 3.4. Một số yêu cầu đối với mô phỏng thuật toán ………………………8 4. Tổng quan về đồ thị ………………………………………………………….8 4.1. Định nghĩa đồ thị …………………………………………………...9 4.2. Phân loại đồ thị ……………………………………………………..9 4.3. Cây khung và cây khung nhỏ nhất …………………………………10 4.4. Các phương pháp biểu diễn đồ thị ………………………………....10 5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị …………….11 5.1. Phân tích hệ thống mô phỏng thuật toán đồ thị…………………….11 5.1.1. Mục đích……………………………………………………..11 5.1.2. Đặc điểm …………………………………………………….11 5.1.3. Kết quả phân tích…………………………………………….12 5.2. Thiết kế hệ thống mô phỏng thuật toán đồ thị……………………...14 5.2.1. Màn hình nền hệ thống mô phỏng…………………………...14 5.2.2. Giao diện chính và chức năng trình mô phỏng ……………..14 6. Cài đặt mô phỏng thuật toán đồ thị …………………………………………15 6.1. Công cụ lập trình …………………………………………………..15 6.2. Cài đặt thuật toán Prim …………………………………………….16 6.2.1. Bài toán ……………………………………………………..16 6.2.2. Ý tưởng thuật giải …………………………………………..16 6.3. Cài đặt các lớp trong chương trình…………………………………17 6.3.1. Lớp cơ sở …………………………………………………..17 6.3.2. Lớp Prim ……………………………………………………18 6.3.3. Lớp Main …………………………………………………...18 7. Kết luận ……………………………………………………………………18 8. Hướng phát triển …………………………………………………………..18 Tài liệu tham khảo 1. Lý do chọn đề tài Lý thuyết đồ thị là một vấn đề hết sức phức tạp, hơn nữa nó chiếm một vị trí quan trọng trong khối kiến thức cơ sở của ngành công nghệ thông tin. Để hiểu được lý thuyết về đồ thị cũng như hiểu được hoạt động của các thuật toán trên đồ thị cần phải có thời gian tìm hiểu lâu dài. Việc dạy và học về đồ thị trong nhà trường cũng gặp nhiều khó khăn. Các thuật toán khiến cho người học khó hiểu, khó hình dung nhất là với những người mới bắt đầu học Tin ví dụ như thuật toán Dijkstra và nếu chỉ với các dòng lệnh của thuật toán, người dạy đôi khi cũng rất khó truyền đạt cho người học ý tưởng, hoạt động của thuật toán như thế nào. Sử dụng việc mô phỏng các thuật toán trên đồ thị sẽ giải quyết được vấn đề này. Bởi vì việc mô phỏng với giao diện đồ hoạ, rất trực quan, có chú giải từng bước, đồng thời với giao diện đồ họa trực quan như vậy, người sử dụng có thể tương tác với hệ thống mô phỏng. Mô phỏng sẽ giúp cho người học nhanh chóng hiểu được bản chất, hiểu được từng câu lệnh trong thuật toán hoạt động như thế nào, đồng thời đánh giá được tính đúng đắn của thuật toán. Còn đối với người dạy, mô phỏng sẽ giúp cho người dạy dễ dàng truyền đạt ý tưởng của thuật toán, giúp cho quá trình giảng dạy thuận lợi hơn. Hơn nữa, mô phỏng làm cho người học cảm thấy hứng thú hơn khi tiếp xúc với các thuật toán trên đồ thị. Mô phỏng cũng là một công cụ giảng dạy hiệu quả cho người dạy và cũng là một tư liệu học tập tốt. Như vậy mô phỏng thuật toán nói chung và mô phỏng các thuật toán đồ thị nói riêng mang lại nhiều lợi ích trong việc dạy và học về lý thuyết đồ thị. Đồng thời nó cũng góp phần quan trọng vào việc ứng dụng công nghệ thông tin vào việc giảng dạy trong nhà trường. Thuật toán về đồ thị chiếm một số lượng khá lớn, tuy nhiên số lượng thuật toán được mô phỏng và đưa vào áp dụng để giảng dạy thì còn hạn chế. Cũng có nhiều trang Web về mô phỏng thuật toán đồ thị nhưng hầu hết chưa có hệ thống. Cao học K15 cũng có một luận văn mô phỏng thuật toán đồ thị như thuật toán Dijkstra, thuật toán Kruskal. Vì vậy trong khuôn khổ nghiên cứu của mình, em xin tiếp tục nghiên cứu việc mô phỏng một số thuật toán đồ thị như thuật toán Prim, các thuật toán tìm kiếm theo chiều rộng, chiều sâu trên đồ thị. 2. Những kiến thức cơ sở 2.1. Khái niệm thuật toán Thuật toán là một hệ thống chặt chẽ và rõ ràng các quy tắc nhằm xác định một dãy các thao tác trên cấu trúc dữ liệu sao cho: với một bộ dữ liệu vào, sau một số hữu hạn bước thực hiện các thao tác đã chỉ ra, ta đạt được mục tiêu đã định. 2.2. Các đặc trưng của thuật toán - Tính đơn định: Ở mỗi bước của thuật toán, các thao tác phải hết sức rõ ràng, không gây nên sự nhập nhằng, lộn xộn, đa nghĩa. Thực hiện đúng các bước của thuật toán thì với một bộ dữ liệu vào chỉ cho duy nhất một kết quả ra. - Tính dừng: Thuật toán không được rơi vào quá trình vô hạn, phải dừng lại và cho kết quả sau một số hữu hạn bước. Tính đúng: Sau khi thực hiện tất cả các bước của thuật toán theo đúng quá trình đã định, ta phải đạt được kết quả mong muốn với mọi bộ dữ liệu đầu vào. Kết quả đó được kiểm chứng bằng yêu cầu bài toán. Tính phổ dụng: Thuật toán phải dễ sửa đổi để thích ứng được với bất kì bài toán nào trong một lớp các bài toán và có thể làm việc trên các dữ liệu khác nhau. - Tính khả thi: Kích thước dữ liệu phải đủ nhỏ, thuật toán phải được máy tính thực hiện trong thời gian cho phép, thuật toán phải dễ hiểu và dễ cài đặt. 2.3. Độ phức tạp thuật toán Cho f và g là hai hàm xác định dương với mọi n. Hàm f(n) được gọi là O(g(n)) nếu tồn tại một hằng số c > 0 và một giá trị n0 sao cho: f(n) ≤ c.g(n) với mọi n ≥ n0 Nghĩa là nếu xét những giá trị n ≥ n0 thì hàm f(n) sẽ bị chặn trên bởi một hằng số nhân với g(n). Khi đó, nếu f(n) là thời gian thực hiện của một giải thuật thì ta nói giải thuật đó có cấp là g(n) (hay độ phức tạp tính toán là O(g(n))). 3. Tổng quan về mô phỏng thuật toán 3.1. Khái niệm mô phỏng thuật toán Mô phỏng thuật toán (Algorithm Animation) là quá trình tách dữ liệu, thao tác, ngữ nghĩa và tạo mô phỏng đồ họa cho quá trình trên [Stasko 1990]. Mô phỏng thuật toán được thiết kế để giúp người dùng có thể hiểu thuật toán, đánh giá chương trình và sửa lỗi chương trình. Một chương trình máy tính chứa các cấu trúc dữ liệu của thuật toán mà nó thực thi. Trong quá trình thực thi chương trình, các giá trị trong cơ sở dữ liệu được thay đổi. Mô phỏng thuật toán sử dụng biểu diễn đồ họa để biểu diễn cấu trúc dữ liệu và chỉ ra sự thay đổi giá trị trong cơ sở dữ liệu trong mỗi trạng thái. Thông qua đó, người sử dụng có thể xem được từng bước thực thi chương trình và nhờ vậy có thể hiểu chi tiết được thuật toán. Mô phỏng thuật toán cũng được dùng để đánh giá một chương trình đã có bằng cách cung cấp các mô phỏng cho các thành phần của hệ thống, nhờ đó có thể kiểm tra được hiệu năng của hệ thống. Bên cạnh việc giúp người sử dụng hiểu hơn về hệ thống, mô phỏng thuật toán còn được dùng để giúp thực hiện quá trình dò lỗi dễ dàng hơn. Để sử dụng mô phỏng thuật toán trong quá trình dò lỗi của một chương trình, người sử dụng chú thích vào các trạng thái của chương trình để tạo ra các lệnh mô phỏng, sau đó chúng sẽ được đưa vào hệ thống mô phỏng thuật toán để tạo mô phỏng. Người sử dụng có thể xem chương trình của họ đã thực hiện như thế nào, các giá trị dữ liệu ở mỗi bước và một bước sẽ ảnh hưởng tới các bước sau như thế nào. Nó sẽ giúp người sử dụng tìm ra tất cả các lỗi có thể xảy ra trong chương trình. 3.2. Lịch sử mô phỏng thuật toán Mô phỏng thuật toán đã được xây dựng từ hai thập kỷ gần đây. Nhưng chương trình mô phỏng thuật toán đầu tiên là của Ken Knowlton ở Bell Telephone Laboratories khi mô phỏng ngôn ngữ liên kết danh sách vào năm 1966. Mô phỏng thuật toán phát triển mạnh vào đầu những năm 80 của thế kỷ 20. Vào năm 1981, video (sorting out sorting) được xây dựng bởi Ronald Baecker ở đại học Toronto được coi là khởi điểm của lĩnh vực mô phỏng thuật toán. Từ đó các nhà giáo dục đã sử dụng mô phỏng thuật toán để trợ giúp quá trình dạy học. Giữa những năm 80 và đầu những năm 90, hai hệ thống có ảnh hưởng mạnh đến về sau được phát triển và có ý nghĩa lớn trên tất cả những hệ thống sau này. Hai hệ thống này là BALSA-I (Brown ALgorithm Simulator and Animator) [Brown 1984] và TANGO (Transition-based Animation GeneratiOn) [Stasko 1990]. Từ khi hai hệ thống của BALSA và TANGO được phát triển, các hệ thống đi sau của hai hệ thống đáng chú ý này cũng được phát triển. Với việc phát triển của công nghệ mới, tính phổ dụng của mạng toàn cầu và sự tiến hóa của ngôn ngữ lập trình Java, những người phát triển đã xây dựng những hệ thống mô phỏng thuật toán trực tuyến, có lợi thế của những hệ thống mở dễ tiếp cận hơn.Một số nhà phát triển cũng hợp nhất việc sử dụng đa phương tiện trong các hệ thống của họ. Việc sử dụng các hệ thống mô phỏng thuật toán không còn bị bó hẹp trong các lớp học truyền thống hoặc phòng thí nghiệm giảng dạy nữa mà đã được mở rộng để dạy từ xa. Trong khoảng hai thập niên gần đây, một số rất lớn các hệ thống mô phỏng thuật toán đã ra đời và phát triển mạnh mẽ. Phần lớn các hệ thống mô phỏng thuật toán đã đề cập trong mục này đều phổ biến hơn và phức tạp hơn các hệ thống đang được sử dụng trong thực tế. Chúng đã được phát triển và sử dụng bởi những nhà chuyên môn, với mục đích giáo dục hoặc nghiên cứu thực nghiệm của họ. Một trong số các hệ thống này có một kiến trúc phức tạp và cần những công nghệ đặc biệt để chạy nó. Chúng ta không có bất kỳ tiện ích nào của các hệ thống này để xây dựng hệ thống mô phỏng các thuật toán đồ thị; thay vào đó, chúng ta đã ước lượng được các hệ thống mô phỏng hiện hữu khác mà kích thước nhỏ hơn và có những kiến trúc đơn giản hơn. 3.3. Tác dụng của mô phỏng thuật toán trong dạy học Các hệ thống mô phỏng thuật toán được sử dụng rộng rãi như công cụ hỗ trợ giảng dạy trong ngành giáo dục khoa học máy tính. Một số nghiên cứu thực nghiệm đã ước lượng hiệu quả của chúng trong giáo dục và kết quả nhận được có thay đổi. Những tác dụng của việc áp dụng mô phỏng thuật toán trong dạy học được ghi nhận lại như sau: Việc sử dụng các hoạt cảnh mô phỏng thuật toán gây hứng thú cho người học, làm tăng tính sáng tạo của người học. Sử dụng mô phỏng kết hợp với phương pháp thuyết trình truyền thống làm tăng tốc độ hiểu biết cho người học. Ngoài ra mô phỏng giúp cho người học dễ hiểu thuật toán hơn thông qua các bước mô phỏng trực quan kết hợp với mã nguồn chương trình. Tuy nhiên việc sử dụng mô phỏng thuật toán không phải lúc nào cũng đem lại hiệu quả. Các nghiên cứu thực nghiệm của Stasko (1993) và Bynre (1996) đã cho kết quả là giữa nhóm sinh viên sử dụng mô phỏng và nhóm không sử dụng mô phỏng thì hiệu quả đạt được không có sự chênh lệch là mấy. Những kết quả thí nghiệm bất lợi này gợi ý những yếu tố quan trọng khác trong việc sử dụng mô phỏng thuật toán. Các kết quả đã thông báo rằng để đạt được hiệu quả mô phỏng thuật toán đầy đủ thì điều quan trọng là mô phỏng được sử dụng phối hợp với những yếu tố khác. Phải để sinh viên tự mình sử dụng, điều khiển quá trình mô phỏng và phải để họ tự tạo những bộ dữ liệu của riêng mình. Để mô phỏng thuật toán mang lại hiệu quả cao nhất, nó phải thoả mãn những yêu cầu sau đây : Thứ nhất, sử dụng mô phỏng thuật toán phải song song với những chỉ dẫn, có hệ thống trợ giúp sử dụng, phải có mô phỏng từng bước để người học hiểu từng bước của giải thuật, có khả năng quay lui để ngườu học có thể quay lại những bước quan trọng, đồng thời lấy ý kiến phản hồi từ sinh viên để cải thiện chương trình mô phỏng thuật toán tốt hơn. Hai là phải biết xây dựng mô phỏng hiệu quả : mô phỏng cái gì, mô phỏng như thế nào, hình ảnh ra sao,... Một chương trình mô phỏng thuật toán hiệu quả phải đáp ứng được các yêu cầu : Truy cập mở (Open access): Người dùng có thể truy cập hệ thống mô phỏng mở. Hơn nữa, nếu có cài đặt hệ thống mô phỏng trong trường học, thì họ có thể truy cập tới hệ thống này từ nhà hoặc từ bất cứ nơi nào khác. Mô phỏng một cách có điều khiển (Control animation): Người dùng có thể tự tạo tập dữ liệu của chính mình khi sử dụng hệ thống mô phỏng. Trong khi các tập dữ liệu được cài đặt sẵn cũng có thể giúp đỡ sinh viên có những sự hiểu biết ban đầu, hệ thống nên có cả 2 tùy chọn này. Tương tác (Ineractivity): Hệ thống mô phỏng phải cung cấp được sự Tương tác giữa người dùng và hệ thống. Sự tương tác bao gồm: người dùng xem theo từng bước, hủy, chạy nhanh tới một bước mong muốn, hay xem lại từ đầu, ... Lịch sử (History): Hệ thống mô phỏng cho phép người dùng xem lại các bước trước trong quá trình thực hiện. Phản hồi (Feedback): Phải tiếp thu phản hồi của sinh viên về việc sử dụng hệ thống mô phỏng để ước lượng hiệu quả của hệ thống cũng như để cải thiện hệ thống. 3.4. Một số yêu cầu đối với mô phỏng thuật toán - Phản ánh đúng nội dung thuật toán : Thuật toán được đưa ra mô phỏng phải chính xác, các bước thực hiện thuật toán phải trực quan và phản ánh đúng theo nội dung thuật toán đã đưa ra để đảm bảo tính đúng đắn của thuật toán. Hệ thống mô phỏng phải được thực hiện theo từng bước : thuật toán thường là trừu tượng, nếu để chương trình chạy tự động thì người dùng sẽ khó hiểu. Vì vậy, cần phải có chế độ thực hiện mô phỏng thuật toán theo từng bước, để người học có thể quan sát, theo dõi sự thay đổi giá trị của từng biến. Nhờ đó, sẽ giúp cho người học hiểu thuật toán rõ hơn và nhanh hơn. Mô tả thuật toán phải có tính động: để mô tả trực quan hóa quá trình thực hiện của thuật toán ta nên đưa vào hình ảnh động (có thể có âm thanh) để thể hiện sự thay đổi của dữ liệu trong quá trình thực thi. Ví dụ như, trong thuật toán tìm cây khung nhỏ nhất - thuật toán Prim, ta đưa vào các đối tượng đồ họa là đỉnh, cạnh. Trong quá trình thực thi thuật toán thì các đỉnh/cạnh được chọn sẽ sáng nhấp nháy và đổi màu, sau khi được chọn thì các đỉnh/cạnh sẽ được tô màu khác với màu ban đầu. Tương ứng với quan sát sự thay đổi trên đồ thị, ta có thể đưa vào đoạn thuật toán thể hiện tương ứng và song song với quá trình duyệt trên đồ thị. Nhờ đó mà thuật toán được thể hiện một cách rõ nét, sinh động, trực quan. giúp người đọc dễ theo dõi, dễ hiểu thuật toán hơn. Thuật toán được thử nghiệm trong mọi trường hợp để đảm bảo thời gian thực hiện tốt nhất : một thuật toán được mô phỏng phải đảm bảo là thuật toán tốt, dễ hiểu và đúng đắn. Muốn vậy ta phải thử nghiệm trong các trường hợp dữ liệu ngẫu nhiên, tốt nhất, xấu nhất. Nếu thuật toán vẫn chạy tốt và trong một thời gian cho phép thì thuật toán mới hiệu quả. Ta không thể chấp nhận một thuật toán đúng mà thời gian chạy quá lớn. - Tạo ra các mức độ khác nhau cho người dùng: Đối tượng học thuật toán thường là các sinh viên. Họ có trình độ tiếp thu khác nhau, nên ta phải đưa ra nhiều chế độ thao tác khác nhau để người học được phép lựa chọn. 4. Tổng quan về đồ thị 4.1. Định nghĩa đồ thị Một đồ thị được hiểu là một bộ hai tập hợp hữu hạn: Tập hợp đỉnh và tập hợp cạnh nối các đỉnh này với nhau. Một đồ thị được mô tả hình thức như sau: G = (V, E) Trong đó V là tập các đỉnh (Vertices) và E là tập các cạnh (Edges). Như vậy có thể coi đồ thị là tập các cặp (u, v) với u và v là hai đỉnh của V. 4.2. Phân loại đồ thị Chúng ta có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E. Cho đồ thị G = (V, E). G được gọi là đơn đồ thị nếu giữa hai đỉnh u và v của V có nhiều nhất là một cạnh trong E nối từ u tới v. G được gọi là đa đồ thị nếu giữa hai đỉnh u và v của V có thể có nhiều hơn một cạnh trong E nối từ u tới v. G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kì cũng là cạnh nối hai đỉnh u, v G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nối từ đỉnh v tới đỉnh u. Chu trình của đồ thị: chu trình là một dãy cạnh kế tiếp khép kín sao cho mỗi đỉnh của đồ thị được đi qua không quá một lần. Chu trình được kí hiệu bởi việc đưa ra các cạnh và các đỉnh liên tiếp nhau trên chu trình. Chẳng hạn chu trình C đi qua các đỉnh p1, p2, …, pk và các cạnh e1, e2, …, ek thì ta viết C = (p1, e1, …, pk, ek, p1) Trong trường hợp đồ thị là đồ thị đơn, thì thay vì viết rõ các cạnh và các đỉnh, chu trình được xác định duy nhất qua việc gọi tên các đỉnh nó đi qua. Ví dụ chu trình C ở trên có thể viết thành: C = (p1, p2, …, pk, p1) Số cạnh của chu trình được gọi là độ dài của chu trình và thông thường hay kí hiệu là l(C). 4.3. Cây khung và cây khung nhỏ nhất - Cây là đồ thị vô hướng, liên thông, không có chu trình đơn. Đồ thị vô hướng không có chu trình đơn được gọi là một rừng (hợp của nhiều cây). Như vậy mỗi thành phần liên thông của một rừng là nhiều cây. - Cây khung: Cho G là một đơn đồ thị. Một cây được gọi là cây khung của G nếu nó là một đồ thị con của G và chứa tất cả các đỉnh của G. - Cây khung nhỏ nhất: Nói chung, ta có thể định nghĩa cây khung nhỏ nhất cho một đồ thị G như sau: Nếu mỗi cạnh eij = (vi, vj) có một trọng số cij, thì cây khung nhỏ nhất là một tập hợp các cạnh ký hiệu là Espan, sao cho: C = sum( cij | eij Î Espan ) là nhỏ nhất. 4.4. Các phương pháp biểu diễn đồ thị 4.4.1. Biểu diễn đồ thị bằng ma trận kề Giả sử G = (V, E) là một đơn đồ thị có số đỉnh (kí hiệu |V| là n), không mất tính tổng quát, có thể coi các đỉnh được đánh số 1, 2, …, n. Khi đó ta có thể biểu diễn đồ thị bằng một ma trận vuông A = [aij] cấp n. Trong đó: aij = 1 nếu (i, j) Î E aij = 0 nếu (i, j) Ï E Quy ước aii = 0 với mọi i; Đối với đa đồ thị thì việc biểu diễn cũng tương tự trên, chỉ có điều nếu như (i,j) là cạnh thì không phải ta ghi số 1 vào vị trí aij mà là ghi số cạnh nối giữa đỉnh i và j. Ví dụ: 4.4.2. Biểu diễn bằng ma trận liên thuộc Sử dụng ma trận (aij) có kích thước n x m với n là số đỉnh, m là số cạnh của đồ thị. Trước hết ta đánh số các đỉnh của đồ thị từ 1 đến n, còn các cạnh được đánh số từ 1 đến m. Ta gán cho aij giá trị bằng 0 nếu cạnh thứ j không chứa đỉnh i hoặc 1 nếu ngược lại. Ví dụ: 5. Phân tích và thiết kế hệ thống mô phỏng thuật toán trên đồ thị 5.1. Phân tích hệ thống mô phỏng một số thuật toán đồ thị 5.1.1. Mục đích Hệ thống nhằm giúp cho quá trình học tập về cấu trúc dữ liệu và giải thuật được diễn ra một cách thuận lợi hơn. Cụ thể: giúp học sinh, sinh viên dễ hiểu, dễ nắm bắt được thuật toán, có thể hiểu chi tiết thuật toán làm gì và làm như thế nào. Hơn nữa, với ưu điểm là một trang Web nên người học có thể truy cập vào bất kì lúc nào, vào bất kì thời điểm nào. Như vậy người học có thể luyện tập vào bất kì lúc nào sau khi học bài trên lớp. 5.1.2. Đặc điểm Hiện nay, trên mạng cũng đã có khá nhiều trang Web làm về mô phỏng thuật toán, trong đó cũng có một số trang viết về mô phỏng thuật toán đồ thị. Nhưng hầu hết các trang Web đó là của nước ngoài nên chúng được viêt bằng tiếng Anh. Điều này gây khó khăn cho những người không thông thạo tiếng Anh và cả với những người mới học về cấu trúc dữ liệu và giải thuật. Hơn nữa hầu hết các trang đó chỉ giới thiệu thuật toán, sau đó trình chiếu mô phỏng các ví dụ mẫu. Điều này làm cho người học khó hiểu về thuật toán, không nhận biết được thuật toán làm cụ thể những gì, người dùng không thể xem lại các bước trước đó dẫn đến việc học thuật toán không hiệu quả. Một vấn đề nữa là các trang Web đó không kết hợp được việc mô phỏng và hiển thị code của thuật toán. Một số trang có kết hợp được cái đó nhưng hầu hết code thuật toán được viết bằng ngôn ngữ Java, yêu cầu người học phải có một trình độ nhất định thì mới có thể hiểu được thuật toán. Ở thời điểm hiện tại cũng đã có một số rất ít trang Web có giao diện thân thiện với người dùng, chúng vừa cho phép hiển thị đồ thị mẫu, một bên là giả mã của thuật toán, có thể thực hiện mô phỏng từng bước giúp người dùng có thể nắm bắt thuật toán dễ dàng hơn. Nhưng hệ thống đó còn hạn chế là không thể thực hiện quay lui được, sau khi mô phỏng xong một đồ thị, ta không thể thực hiện mô phỏng đối với một đồ thị mới. Ngày nay, với sự bùng nổ công nghệ Web, việc dạy và học không thể dừng lại ở phương pháp truyền thống mà còn kết hợp với trực quan sinh động. Và việc xây dựng một hệ thống mô phỏng thuật toán đồ thị khắc phục những nhược điểm của các hệ thống hiện tại là rất cần thiết. 5