Các thao tác cơ bản trên đồ thị

Các thao tác cơ bản trên đồ thị có thể được chia thành các thao tác trên "cạnh" và các thao tác trên "đỉnh". Cách triển khai của chúng khác nhau tùy thuộc vào việc đồ thị được biểu diễn bằng "ma trận kề" hay "danh sách kề".

Triển khai dựa trên ma trận kề

Cho một đồ thị vô hướng có \(n\) đỉnh, các thao tác khác nhau được triển khai như mô tả trong hình dưới đây.

• Thêm hoặc xóa một cạnh: Trực tiếp sửa đổi cạnh đã chỉ định trong ma trận kề, tốn thời gian \(O(1)\). Vì đây là đồ thị vô hướng, cả hai chiều của cạnh cần được cập nhật đồng thời.
• Thêm một đỉnh: Thêm một hàng và một cột ở cuối ma trận kề rồi lấp đầy tất cả bằng các số \(0\), tốn thời gian \(O(n)\).
• Xóa một đỉnh: Xóa một hàng và một cột trong ma trận kề. Trường hợp xấu nhất xảy ra khi xóa hàng và cột đầu tiên, yêu cầu \((n-1)^2\) phần tử phải "dịch chuyển lên trên và sang trái", do đó tốn thời gian \(O(n^2)\).
• Khởi tạo: Cho \(n\) đỉnh, khởi tạo một danh sách đỉnh vertices có chiều dài \(n\), tốn thời gian \(O(n)\); khởi tạo một ma trận kề adjMat kích thước \(n \times n\), tốn thời gian \(O(n^2)\).

<1><2><3><4><5>

Dưới đây là mã nguồn triển khai cho đồ thị được biểu diễn bằng ma trận kề:

[file]{graph_adjacency_matrix}-[class]{graph_adj_mat}-[func]{}

Triển khai dựa trên danh sách kề

Cho một đồ thị vô hướng có tổng cộng \(n\) đỉnh và \(m\) cạnh, các thao tác khác nhau có thể được triển khai như mô tả trong hình dưới đây.

• Thêm một cạnh: Thêm cạnh vào cuối danh sách liên kết của đỉnh tương ứng, tốn thời gian \(O(1)\). Vì đây là đồ thị vô hướng, các cạnh ở cả hai chiều cần được thêm vào đồng thời.
• Xóa một cạnh: Tìm và xóa cạnh đã chỉ định trong danh sách liên kết của đỉnh tương ứng, tốn thời gian \(O(m)\). Trong đồ thị vô hướng, các cạnh ở cả hai chiều cần được xóa đồng thời.
• Thêm một đỉnh: Thêm một danh sách liên kết vào danh sách kề, với đỉnh mới làm nút đầu (head node), tốn thời gian \(O(1)\).
• Xóa một đỉnh: Duyệt qua toàn bộ danh sách kề và xóa tất cả các cạnh chứa đỉnh đã chỉ định, tốn thời gian \(O(n + m)\).
• Khởi tạo: Tạo \(n\) đỉnh và \(2m\) cạnh trong danh sách kề, tốn thời gian \(O(n + m)\).

<1><2><3><4><5>

Mã nguồn dưới đây thể hiện cách triển khai danh sách kề. So với hình trên, mã nguồn thực tế có một số điểm khác biệt như sau.

• Để thuận tiện cho việc thêm và xóa đỉnh, cũng như để đơn giản hóa mã nguồn, chúng ta sử dụng danh sách (mảng động) thay vì danh sách liên kết.
• Một bảng băm được sử dụng để lưu trữ danh sách kề, trong đó key là thực thể đỉnh và value là danh sách (danh sách liên kết) các đỉnh kề của đỉnh đó.

Ngoài ra, sở dĩ chúng ta sử dụng lớp Vertex để biểu diễn các đỉnh trong danh sách kề là vì: nếu chúng ta sử dụng chỉ số danh sách để phân biệt các đỉnh khác nhau giống như với ma trận kề, thì để xóa đỉnh tại chỉ số \(i\), chúng ta sẽ cần phải duyệt qua toàn bộ danh sách kề và giảm tất cả các chỉ số lớn hơn \(i\) đi \(1\), điều này rất kém hiệu quả. Tuy nhiên, nếu mỗi đỉnh là một thực thể Vertex duy nhất, việc xóa một đỉnh sẽ không yêu cầu sửa đổi các đỉnh khác.

[file]{graph_adjacency_list}-[class]{graph_adj_list}-[func]{}

So sánh hiệu quả

Giả sử đồ thị có \(n\) đỉnh và \(m\) cạnh, bảng dưới đây so sánh hiệu quả thời gian và hiệu quả không gian của ma trận kề và danh sách kề. Lưu ý rằng danh sách kề (danh sách liên kết) tương ứng với cách triển khai được sử dụng trong phần này, trong khi danh sách kề (bảng băm) đề cập cụ thể đến cách triển khai mà toàn bộ các danh sách liên kết được thay thế bằng bảng băm.

Bảng   So sánh ma trận kề và danh sách kề

	Ma trận kề	Danh sách kề (danh sách liên kết)	Danh sách kề (bảng băm)
Xác định sự kề nhau	\(O(1)\)	\(O(n)\)	\(O(1)\)
Thêm một cạnh	\(O(1)\)	\(O(1)\)	\(O(1)\)
Xóa một cạnh	\(O(1)\)	\(O(n)\)	\(O(1)\)
Thêm một đỉnh	\(O(n)\)	\(O(1)\)	\(O(1)\)
Xóa một đỉnh	\(O(n^2)\)	\(O(n + m)\)	\(O(n)\)
Không gian chiếm dụng	\(O(n^2)\)	\(O(n + m)\)	\(O(n + m)\)

Quan sát bảng trên, có vẻ như danh sách kề (bảng băm) có hiệu quả thời gian và hiệu quả không gian tốt nhất. Tuy nhiên, trong thực tế, các thao tác trên cạnh trong ma trận kề sẽ hiệu quả hơn, chỉ yêu cầu một thao tác truy cập hoặc gán mảng duy nhất. Nhìn chung, ma trận kề thể hiện nguyên lý "đánh đổi không gian lấy thời gian", trong khi danh sách kề thể hiện việc "đánh đổi thời gian lấy không gian".