Một cách cài đặt đồ thị bằng phương pháp lập trình hướng đối tượng
Trần Minh Quang
Đồ thị (Graph) có thể nói là một trong những cấu trúc rời rạc thường được sử dụng nhất
trong ngành khoa học máy tính. Mỗi khi cần mô hình hóa một tập đối tượng cùng với các
mối quan hệ giữa chúng, chúng ta luôn có thể trừa tượng hóa (abstract) chúng bằng đồ thị.
Một mạng giao thông, mạng máy tính, quan hệ quen biết giữa một nhóm người, quan hệ về
sở thích (A thích ăn cam, B thích ăn quýt)…v…v. tất cả đều có thể đưa về mô hình của
một đồ thị.
Mục đích của bài viết tuy nhiên không phải là giới thiệu lý thuyết về đồ thị cũng như
phương pháp lập trình hướng đối tượng mà muốn trình bày một cách cài đặt đồ thị tương
đối hiệu quả bằng phương pháp lập trình hướng đối tượng bằng ngôn ngữ lập trình Java.
Vì vậy, tác giả xem như người đọc đã biết lý thuyết về đồ thị cũng như lập trình hướng đối
tượng trên Java.
I. Nhắc lại khái niệm của đồ thị
Đồ thị G được cấu thành từ một tập hợp các đỉnh (Vertices) và các cạnh (Edges) ký hiệu là
G = (V, E).
Đồ thị G gọi là đồ thị vô hướng nếu các cạnh của G không có thứ tự, tức là chúng không
phân biệt cạnh AB với BA (tương tự đường 2 chiều).
Đồ thị G gọi là đồ thị vô hướng nếu các cạnh của G có thứ tự, tức là cạnh AB khác với
cạnh BA (tương tự đường 1 chiều).
Đồ thị có trọng số là đồ thị trong đó mỗi cạnh của đồ thị được gán bằng trọng số (khoảng
cách, chi phí..v..v).
II. Phân tích & Thiết kế
Như thường lệ, khi bắt đầu thiết kế một chương trình hướng đối tượng chúng ta thường
phải đặt ra các mục tiêu sau đây:
a. Mô tả (interface) của đồ thị phải độc lập với các biến thể cài đặt chúng
Vì đồ thị là một khái niệm chung chung, có rất nhiều cách đề cài đặt nó. Người này có thể
cài đặt bằng phương pháp danh sách cạnh kề (Adjacency List), người kia lại thích bằng ma
trận (matrix). Kiến trúc (Architecture) của chương trình chúng ta phải đảm bảo tách rời
interface một đồ thị với các biến thể cài đặt chúng.
b. Khả năng mở rộng (scalable)

boolean contains(int u, int v);
int v();
int e();
void displayGraph();
}
Có một điều cần lưu ý là chúng ta cần hết sức thận trọng khi thiết kế một interface!. Khi
một lớp (class) cài đặt một interface thì nó phải cài đặt tất cả các phương thức của interface
ấy, chẳng hạn: ta cài đặt đồ họa bằng ma trận vào gọi lớp này là: GraphMatrix. Ta sẽ có
khai báo là: GraphMatrix implements Graph. Khi đấy trong phần cài đặt của lớp
GraphMatrix nhất thiết phải chứa đầy đủ 7 phương thức của interface Graph từ ađ(int u,
int v) cho đến displayGraph().
Lại giả sử rằng ta viết một thư viện cài đặt đồ thị trong đó interface Graph của chúng ta
chứa 7 phương thức như ở trên. Một công ty phần mềm mua thư viện này về và khi dẫn
xuất (extends) interface Graph của chúng ta họ sẽ phải cài đặt đủ 7 phương thức này.
Một thời gian sau, chúng ta thấy cảm thấy không ưng ý về interface Graph ở trên và muốn
thêm vào một vài phương thức mới ví dụ như: gradeSequence() đưa ra danh sách các bậc
của các đỉnh của đồ thị chẳng hạn…v…v. Sau khi sửa đổi lại thư viện, công ty nọ cũng
nhận được một bản cập nhật như theo thỏa thuận với interface Graph chúng ta vừa sửa
đổi này.
Và tại họa đã xảy ra….toàn bộ những chương trình mà công ty đã viết sử dụng interface
Graph đều không họat động nữa vì các lớp cài đặt interface Graph đều không cài đặt các
phuơng phức mới thêm vào interface sau này (như gradeSequence()).
Bài học rút ra ở đây là: việc thiết kế interface đòi hỏi chúng ta phải nhìn trước được tất cả
các phương thức mà interface cung cấp. Điều này tất nhiên là không hề đơn giản chút nào!!
Quay trở lại với interface Graph. Nếu suy nghĩ kỹ ta sẽ nhận thấy một trong những thao tác
quan trọng đối với một đồ thị là duyệt đồ thị theo một thứ tự nào đấy (chẳng hạn theo
chiều rộng BFS, hoặc chiều sâu DFS). Với Java điều này tương đương với “Graph is
iterable”. Java cung cấp interface “Iterable”, theo Java SDK Documentation:
public interface Iterable
{

public GraphMatrix(int v)
{
//Only allow positive number of vertices
if (v > 0)
{
this.e = 0;
this.v = v;
//Connected array is automatically initialized with “false”
connected = new boolean[v][v];
}
}

public boolean ađ(int u, int v)
{
if (!isValidNode(u) || !isValidNode(v) || (u == v) || contains(u, v))
return false;

connected[u][v] = true;
connected[v][u] = true;
this.e++;
return true;
}

public boolean remove(int u, int v)
{
if (!isValidNode(u) || !isValidNode(v) || (u == v) || !contains(u, v))
return false;

connected[u][v] = false;
connected[v][u] = false;