Giáo trình Cấu trúc dữ liệu và giải thuật - Chương 13: Đồ thị

hay 
đổi mà chúng ta đã làm đối với tập X như sau: với mỗi w chưa có trong X, nếu có 
Hình 13.13 – Ví dụ về giải thuật Prim 
Chương 13 – Đồ thị 
Giáo trình Cấu trúc dữ liệu và Giải thuật 361
một cạnh nối ν và w, chúng ta xem thử tải trọng của cạnh này có nhỏ hơn 
distance[w] hay không, nếu quả thực như vậy thì distance[w] cần được cập 
nhật lại bằng trị của tải trọng này, và neighbor[w] sẽ là ν. 
Lấy ví dụ, chúng ta hãy xem xét mạng trong hình (a) của hình 13.13. Trạng 
thái ban đầu trong hình (b): Tập X (các đỉnh được tô màu) chỉ gồm đỉnh nguồn 0, 
và đối với mỗi đỉnh w, đỉnh được lưu trong neighbor[w] được chỉ bởi các mũi tên 
từ w. Trị của distance[w] là tải trọng của cạnh tương ứng. Khoảng cách từ 
nguồn đến đỉnh 1 là một trong những trị nhỏ nhất, nên 1 được thêm vào X như 
hình (c), và trong các phần tử của các mảng neighbor và distance chỉ có các 
phần tử tương ứng với đỉnh 2 và đỉnh 5 là được cập nhật lại. Đỉnh kế tiếp gần với 
các đỉnh trong X nhất là đỉnh 2, nó được thêm vào X như hình (d), trong này 
cũng đã chỉ ra các trị của các mảng đã được cập nhật lại. Các bước cuối cùng được 
minh họa trong hình (e), (f) và (g). 
13.6.3. Hiện thực 
Để hiện thực giải thuật Prim, chúng ta cần chọn một lớp để biểu diễn cho 
mạng. Sự tương tự của giải thuật này so với giải thuật tìm đường ngắn nhất trong 
phần trước giúp chúng ta quyết định thiết kế lớp Network dẫn xuất từ lớp 
Digraph. 
template 
class Network: public Digraph { 
public: 
 Network(); 
 void read(); // Định nghĩa lại để nhập thông tin về mạng. 
 void make_empty(int size = 0); 
 void add_edge(Vertex v, Vertex w, Weight x); 
 void minimal_spanning(Vertex source, 
 Network &tree) const; 
}; 
Chúng ta sẽ viết lại phương thức nhập read để đảm bảo rằng tải trọng của 
cạnh (ν, w) luôn trùng với tải trọng của cạnh (w, ν), với mọi ν và w, vì đây là một 
mạng vô hướng. Phương thức mới make_empty(int size) tạo một mạng có 
size đỉnh và không có cạnh. Phương thức khác, add_edge, thêm một cạnh có 
một tải trọng cho trước vào mạng. Chúng ta cũng đã giả sử rằng lớp Weight đã có 
đầy đủ các toán tử so sánh. Ngoài ra, người sử dụng cần khai báo trị lớn nhất có 
thể của Weight gọi là infinity. Phương thức minimal_spanning mà chúng ta 
sẽ viết ở đây sẽ tìm cây phủ tối tiểu và trả về qua tham biến tree. Tuy phương 
thức chỉ có thể tìm cây phủ khi thực hiện trên một mạng liên thông, nó cũng có 
thể tìm một cây phủ cho một thành phần liên thông có chứa đỉnh source trong 
mạng. 
Chương 13 – Đồ thị 
Giáo trình Cấu trúc dữ liệu và Giải thuật 362
template 
void Network::minimal_spanning(Vertex source, 
 Network &tree) const 
