Tìm hiểu về lý thuyết đồ thị với Ruby

Trong bài viết này, chúng ta sẽ cùng tìm hiểu về lý thuyết đồ thị với Ruby. Là một lập trình viên, chắc hẳn các bạn đã ít nhiều nghe nói về cây nhị phân. Nó có dạng như sau: Cây nhị phân thực tế chính là một phiên bản của đồ thị, qua đó các bạn có thể hình dung được mức độ phổ biến rộng rãi của đồ thị. Chúng ta sẽ bắt đầu với một cái nhìn tổng quát về các nguyên lý cơ bản của đồ thị, sau đó chúng ta sẽ tìm hiểu một số ứng dụng thực tế và cách implement trong Ruby.

Một đồ thị có 2 thành phần

• Nút (hoặc Đỉnh)
• Cạnh

Mỗi một nút sẽ biểu thị cho một phần tử trong đồ thị, ví dụ như một thành phố, một con đường trong một đồ thị mô tả bản đồ. Các cạnh thì sẽ biểu thị cho sự kết nối giữa các nút. Trong khoa học máy tính hoặc toán học, đồ thị thường được xác định bằng công thức G(V, E), với G nghĩa là Graph, V là tập hợp các nút và E là tập hợp các cạnh. Có 2 loại đồ thị cơ bản đó là đồ thị có hướng và đồ thị vô hướng. Đồ thị có hướng là đồ thị mà đồ thị quy định rõ hướng của các cạnh, ví dụ như từ nút A có thể sang nút B nhưng từ nút B chưa chắc có thể sang nút A, còn đồ thị vô hướng là đồ thị không quy định hướng của mỗi cạnh, từ A đi đường sang B thì từ B cũng sẽ đi được sang A. Một loại đồ thị rất phổ biến đó là Directed Acyclic Graph (DAG) nghĩa là đồ thị có hướng không có chu trình. Trong phạm vi của bài viết, tôi chỉ giới thiệu về loại đồ thị này, nếu có thời gian, các bạn có thể tìm hiểu thêm về loại đồ thị này vì tính ứng dụng của nó khá lớn.

Chúng ta đã có một cái nhìn khá tổng quan và cơ bản về đồ thị, còn bây giờ hãy cùng xem một số ứng dụng phổ biến của đồ thị.

• Tìm đường đi ngắn nhất giữa 2 địa điểm
• Kiểm tra xem có đường đi giữa 2 địa điểm không
• ...

Một ứng dụng cũng khá hữu ích đó là tìm kiếm đường đi tốt nhất đến một đích (GPS devices)

Bạn có thể tự implement đồ thị cho riêng mình, tuy nhiên trong bài viết này, chúng ta sẽ sử dụng RGL gem để làm việc với đồ thị. Để tạo một đồ thị cơ bản với RGL gem, chúng ta sẽ làm như sau

require 'rgl/adjacency'
 
graph = RGL::DirectedAdjacencyGraph.new
 
graph.add_edge 1,2
graph.add_edge 3,4
graph.add_edge 1,4
graph.add_edge 4,3

Đoạn code trên sẽ tương ứng với đồ thị sau: Để có được hình ảnh trực quan về đồ thị mà chúng ta vừa tạo ra, bạn có thể sử dụng đoạn code sau:

require 'rgl/dot'
 
graph.print_dotted_on

Công việc còn lại chỉ là copy output vừa nhận được rồi vào một nơi có thể xử lý dot language như https://dreampuf.github.io/GraphvizOnline/, và đây là kết quả chúng ta nhận được Ngoài ra, chúng ta còn có thể cài Graphviz để xuất ra trực tiếp hình ảnh của đồ thị bằng đoạn code sau:

require 'rgl/dot'
graph.write_to_graphic_file('jpg')

Việc tạo đồ thị đã xong, tiếp theo, chúng ta sẽ cùng duyệt qua đồ thị này để tìm hiểu thêm những thông tin về nó.

Có 2 thuật toán cơ bản để tìm kiếm trên đồ thị:

• Breadth-First Search (BFS) (Tìm kiếm theo chiều rộng)
• Depth-First Search (DFS) (Tìm kiếm theo chiều sâu)

Với thuật toán BFS, chúng ta sẽ duyệt theo thứ tự các nút gần nút gốc nhất (nút duyệt đầu tiên). Thuật toán này còn được gọi với cái tên đơn giản và dễ hiểu hơn là thuật toán loang. Còn với thuật toán DFS, bạn sẽ duyệt tuần tự đến khi không thể tiếp tục đi được nữa hoặc gặp nút đã được duyệt, đây chính là lý do cho tên gọi tìm kiếm theo chiều sâu. RGL gem cũng đã implement 2 thuật toán này cho chúng ta:

require 'rgl/traversal'
 
graph.bfs_iterator.to_a
# [1, 2, 4, 3]
 
graph.dfs_iterator.to_a
# [1, 4, 3, 2]

Hãy quan sát lại đồ thị ban đầu và kết quả sau khi duyệt bằng 2 thuật toán BFS và DFS, bạn sẽ hình dung rõ ràng và cụ thể hơn về cách hoạt động của chúng.