Lý thuyết đồ thị là một trong những môn học hổ trợ kiến thức lập trình, khi học ngành CNTT sẽ gặp môn nay với các bài toán tìm đường đi ngắn nhất. Hôm nay mình xin chia sẻ đến mọi người một công cụ hay hỗ trợ học Lý Thuyết Đồ Thị trên điện thoại Android và Windows! Công cụ này có tên là Graph Engine và bài viết này mình sẽ giới thiệu các tính năng và hướng dẫn sử dụng Graph Engine.
Graph Engine
Graph Engine là công cụ hỗ trợ học Lý Thuyết Đồ Thị thông qua vẽ đồ thị dựa trên đầu vào (Input) các danh sách cung. Hỗ trợ đơn đồ thị. Sau đây là các tính năng và cách sử dụng Graph Engine.
Link tải Graph Engine: https://ktfamily.github.io/graphengine.html
1. Vẽ đồ thị
Để vẽ được đồ thị bên ngoài Layout thì đầu tiên bạn phải nhập vào số đỉnh cần thiết. Sau đó nhập lần lượt các danh sách cung. Mỗi một cung có 3 chỉ số cách nhau bằng một dấu cách lần lượt là đỉnh đầu – đỉnh cuối – trọng số. Khi bạn nhập một đồ thị hợp lệ thì sẽ nhận được dấu tick màu xanh như trên hình.
Lưu ý rằng Graph Engine chỉ hỗ trợ đơn đồ thị, không chấp nhận các trường hợp đa cung, hoặc có khuyên. Nếu bạn nhập đồ thị có trọng số thì phải nhập hết trọng số cho tất cả các cung mới được xem là hợp lệ!
2. Chỉnh hướng cho cung
Để chỉnh cho cung là vô hướng hoặc có hướng thì bạn chọn click vào mục Directed nhé!
3. Hiển thị láng giềng của đỉnh
Bằng cách nhấp vào Show Neighbors, bạn có thể hiển thị được láng giềng của tất cả cách đỉnh đồ thị. Đối với đồ thị có hướng, bạn có thể xem các bậc trong, bậc ngoài của đỉnh.
4. Căn chỉnh đồ thị bằng Force
Đồ thị sẽ trông cân đối hơn nếu bạn sử dụng tính năng căn chỉnh đồ thị bằng cách nhấp vào Force. Al sẽ tự làm cân bằng khoảng cách các cung, đỉnh của đồ thị và đem đồ thị ra giữa màn hình. Nếu bạn không hài lòng với tính năng này thì không dùng nữa bằng cách nhấp hủy (Bỏ tick).
5. Hiển thị ma trận
Graph Engine hỗ trợ hiển thị đồ thị dưới dạng ma trận với 2 loại ma trận là Ma trận liên thuộc (đỉnh-cung) EV và Ma trận kề (đỉnh-đỉnh) VV. Bạn có thể lấy ma trận này bằng cách Copy nhé!
6. Chụp ảnh đồ thị
Nhấp vào biểu tượng hình Camera và bạn có thể lưu lại đồ thị dưới dạng PNG rồi. Nhớ cấp quyền truy cập bộ nhớ cho công cụ này nhé!
Hình ảnh sau khi chụp!
7. Minh hoạ các thuật toán tìm kiếm (Search Algorithms)
Chức năng Duyệt đồ thị giúp bạn duyệt và cho ra kết quả của 3 thuật toán:
– Duyệt theo chiều rộng (Breadth First Search)
– Duyệt theo chiều sâu (Deepth First Search)
+ Dùng Stack
+ Dùng đệ quy (Recursion)
Ngoài ra bạn có thể xem quá trình duyệt ở chế độ minh hoạ (bỏ tick Quickly). Có thể tạm dừng để chụp lại.
Tất cả các thuật toán duyệt đều hỗ trợ 2 chiều tăng và giảm danh dách kề.
Lưu ý khi duyệt minh hoạ xong bạn cần Clear Color để duyệt tiếp nhé!
Link tải Graph Engine: https://ktfamily.github.io/graphengine.html
Đây là phiên bản chính thức đầu tiên nên vẫn có thể chưa tốt. Nếu các bạn ủng hộ chúng tôi bằng cách click vào những Quảng cáo trên Android thì chúng tôi sẽ hoàn thiện hơn công cụ này và Bổ sung nhiều thuật toán khác nữa như Kiểm tra chu trình, Tìm đường, Tìm cây khung, Tìm luồng cực đại,… Cảm ơn mọi người đã xem bài viết!