/* 
post: Xác định cây phủ tối tiểu trong thành phần liên thông có chứa đỉnh source của mạng. 
*/ 
{ 
 tree.make_empty(count); 
 bool component[graph_size]; // Các đỉnh trong tập X. 
 Vertex neighbor[graph_size];// Phần tử thứ i chứa đỉnh trước của nó sao cho khoảng 
// cách giữa chúng nhỏ nhất so với các khoảng cách từ 
// các đỉnh trước khác đã có trong tập X đến nó. 
 Weight distance[graph_size];// Các khoảng cách nhỏ nhất tương ứng với từng phần tử 
// trong mảng neighbor trên. 
 Vertex w; 
 for (w = 0; w < count; w++) { 
 component[w] = false; 
 distance[w] = adjacency[source][w]; 
 neighbor[w] = source; 
 } 
 component[source] = true; // Tập X chỉ có duy nhất đỉnh nguồn. 
 for (int i = 1; i < count; i++) { 
 Vertex v; // Mỗi lần lặp bổ sung thêm một đỉnh vào tập X. 
 Weight min = infinity; 
 for (w = 0; w < count; w++) if (!component[w]) 
 if (distance[w] < min) { 
 v = w; 
 min = distance[w]; 
 } 
 if (min < infinity) { 
 component[v] = true; 
 tree.add_edge(v, neighbor[v], distance[v]); 
 for (w = 0; w < count; w++) if (!component[w]) 
 if (adjacency[v][w] < distance[w]) { 
 distance[w] = adjacency[v][w]; 
 neighbor[w] = v; 
 } 
 } 
 else break; // Xong một thành phần liên thông trong đồ thị không liên thông. 
 } 
} 
Vòng lặp chính trong hàm trên thực hiện n-1 lần, với n là số đỉnh, và trong 
vòng lặp chính còn có hai vòng lặp khác, mỗi vòng lặp này thực hiện n-1 lần. Vậy 
các vòng lặp thực hiện (n-1)2 lần. Các lệnh bên ngoài vòng lặp chỉ hết O(n), nên 
thời gian chạy của hàm là O(n2). 
13.6.4. Kiểm tra giải thuật Prim 
Chúng ta cần chứng minh rằng, đối với đồ thị liên thông G, cây phủ S sinh ra 
bởi giải thuật Prim phải có tổng tải trọng trên các cạnh nhỏ hơn so với bất kỳ 
Chương 13 – Đồ thị 
Giáo trình Cấu trúc dữ liệu và Giải thuật 363
một cây phủ nào khác của G. Giải thuật Prim xác định một chuỗi các cạnh s1, s2, 
..., sn tạo ra cây phủ S. Như hình 13.14, s1 là cạnh thứ nhất được thêm vào tập Y 
trong giải thuật Prim, s2 là cạnh thứ hai được thêm vào, và cứ thế. 
Để chứng minh S là một cây phủ tối tiểu, chúng ta chứng minh rằng nếu m là 
một số nguyên, 0 ≤ m ≤ n, thì sẽ có một cây phủ tối tiểu chứa cạnh si với i ≤ m. 
Chúng ta sẽ chứng minh quy nạp trên m. Trường hợp cơ bản, khi m = 0, rõ ràng 
là đúng, vì bất kỳ cây phủ tối tiểu nào cũng đều phải chứa một tập rỗng các cạnh. 
Ngoài ra, khi chúng ta hoàn tất việc quy nạp, trường hợp cuối cùng với m = n chỉ 
ra rằng có một cây phủ tối tiểu chứa tất cả các cạnh của S, và chính là S. (Lưu ý 
rằng nếu thêm bất kỳ một cạnh nào vào một cây phủ thì cũng tạo ra một chu 
trình, nên bất kỳ cây phủ nào chứa mọi cạnh của S đều phải chính là S). Nói cách 
khác, khi chúng ta hoàn tất việc quy nạp, chúng ta đã chứng minh được rằng S 
chính là cây phủ tối tiểu. 
Như vậy chúng ta cần trình bày các bước quy nạp bằng cách chứng minh rằng 
nếu m < n và T là một cây phủ tối tiểu chứa các cạnh s i với i ≤ m, thì phải có một 
cây phủ tối tiểu U cũng chứa các cạnh trên và thêm một cạnh sm+1. Nếu sm+1 đã có 
trong T, chúng ta có thể đơn giản cho U = T, như vậy chúng ta có thể giả sử rằng 
sm+1 không là một cạnh trong T. Chúng ta hãy xem hình (b) của hình 13.14. 
Chúng ta hãy gọi X là tập các đỉnh trong S thuộc các cạnh s1, s2, ..., sm và R là 
tập các đỉnh còn lại trong S. Trong giải thuật Prim, cạnh sm+1 nối một đỉnh trong 
Hình 13.14 – Kiểm tra giải thuật Prim 
Chương 13 – Đồ thị 
Giáo trình Cấu trúc dữ liệu và Giải thuật 364
X với một đỉnh trong R, và sm+1 là một trong các cạnh có tải trọng nhỏ nhất nối 
giữa hai tập này. Chúng ta hãy xét ảnh hưởng của việc thêm cạnh sm+1 này vào T, 
như minh họa trong hình (c). Việc thêm vào này phải tạo ra một chu trình C, do 
mạng liên thông T rõ ràng là có chứa một đường đi có nhiều cạnh nối hai đầu của 
cạnh sm+1. Chu trình C phải có chứa một cạnh t ≠ sm+1 nối tập X với tập R, do nếu 
chúng ta di dọc theo đường đi khép kín C chúng ta phải đi vào tập X một số lần 
bằng với số lần chúng ta đi ra khỏi nó. Chúng ta hãy xem hình (d). Giải thuật 
Prim bảo đảm rằng tải trọng của sm+1 nhỏ hơn hoặc bằng tải trọng của t. Do đó, 
cây phủ mới U trong hình (e), có được từ T bằng cách loại đi t và thêm vào sm+1, 
sẽ có tổng tải trọng không lớn hơn tải trọng của T. Như vậy chúng ta đã có được 
U là một cây phủ tối tiểu của G, mà U chứa các cạnh s1, s2, ..., sm, sm+1. Điều này 
hoàn tất được quá trình quy nạp của chúng ta. 
13.7. Sử dụng đồ thị như là cấu trúc dữ liệu 
Trong chương này, chúng ta đã tìm hiểu chỉ một ít ứng dụng của đồ thị, nhưng 
chúng ta đã bắt đầu thâm nhập vào những vấn đề sâu sắc của các giải thuật về đồ 
thị. Nhiều giải thuật trong số đó, đồ thị xuất hiện như các cấu trúc toán học và đã 
nắm bắt được các đặc trưng thiết yếu của bài toán, thay vì chỉ là những công cụ 
tính toán cho ra được những lời giải của chúng. Lưu ý rằng trong chương này 
chúng ta đã nói về các đồ thị như là các cấu trúc toán học, chứ không như các cấu 
trúc dữ liệu, do chúng ta đã sử dụng chúng để đặc tả các vấn đề trong toán học, 
và để viết các giải thuật, chúng ta đã hiện thực các đồ thị trong các cấu trúc dữ 
liệu như danh sách hoặc bảng. Tuy vậy, rõ ràng là đồ thị tự bản thân nó có thể 
được xem như các cấu trúc dữ liệu - các cấu trúc dữ liệu mà có chứa các mối quan 
hệ giữa các dữ liệu phức tạp hơn những gì đã được mô tả trong một danh sách 
hoặc một cây. Do tính tổng quát và mềm dẻo, đồ thị là cấu trúc dữ liệu rất hiệu 
quả và đã tỏ rõ những giá trị của nó trong những ứng dụng cấp tiến như thiết kế 
hệ quản trị cơ sở dữ liệu chẳng hạn. Tất nhiên, một công cụ mạnh như vậy càng 
nên được sử dụng mọi khi cần thiết, nhưng việc sử dụng nó cần phải được kết hợp 
với việc xem xét một cách cẩn thận để sức mạnh của nó không làm cho cho chúng 
ta bị rối. Cách an toàn nhất trong việc sử dụng một công cụ mạnh là dựa trên sự 
chính quy; nghĩa là, chúng ta chỉ sử dụng công cụ mạnh trong những phương 
pháp đã được định nghĩa một cách cẩn thận và dễ hiểu. Do tính tổng quát của đồ 
thị, việc tuân thủ nguyên tắc vừa nêu ra trong việc sử dụng nó không phải luôn dễ 
dàng.