Báo cáo nghiên cứu khoa học 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

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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
3
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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.

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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
5
Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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

Báo cáo nghiên cứu khoa học Mô phỏng một số thuật toán đồ thị
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
Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
7

Bùi Thị Thuỷ - AK54.CNTT.ĐHSPHN
8