Cách cài đặt đồ thị ( lập trình).doc

Cách cài đặt đồ thị bằng phương pháp lập trình hướng đối tượng

Đồ 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)
Là khả năng mở rộng chương trình mà kô phải tốn nhiều công sức thiết kế lại kiến trúc của nó. Chẳng hạn: đồ thị chúng ta sẽ cài đặt ở đây là đồ thị không trọng số,giả sử sau này ta muốn mở rộng sang loại đồ thị có trọng số thì toàn bộ kiến trúc của chương trình không được phép sụp đổ và phải thiết kế lại. Đây là một yêu cầu rất quan trọng trong lĩnh vực phát triển phần mềm vì khách hàng sau khi sử dụng phần mêm một thời gian thường có nhu cầu bổ sung các chức năng mới hoặc thay đổi một số chức năng của chương trình (change requests)
c) Khả năng sử dụng lại (resuable)
Đó là khi những đoạn mã chúng ta viết một lần và luôn có thể được sử dụng lại cho các ứng dụng tiếp theo. Ví dụ như: ta bỏ công ra để cài đặt đồ thị này, sau này có một lúc nào đấy ta nghiên cứu về mạng Neuron của lĩnh vực trí tuệ nhân tạo (AI). Vì mạng Neuron thực chất cũng là một đồ thị, ta có thể sử dụng lại các lớp (class) mà ta viết hôm này với khả năng kế thừa của OOP rồi thay đổi một số thuộc tính (Attribute) hoặc phương thức (Method) cho phù hợp với yêu cầu bài toán mới, ta có thể giải quyết vấn đề mới trong thời gian ngắn hơn nhiều là khi ta phải làm mọi thứ từ đầu. Đấyâu cũng là một nét đẹp của OOP vậy!
Một đồ thị có nghĩa vụ cần cung cấp những giao tiếp (Methods) cơ bản sau đây:
-lấy số đỉnh của đồ thị: v()
-lấy số cạnh của đồ thi: e()
-thêm một cạnh vào đồ thị: add(int u, int v)
-xóa một cạnh khỏi đồ thị: remove(int u, int v)
-kiểm tra một cạnh có thuộc đồ thị hay không: contains(int u, int v) ?
-lấy ra tất cả các đỉnh kề với một đỉnh cho trước: adj(int u)
-hiển thị đồ thị ra màn hình. displayGraph()
Với Java ta có thể mô tả “định nghĩa” một đồ họa như trên bằng interface như sau:
public interface Graph
{
boolean add(int u, int v);
boolean remove(int u, int v);
List adj(int u);
boolean contains(int u, int v);
int v();
int e