Lý thuyết đồ thị thực tế trong Ruby

Có lẽ bạn đã từng nghe qua về cây nhị phân, ví dụ như hình sau:

Vấn đề ở đây là cây nhị phân là một phiên bản đặc biệt của đồ thị, vì vậy chúng ta cần phải có kiến thức về cây nhị phân trước khi muốn biết về lý thuyết đồ thị.

Hãy bắt đầu tìm hiểu về những lý thuyết cơ bản nhất về đồ thị, sau đó chúng ta sẽ đi sâu vào cách sử dụng và cách để áp dụng nó vào trong Ruby!

Cấu trúc của đồ thị bao gồm hai phần tử:

• Nodes (Đỉnh)
• Edges (Cạnh)

Mỗi node sẽ đại diện cho một phần tử trong đồ thị, ví dụ như một thành phố hoặc một con đường, còn đồ thị sẽ ứng với một cái bản đồ. Trong khi đó, các edges sẽ là các mối liên kết giữa các nodes với nhau. Trong sách khoa học máy tính hoặc sách toán cao cấp, bạn sẽ thấy các đồ thị được định nghĩa dưới công thức:

G(V, E).

Trong đó:

• G: Graph (Đồ thị)
• V: Tập các Vertices
• E: Tập các Edges.

Đồ thị có thể có hướng hoặc không có hướng. Điều này có nghĩa là bạn chỉ có thể đi theo một hướng (đồ thị có hướng), hoặc nhiều hướng (đồ thị không có hướng). Loại đồ thị phổ biến nhất là đồ thị Directed Acyclic Graph (DAG). Acyclic nghĩa là sẽ không có trường hợp quay lại.

Bây giờ chúng ta sẽ có một cái nhìn tổng quan về những điều cơ bản về đồ thị, hãy tiến hành xem những ứng dụng phổ biến của đồ thị.

Với đồ thị, bạn có thể làm những điều như là:

• Tìm đường đi ngắn nhất giữa hai địa điểm.
• Kiểm tra hai điểm có mỗi liên quan với nhau không.
• Xây dựng một phần mềm gợi ý.
• Phân tích sự phụ thuộc.

Bạn có thể viết riêng cho mình một cái phần mềm có thể sử dụng đồ thị, nhưng trong bài viết này chúng ta sẽ tập trung vào gem RGL. Để xây dựng đồ thị cơ bản bằng RGL, chúng ta dùng đoạn code 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ẽ xuất ra đồ thị như sau:

Bạn có thể lấy được cái hình như trên bằng đoạn lệnh bên dưới:

require "rgl/dot"
graph.print_dotted_on

Sau đó, chúng ta sẽ copy kết quả mà cái đoạn code trên cho vào trang web sau Graphviz Online. Giờ chúng ta đã có được cái đồ thị như ảnh trên, bạn có thể biết thông tin cụ thể về nó.

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

• Breadth-First Search (BFS)
• Depth-First Search (DFS)

Trong BFS, bạn sẽ bắt đầu từ cái node gần nhất đầu tiên và trong DFS bạn sẽ đi sâu nhất có thể với mỗi node. Những cái thuật toán trên có thể được áp dụng bằng cách sử dụng the stack data structure.

Gem RGL đã nhúng sẵn hai thuật toán trên 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 nhìn lại vào đồ thị và đi theo cái luồng của các luồng của các thuật toán trên cho ra. Nó sẽ giúp bạn hiểu được ý nghĩa của những điều trên.

Chúng ta có thể thêm các trọng số vào trong đồ thị để cho nó có thể hữu dụng hơn. Trọng số được đưa vào các edges, cái mà ở giữa hai nodes. Những trọng số trên đại diện cho giá trị tiêu hao khi đi từ điểm này đến điểm khác. Ví dụ, nếu chúng ta có một cái bản đồ của thành phố dưới dạng một biểu đồ và chúng ta muốn tìm kiếm một địa điểm cụ thể trong thời gian ngắn nhất, các trọng số là thể hiện khoảng cách giữa hai thành phố.

Dưới đây là đoạn code ví dụ cho đồ thị trọng số được mô tả như hình trên:

graph = RGL::DirectedAdjacencyGraph.new
graph.add_vertices "Los Angeles", "New York", "Chicago", "Houston", "Seattle"
 
edge_weights =
{
  ["New York", "Los Angeles"] => 2445,
  ["Los Angeles", "Chicago"] => 2015,
  ["Los Angeles", "Houston"] => 1547,
  ["Chicago", "Houston"] => 939,
  ["Seattle", "Los Angeles"] => 1548
}
 
edge_weights.each { |(city1, city2), w| graph.add_edge(city1, city2) }

Bây giờ chúng ta có thể tìm kiếm đường đi ngắn nhất từ một điểm đến một điểm khác. Và đó chính là nội dung của phần tiếp theo.

Một thuật toán phổ biến để tìm đường đi ngắn nhất trong đồ thị là Dijkstra’s Shortest Path. Cho đồ thị trọng số như trên, chúng ta có thể sử dụng thuật toán Dijkstra’s Shortest Path để giải quyết câu hỏi sau: Đường đi ngắn nhất để đi từ điểm A đến điểm B? Đây là đoạn code mẫu, sử dụng RGL gem:

p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston")
# ["New York", "Los Angeles", "Houston"]

Sau khi chạy đoạn code trên nó sẽ cho chúng ta thấy được đường đi ngắn nhất từ New York đến Houston, sử dụng những thông tin có sẵn trong đồ thị.

Trên đây mình đã giới thiệu về đồ thị cấu trúc dữ liệu và cách sử dụng nó trong RGL gem. Ngoài ra trong bài viết còn có nói đến các thuật toán phổ biến sử dụng trong đồ thị như là: DFS, BFS, và Dijkstra’s.

Tham khảo

Bài viết mình dịch lại của tác giả Jesus Castello từ Black Bytes. Cảm ơn các bạn đã đọc qua.