Đây là phần tiếp theo trong series "Khoa học Máy tính Thực hành", nơi bạn sẽ học cách áp dụng các khái niệm khoa học máy tính kinh điển để giải quyết vấn đề thực tế dùng Ruby.
Hôm nay chúng ta sẽ nói về Lý thuyết Đồ thị.
Bạn có thể đã nghe về cây nhị phân, chúng trông như thế này:
Vấn đề là cây nhị phân chỉ là phiên bản đặc biệt của đồ thị, vì vậy đó sẽ cho bạn ý tưởng đồ thị phổ biến như thế nào.
Hãy bắt đầu với tổng quan cơ bản lý thuyết đồ thị, sau đó xem một số ứng dụng thực tế và cách triển khai trong Ruby!
Cơ bản về Đồ thị
Đồ thị bao gồm hai yếu tố:
- Nút (hoặc đỉnh)
- Cạnh
Một nút đại diện cho một phần tử trong đồ thị, như thành phố hoặc đường phố, trong đồ thị biểu diễn bản đồ. Trong khi cạnh đại diện cho kết nối giữa các nút.
Nếu bạn nhìn sách khoa học máy tính hoặc toán học, bạn sẽ thấy đồ thị được định nghĩa bằng công thức này: G(V, E).
Ở đâu G có nghĩa là Graph, V là tập đỉnh và E là tập cạnh.
Đồ thị có thể có hướng hoặc không hướng. Nghĩa là bạn chỉ đi một chiều (đồ thị có hướng) hoặc cả hai chiều (đồ thị không hướng).
Loại đồ thị phổ biến nhất là Đồ thị Có hướng Không Chu trình (DAG). Không chu trình nghĩa là không có vòng lặp, không có cách nào quay lại.
Ứng dụng của Đồ thị
Bây giờ chúng ta đã xem tổng quan cơ bản, hãy xem một số ứng dụng phổ biến cho đồ thị.
Dùng đồ thị bạn có thể làm những việc như:
- Tìm đường đi ngắn nhất (hoặc dài nhất) giữa hai vị trí
- Kiểm tra hai thứ có liên quan đến nhau không
- Xây dựng máy gợi ý
- Phân tích phụ thuộc
Ví dụ khác bao gồm tìm đường tốt nhất đến đích (nghĩ đến thiết bị GPS).
Cách Triển khai & Sử dụng Đồ thị
Bạn có thể tự viết triển khai đồ thị, nhưng cho bài này chúng ta sẽ dùng gem RGL đã triển khai sẵn cho chúng ta.
Để tạo đồ thị cơ bản dùng RGL:
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
Mã này tạo ra đồ thị sau:
Bạn có thể lấy biểu diễn đồ họa của đồ thị như thế này:
require 'rgl/dot' graph.print_dotted_on
Sau đó sao chép đầu ra của phương thức đó trên trang web có thể xử lý ngôn ngữ dot. Như cái này.
Thay vào đó, bạn có thể cài Graphviz trên máy để tạo hình ảnh cục bộ.
Bây giờ chúng ta có đồ thị, chúng ta có thể muốn duyệt nó để tìm thông tin về nó.
Có hai thuật toán cơ bản tìm kiếm đồ thị:
- Tìm kiếm Rộng (BFS)
- Tìm kiếm Sâu (DFS)
Trong BFS bạn nhận nút gần nhất trước và trong DFS bạn đi sâu nhất có thể cho mỗi nút. Các thuật toán này có thể triển khai dùng cấu trúc dữ liệu stack.
Gem RGL đã triển khai sẵn các thuật toán đó cho bạn:
require 'rgl/traversal' graph.bfs_iterator.to_a # [1, 2, 4, 3] graph.dfs_iterator.to_a # [1, 4, 3, 2]
Nhìn lại đồ thị và theo dõi đường đi các thuật toán này làm chỉ bằng mắt (hoặc ngón tay nếu bạn muốn). Điều đó sẽ giúp bạn cảm nhận chuyện gì đang xảy ra.
Đồ thị Có Trọng số
Chúng ta có thể thêm thông tin cho đồ thị dưới dạng trọng số để làm nó hữu ích hơn.
Trọng số được gán cho cạnh, là đường đi giữa hai nút (còn gọi là "đỉnh"). Trọng số này đại diện cho chi phí đi từ điểm này đến điểm kia.
Ví dụ, nếu chúng ta có bản đồ một quốc gia dạng đồ thị và muốn đến đích nào đó trong thời gian ngắn nhất, trọng số sẽ đại diện cho khoảng cách giữa hai thành phố.
Hoặc nếu chúng ta có mạng máy tính, trọng số có thể đại diện cho số nhảy (hop) cần để đạt mạng nào đó.
"Trong mạng máy tính, một hop là một phần của đường đi giữa nguồn và đích. Gói tin đi qua cầu, router và gateway khi di chuyển giữa nguồn và đích. Mỗi lần gói tin được truyền đến thiết bị mạng tiếp theo, một hop xảy ra." — Wikipedia
Đây là ví dụ mã cho đồ thị có trọng số:
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) }
Chúng ta giờ có thể tìm đường đi ngắn nhất từ điểm này đến điểm kia. Và đó chính là chủ đề phần tiếp theo!
Tìm Đường đi Ngắn nhất
Một thuật toán phổ biến tìm đường đi ngắn nhất trong đồ thị là thuật toán "Đường đi Ngắn nhất Dijkstra".
Cho một đồ thị có trọng số, chúng ta có thể dùng thuật toán Dijkstra để giải quyết câu hỏi:
"Cách nhanh nhất từ điểm A đến điểm B là gì?"
Đây là ví dụ mã, dùng gem RGL:
p graph.dijkstra_shortest_path(edge_weights, "New York", "Houston") # ["New York", "Los Angeles", "Houston"]
Điều này cho chúng ta đường đi ngắn nhất từ New York đến Houston, dùng thông tin có trong đồ thị.
Tóm tắt
Bạn đã học cấu trúc dữ liệu đồ thị là gì và cách dùng nó với gem RGL.
Bạn cũng đã học về thuật toán phổ biến làm việc với đồ thị, như DFS, BFS và Dijkstra.
Đừng quên chia sẻ bài viết này nếu bạn thấy hữu ích để nhiều người hơn có thể tận hưởng 🙂