Graph - Đồ thị
1. Giới thiệu
Đồ thị là một cấu trúc dữ liệu để lưu trữ dữ liệu được kết nối như một mạng người trên nền tảng của xã hội. Nghe có vẻ khó hình dung, nhưng hãy theo dõi tiếp chi tiết bên dưới.
Một đồ thị bao gồm các đỉnh và các cạnh. Một đỉnh đại diện cho thực thể (ví dụ: con người) và một cạnh đại diện cho mối quan hệ giữa các thực thể (ví dụ: tình bạn của một người).
Với A, B, C, D, E là đại diện cho tên một người cụ thể.
Ở đây, chúng ta đã xác định một đồ thị đơn giản với năm đỉnh và sáu cạnh. Các vòng tròn là các đỉnh đại diện cho người và các đường nối hai đỉnh là các cạnh đại diện cho tình bạn trong một mối quan hệ nào đó.
Có một vài biến thể của đồ thị đơn giản này tùy thuộc vào thuộc tính của các cạnh. Chúng ta hãy lướt qua chúng trong các phần tiếp theo.
Tuy nhiên, chúng ta sẽ chỉ tập trung vào đồ thị đơn giản được trình bày bên trên cho các ví dụ Java trong nội dung được chia sẻ của bài viết này.
Đồ thị có hướng
Đồ thị chúng ta đã xác định bên trên chỉ có các cạnh mà không có bất kỳ hướng nào. Nếu các cạnh này có hướng xác định, chúng sẽ trở thành đồ thị có hướng.
Chúng ta có thể thấy rằng các cạnh có hướng cố định. Các cạnh cũng có thể là hai hướng.
Đồ thị có trọng số
Một lần nữa, đồ thị đơn giản của chúng ta có các cạnh vô hướng hoặc không có trọng số. Nếu thay vào đó, các cạnh này mang trọng số tương đối, thì đồ thị này được gọi là đồ thị có trọng số.
Một ví dụ về một ứng dụng thực tế của điều này có thể thể hiện thông qua thời gian quen biết của các mối quan hệ của các đối tượng:
Đồ thị có trọng số cung cấp thông tin cực kì quan trọng cho lập trình viên giải quyết các vấn đề. Dễ hình dung nhất là các thành phố trên bản đồ và khoảng cách giữa chúng.
2. Biểu diễn đồ thị
Một đồ thị có thể được biểu diễn ở các dạng khác nhau như ma trận kề và danh sách kề. Mỗi cái đều có ưu và nhược điểm trong cách thiết lập khác nhau.
Chúng ta sẽ xem qua một số cách biểu diễn đồ thị sau đây:
Ma trận kề
Ma trận kề là một ma trận vuông có kích thước tương đương với số đỉnh trong đồ thị. Các phần tử của ma trận thường có giá trị “0” hoặc “1”. Giá trị ‘1’ biểu thị sự liền kề giữa các đỉnh trong hàng và cột và giá trị ‘0’ nếu không có liên kết.
Hãy xem ma trận kề trông như thế nào đối với đồ thị đơn giản của chúng ta từ phần trước: | | A | B | C | D | E | |—|—|—|—|—|—| | A | 0 | 1 | 0 | 1 | 0 | | B | 1 | 0 | 1 | 0 | 1 | | C | 0 | 1 | 0 | 1 | 0 | | D | 1 | 0 | 1 | 0 | 1 | | E | 0 | 1 | 0 | 1 | 0 |
Biểu diễn này khá dễ thực hiện và cũng hiệu quả để truy vấn. Tuy nhiên, nó kém hiệu quả chiếm dụng khá nhiều không gian.
Danh sách kề
Một danh sách kề không là gì ngoài một mảng danh sách. Kích thước của mảng tương đương với số đỉnh trong đồ thị.
Danh sách tại một chỉ số cụ thể của mảng đại diện cho các đỉnh liền kề của đỉnh được đại diện bởi chỉ số mảng đó.
Hãy xem danh sách kề trông như thế nào cho đồ thị đơn giản của chúng ta ở phần trước:
Biểu diễn này tương đối khó tạo và ít hiệu quả để truy vấn. Tuy nhiên, nó mang lại hiệu quả về không gian tốt hơn.
Chúng ta sẽ sử dụng danh sách kề để biểu diễn đồ thị cho các ví dụ bên dưới.
3. Đồ thị trong Java
Java không có triển khai mặc định của cấu trúc dữ liệu đồ thị.
Tuy nhiên, chúng ta có thể triển khai biểu đồ bằng cách sử dụng Java Collections.
Để xác định một đỉnh trong Java, ta có thể làm như sau:
1
2
3
4
5
6
7
8
class Vertex {
String label;
Vertex(String label) {
this.label = label;
}
// equals and hashCode
}
Định nghĩa ở trên về đỉnh chỉ có một nhãn nhưng điều này có thể đại diện cho bất kỳ thực thể có thể nào như Người hoặc Thành phố.
Ngoài ra, hãy lưu ý rằng chúng ta phải ghi đè các phương thức equals() và hashCode() vì những phương thức này cần thiết để hoạt động với Java Collections.
Như chúng ta đã thảo luận trước đó, một đồ thị không là gì khác ngoài tập hợp các đỉnh và cạnh có thể được biểu diễn dưới dạng ma trận kề hoặc danh sách kề. Hãy xem cách chúng ta có thể xác định điều này bằng cách sử dụng danh sách kề ở đây:
1
2
3
4
5
class Graph {
private Map<Vertex, List<Vertex>> adjVertices;
// constructor, getters, setters
}
Như chúng ta có thể thấy, lớp Graph đang sử dụng Map từ Java Collections để xác định danh sách kề.
Có thể thực hiện một số thao tác trên cấu trúc dữ liệu đồ thị, chẳng hạn như tạo, cập nhật hoặc tìm kiếm thông qua đồ thị. Chúng ta sẽ đi qua một số thao tác phổ biến hơn và xem cách chúng ta có thể triển khai chúng trong Java.
4. Một số thao tác phổ biến trên đồ thị
Thêm và xoá đỉnh: Các hàm này chỉ đơn giản là thêm và bớt các phần tử khỏi Tập đỉnh.
1
2
3
4
5
6
7
8
9
void addVertex(String label) {
adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>());
}
void removeVertex(String label) {
Vertex v = new Vertex(label);
adjVertices.values().stream().forEach(e -> e.remove(v));
adjVertices.remove(new Vertex(label));
}
Thêm cung (cạnh): hàm này tạo một Cung mới và cập nhật các đỉnh liền kề
1
2
3
4
5
6
void addEdge(String label1, String label2) {
Vertex v1 = new Vertex(label1);
Vertex v2 = new Vertex(label2);
adjVertices.get(v1).add(v2);
adjVertices.get(v2).add(v1);
}
Theo cách tương tự, chúng ta sẽ định nghĩa phương thức removeEdge():
1
2
3
4
5
6
7
8
9
10
void removeEdge(String label1, String label2) {
Vertex v1 = new Vertex(label1);
Vertex v2 = new Vertex(label2);
List<Vertex> eV1 = adjVertices.get(v1);
List<Vertex> eV2 = adjVertices.get(v2);
if (eV1 != null)
eV1.remove(v2);
if (eV2 != null)
eV2.remove(v1);
}
Tiếp theo, hãy xem cách chúng ta có thể tạo đồ thị đơn giản mà chúng ta đã vẽ trước đó bằng các hàm chúng ta đã xác định:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Graph createGraph() {
Graph graph = new Graph();
graph.addVertex("A");
graph.addVertex("B");
graph.addVertex("C");
graph.addVertex("D");
graph.addVertex("E");
graph.addEdge("A", "B");
graph.addEdge("A", "D");
graph.addEdge("B", "C");
graph.addEdge("D", "C");
graph.addEdge("B", "E");
graph.addEdge("D", "E");
return graph;
}
Cuối cùng chúng ta sẽ xác định một phương thức để lấy các đỉnh liền kề của một đỉnh cụ thể:
1
2
3
List<Vertex> getAdjVertices(String label) {
return adjVertices.get(new Vertex(label));
}
5. Duyệt đồ thị
Bây giờ chúng ta đã xác định cấu trúc dữ liệu đồ thị và các hàm để tạo và cập nhật nó, chúng ta có thể xác định một số hàm bổ sung để duyệt đồ thị. Chúng ta cần duyệt qua một đồ thị để thực hiện bất kỳ hành động có ý nghĩa nào, chẳng hạn như tìm kiếm.
Có hai cách khả thi để duyệt một đồ thị, duyệt theo chiều sâu và duyệt theo chiều rộng.
Depth-First Traversal - Duyệt theo chiều sâu
Một đường đi “theo chiều sâu” bắt đầu từ một đỉnh gốc tùy ý và duyệt qua các đỉnh càng sâu càng tốt dọc theo mỗi nhánh trước khi duyệt đến các đỉnh ở cùng một bậc.
Code demo cho hàm duyệt theo chiều sâu:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Set<String> depthFirstTraversal(Graph graph, String root) {
Set<String> visited = new LinkedHashSet<String>();
Stack<String> stack = new Stack<String>();
stack.push(root);
while (!stack.isEmpty()) {
String vertex = stack.pop();
if (!visited.contains(vertex)) {
visited.add(vertex);
for (Vertex v : graph.getAdjVertices(vertex)) {
stack.push(v.label);
}
}
}
return visited;
}
Chúng ta có thể sử dụng một Ngăn xếp để lưu trữ các đỉnh cần được duyệt qua.
1
assertEquals("[A, D, E, B, C]", depthFirstTraversal(graph, "A").toString());
Lưu ý rằng đỉnh “A” làm gốc của quá trình duyệt này, nhưng bạn có thể thử với bất kỳ đỉnh nào khác.
Breadth-First Traversal – Duyệt theo chiều rộng
Nói một cách tương đối thì đây là một đường đi ngang theo chiều rộng bắt đầu ở một đỉnh gốc tùy ý và duyệt qua tất cả các đỉnh lân cận ở cùng một bậc trước khi đi sâu hơn vào đồ thị.
Code demo cho hàm duyệt theo chiều rộng:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
Set<String> breadthFirstTraversal(Graph graph, String root) {
Set<String> visited = new LinkedHashSet<String>();
Queue<String> queue = new LinkedList<String>();
queue.add(root);
visited.add(root);
while (!queue.isEmpty()) {
String vertex = queue.poll();
for (Vertex v : graph.getAdjVertices(vertex)) {
if (!visited.contains(v.label)) {
visited.add(v.label);
queue.add(v.label);
}
}
}
return visited;
}
Lưu ý rằng: Phương pháp duyệt này sử dụng Hàng đợi để lưu trữ các đỉnh cần được duyệt.
1
assertEquals("[A, B, D, C, E]", breadthFirstTraversal(graph, "A").toString());
Tương tự, A là đỉnh gốc cho lần duyệt này, bạn có thể chọn đỉnh khác tuỳ ý.
6. Một số thư viện đáng chú ý
Trong Java không cần thiết phải luôn triển khai đồ thị ngay từ đầu. Có một số thư viện mã nguồn mở và được sàn lọc cẩn thận có thể giúp ích cho bạn khá nhiều.
JGraphT
JGraphT là một trong những thư viện phổ biến nhất trong Java cho cấu trúc dữ liệu đồ thị. Nó cho phép tạo một đồ thị đơn giản, đồ thị có hướng, đồ thị có trọng số, v.v. Ngoài ra, nó cung cấp nhiều thuật toán có thể có trên cấu trúc dữ liệu đồ thị.
Link: https://jgrapht.org/
Google Guava
Google Guava là một bộ thư viện Java cung cấp một loạt các chức năng bao gồm cấu trúc dữ liệu biểu đồ và các thuật toán của nó. Nó hỗ trợ tạo Graph, ValueGraph và Network đơn giản. Chúng có thể được định nghĩa là Mutable hoặc Immutable.
Link: https://github.com/google/guava/wiki/GraphsExplained
Apache Commons
Apache Commons là một dự án Apache cung cấp các Java component có thể tái sử dụng. Điều này bao gồm Commons Graph cung cấp một bộ công cụ để tạo và quản lý cấu trúc dữ liệu đồ thị. Đồng thời cũng cung cấp các thuật toán đồ thị chung để hoạt động trên cấu trúc dữ liệu.
Link: https://commons.apache.org/sandbox/commons-graph/
Sourceforge JUNG
Java Universal Network / Graph (JUNG) là Java framework có thể mở rộng để mô hình hóa, phân tích và trực quan hóa bất kỳ dữ liệu nào có thể được biểu diễn dưới dạng đồ thị.
JUNG hỗ trợ một số thuật toán bao gồm các quy trình như phân cụm, phân tách và tối ưu hóa.
Các thư viện này cung cấp một số cách triển khai dựa trên cấu trúc dữ liệu đồ thị. Ngoài ra còn có nhiều framework mạnh mẽ hơn dựa trên đồ thị, chẳng hạn như Apache Giraph, hiện đang được sử dụng tại Facebook để phân tích đồ thị do người dùng của họ tạo ra và Apache TinkerPop, thường được sử dụng trên cơ sở dữ liệu đồ thị.
Link: http://jung.sourceforge.net/
Lời kết
Như vậy - trong bài viết này, chúng ta đã thảo luận về đồ thị như một cấu trúc dữ liệu cùng với các biểu diễn của nó.
Chúng ta đã xác định một đồ thị rất đơn giản trong Java bằng cách sử dụng Java Collections và cũng xác định các phương pháp duyệt cho loại cấu trúc dữ liệu này.
Đây là loại cấu trúc dữ liệu khá khó và hầu như chỉ ứng dụng trong các dự án đặc thù. Thông qua các code mẫu bên trên, bạn có thể tự ghép chúng lại và thêm – bớt các khai báo cần thiết để có cho mình một File hoàn chỉnh nhé.
Túm lại, Đồ thị là một kiến thức nên học, có thể nó đã được giảng dạy ở nhà trường bằng ngôn ngữ này hay ngôn ngữ khác nhưng kiến thức cốt lõi của nó vẫn là vũ khí để các nhà tuyển dụng đansh gục bạn. Hãy chuẩn bị cẩn thận nhaaa.!
Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!
Happy coding! 😎 👍🏻 🚀 🔥