NHỮNG YÊU CẦU THỰC TẾ VÀ HƯỚNG TIẾP CẬN
1.1. Mục đích:
Xây dựng một ứng dụng mà có thể biểu diễn đồ thị trực quan (thể hiện được các
đỉnh và các cạnh của đồ thị) lên một màn hình đồ họa. để từ đó người sử dụng có thể
nhìn thấy trực quan mô hình của đồ thị. Để từ đó hiểu về cấu trúc của đồ thị. Chương
trình cũng phát triển một số thuật toán trên đồ thị để người dùng có thể nhìn thấy trực
quan kết quả của một số giải thuật trên đồ thị.
1.2. Những yêu cầu thực tế:
Hiện nay có nhiều tài liệu, trang web hướng dẫn về đồ thị và các thuật toán trên
đồ thị. Nhưng nhìn chung những bài giảng chỉ mang tình lý thuyết và cũng chưa có
nhiều chương trình cho phép biểu diễn đồ thị dưới dạng trực quan và hiển thị kết quả
dưới các thuật toán sử dụng trên đồ thị. Để giúp sinh viên có thể tự chuẩn bị trước
các thuật toán ở nhà và giúp giáo viên làm rõ những thắc mắc của học sinh về thuật
toán cơ bản và các cải tiến có thể làm giảm độ phức tạp của các thuật toán đó cần
phải có thêm những công cụ giúp làm hiệu quả cho công việc chuẩn bị của sinh viên
cũng như dẫn giải của giảng viên trong khi giảng bài.
Chương trình của chúng em hướng tới mục tiêu đó. Mô phỏng một số các
thuật toán cơ bản trên đồ thị mà sinh viên sẽ học. Đó là các thuật toán: biểu diễn đồ thị
dưới dạng hình tròn, lệch đường thẳng. Biểu diễn kết quả của đồ thị qua các bài toán:
tìm đường đi ngắn nhất, duyệt theo chiều rộng (BFS), duyệt theo chiều sâu (DFS) và
bài toán tìm cây khung cực tiểu trên đồ thị vô hướng. Chương trình đưa ra kết quả và
hiển thị những kết quả đó theo hướng trực quan. Chương trình cũng cho phép người
dùng có thể nhìn thấy tổ chức dữ liệu trực quan như ma trận kề của đồ thị.
Hiện nay đã có nhiều trang web giới thiệu chương trình mô phỏng về các thuật
toán miễn phí ở trên mạng Internet. Nhưng tổng hợp lại, các chương trình đó đều có
chứa những nhược điểm có thể chỉ ra như sau:
Trường Đại Học Đà Lạt – Khoa Công nghệ thông tin Báo cáo đồ án tốt nghiệp
Đề tài: Vẽ đồ thị trực quan trên WPF Trang 10
Hầu hết các chương trình này đều là một dạng bài tập. Hay nói cách
khác, người viết chỉ hoàn thiện một thuật toán riêng lẻ, các thuật toán được
giới thiệu một cách rời rạc.
Hầu hết các chương trình chỉ giới thiệu về thuật toán sau đó cho phép
người dùng chạy thử trên một mẫu dữ liệu có sẵn. Hay nói cách khác các
chương trình mô phỏng chỉ làm một việc là trình chiếu cho người sử dụng
nhìn thấy các bước hoạt động của thuật toán đó. Việc theo dõi kịp các
bước đó để hiểu đã thuật toán đã là một thử thách. Việc đó còn khó hơn
đối với người bắt đầu học một thuật toán cụ thể nào đó chưa kể đến là các
thuật toán đó đều trừu tượng.
Chưa cho phép người dùng đưa dữ liệu của mình vào để thử nghiệm.
Chưa hiển thị kết quả dưới dạng trực quan.
1.3. Đề xuất cho hệ thống mới
Hệ thống mới cho phép người dùng nhìn thấy trực quan đồ thị cũng như kết quả
của các bài toán.
Hệ thống cũng cho phép người dùng đưa dữ liệu vào (là đồ thị vô hướng) để
kiểm tra.
Xây dựng đồ thị trực quan dưới dạng hình tròn, lệch đường thẳng.
Biểu diễn kết quả của một số thuật toán BFS, DFS, cây khung nhỏ nhất dưới
dạng trực quan.
Biểu diễn cấu trúc dữ liệu của đồ thị dưới dạng ma trận kề.
Có thể trích xuất hình ảnh của đồ thị cho mục đích lưu trữ kết quả.
XEM THÊM ==> Hướng dẫn cài đặt chi tiết
Nguồn: Sharecode.vn