Bài này là bài thứ hai trong chuỗi bài mình viết về các thuật toán tìm cây khung nhỏ nhất. Trong bài viết trước, mình giới thiệu bài toán và một số tính chất cơ bản của cây khung nhỏ nhất. Mình sẽ không nhắc lại các tính chất đó ở đây nữa.
Thuật toán Prim, theo Wikipedia, được tìm ra đầu tiên bởi Jarník [2] năm 1930, sau đó được Prim [1] độc lập phát triển năm 1957. Thuật toán Prim xây dựng cây khung dựa trên lát cắt (cut of graphs).
Ví dụ lát cắt tương ứng với $\{a,b,c\}$ của đồ thị trong hình (a) là các cạnh màu đỏ trong hình (b).
Xét một chu trình $C$ của đồ thị và một lát cắt $(A,V\setminus A)$. Nếu $C$ chỉ đi qua các đỉnh trong trong $A$ hoặc chỉ đi qua các đỉnh trong $V\setminus A$, thì $C$ sẽ không chứ cạnh nào của lát cắt, i.e, $|C \cap (A,V\setminus A)| = \emptyset$. Nếu $C$ chứa đỉnh của cả $A$ lần $V\setminus A$ thì ta sẽ thấy $C$ chứa một số chẵn cạnh của lát cắt $(A,V\setminus A)$. Do đó, ta có:
Fact 1 cho chúng ta biết, nếu $|C \cap (A,V\setminus A)| \not= \emptyset$ thì $C$ chứa ít nhất hai cạnh của của lát cắt $(A,V\setminus A)$. Sau đây chúng ta sẽ thảo luận quan hệ giữa cây khung và cắt. Bổ đề dưới đây tương tự như tính chất (5) của cây khung nhỏ nhất mà chúng ta đã thảo luận ở bài trước.
Chứng minh: Thật vậy, gọi $F$ là một cây khung nhỏ nhất nhất không chứa $e$. Ta có $F\cup \{e\}$ sẽ chứa một chu trình $C$. Chu trình này phải chứ $e$. Do đó, $|C \cap (A, V\setminus A)| \not= \emptyset$. Theo Fact 1, $C$ sẽ chứa một cạnh $f$ khác $e$ nằm trong cắt $(A, V\setminus A)$. Thêm nữa, $w(f)\geq w(e)$, do $e$ là cạnh có trọng số nhỏ nhất.
Gọi $T = F\cup \{e\} \setminus \{f\}$. $T$ là một cây khung của đồ thị (tại sao?). Do $w(e) \leq w(f)$, ta suy ra $w(T) \leq w(F)$. Do đó, $T$ cũng phải là một cây khung nhỏ nhất vì $F$ là cây khung nhỏ nhất. Như vậy, $T$ là một cây khung nhỏ nhất chứa $e$.
Lemma 1 cho chúng ta biết cạnh nhỏ nhất của một lát cắt luôn nằm trong một cây khung nhỏ nhất nào đó. Ta sẽ sử dụng tính chất này để xây dựng cây khung.
Gọi $u$ là một đỉnh bất kì thuộc đồ thị và $(\{u\}, V\setminus \{u\})$ là cắt tương ứng với $u$. Cắt này chính là tập các cạnh kề với $u$. Gọi $e$ là cạnh có trọng số nhỏ nhất trong cắt $(\{u\}, V\setminus \{u\})$. Theo Lemma 1, tồn tại cây khung nhỏ nhất chứa cạnh này. Do đó, ta có thể lấy $e$ là cạnh đầu tiên trong cây khung mà ta muốn tìm.
Gọi $v$ là đầu mút khác $u$ của $e$. Cây hiện tại giờ chỉ gồm một cạnh $e$. Xét lát cắt $(\{u,v\}, V\setminus \{u,v\})$ và một cạnh $e'$ là cạnh nhỏ nhất trong lát cắt. Lemma 1 cho chúng ta biết tồn tại cây khung nhỏ nhất chứa $e'$ (và cũng chứa $e$ vì theo chứng minh của Lemma 1, ta chỉ thay đổi cạnh khác trong cùng lát cắt bằng $e'$ để thu được cây khung chứa $e'$). Do đó, ta có thể thêm tiếp $e'$ vào cây khung hiện tại. Gọi $w$ là đầu mút khác $v$ của $e'$ (đương nhiên $w \not= u$), và ta lại có thể tiếp tục thêm cạnh nhỏ nhất của cắt $(\{u,v,w\}, V\setminus \{u,v,w\})$ vào cây hiện tại. Cứ lặp lại như vậy cho đến khi cây hiện tại chứa toàn bộ tập đỉnh của $G$ và cây đó cũng là một cây khung nhỏ nhất.
Ví dụ thực hiện quá trình trên với đồ thị dưới đây. Các cạnh màu đỏ là các cạnh mà ta đã thêm vào cây khung nhỏ nhất. Các cạnh màu xanh gạch ngang là các cạnh của lát cắt mà ta xét để tìm ra cạnh cần thêm vào cây khung.
Thuật toán Prim chính là thuật toán thực hiện quá trình mà chúng ta vừa thảo luận. Giả mã:
pick any vertex $u$
add the smallest edge of the cut $(\{u\},V\setminus \{u\})$ to $T$
while $T \not= V$ $\ll T$ does not contain all vertices$\gg$
$e \leftarrow$ the smallest edge of the cut $(T,V\setminus T)$
$T \leftarrow T \cup \{e\}$
return $T$
Tính đúng đắn của giải thuật Prim có thể được suy ra trực tiếp từ các thảo luận ở trên. Chi tiết cụ thể hơn coi như bài tập cho bạn đọc.
Giờ chúng ta thảo luận cách thực thi thuật toán (đây luôn là phần thú vị nhất). Gọi $n,m$ lần lượt là số đỉnh và số cạnh của đồ thị. Ta thấy thời gian thực thi thuật toán là $O(nF(n,m))$ trong đó $F(n,m)$ là thời gian để thực thi dòng màu đỏ. Thuật toán nhanh hay chậm quyết định bởi dòng này.
Cách thực thi dòng màu đỏ đơn giản nhất đó là duyệt qua tất cả các cạnh của lát cắt và tìm cạnh có trọng số nhỏ nhất. Thời gian của cách thực thi này có thể lên tới $O(m)$, và như vậy, tổng thời gian của thuật toán là $O(nm)$. Với đồ thị dầy ($m = O(n^2)$), cách này cho chúng ta thuật toán $O(n^3)$ (còn xa mới bằng Kruskal).
Thực thi trong thời gian $O(n^2)$
Với cách thực thi này, ta sẽ sử dụng biểu diễn là ma trận kề. Mỗi đỉnh $u$ không thuộc cây hiện tại $T$ ($u \in V\setminus T$), ta sẽ lưu một nhãn $d[u]$. Nhãn $d[u]$ là trọng số của cạnh nhỏ nhất trong số các cạnh từ $u$ tới các đỉnh trong $T$ hiện tại. Ta cũng lưu thêm một nhãn $M[u]$, trong đó $M[u] = v$ nếu $v$ là đỉnh trong $T$ mà $w(u,v) = d[u]$.
Để tìm cạnh nhỏ nhất của lát cắt (thực hiện dòng màu đỏ), ta sẽ duyệt qua tất cả các đỉnh trong $ V\setminus T$, tìm ra đỉnh $u$ có $d[u]$ nhỏ nhất. Khi đó, cạnh $(u,M[u])$ chính là cạnh nhỏ nhất của lát cắt $(T, V\setminus T)$. Do đó, $F(n) \leq n$. Liệu chúng ta đã xong?
Còn một vấn đề nữa, đó là sau khi thêm một cạnh vào trong cây khung hiện tại $T$, ta phải cập nhật lại nhãn cho các đỉnh còn lại. Giả sử cạnh $(u,v)$, với $v = M[u]$, sẽ được thêm vào cây khung. Giả sử trước khi thêm cạnh này, $u \not\in T$. Để cập nhật nhãn, ta duyệt qua các đỉnh còn lại trong $V\setminus T$ và với mỗi đỉnh $x$, ta so sánh trọng số $w(u,x)$ với $d[x]$. Nếu $w(u,x)$ < $d[x]$, ta sẽ cập nhật $d[x] = w(u,x)$ và $M[x] = u$. Nếu không ta sẽ giữ nguyên trọng số. Thao tác cập nhật này có thể thực hiện trong thời gian $O(n)$, do đó, tổng thời gian của thuật toán sẽ là $O(n^2)$.
pick any vertex $u$
$M[1,\ldots, n] \leftarrow \{0,\ldots,0\}$
$d[1, \ldots,n] \leftarrow \{\infty, \ldots, \infty\}$
for each neighbor $x$ of $u$
$M[x] \leftarrow u$
$d[x] \leftarrow w(u,x)$
$T \leftarrow \emptyset$
while $T \not= V$ $\ll T$ does not contain all vertices$\gg$
$u \leftarrow$ FindSmallestVertex$(M[1,\ldots,V])$
for each neighbor $x$ of $u$
if $x \not\in T$ and $w(u,x)$ < $d[x]$
$M[x] \leftarrow u$
$d[x] \leftarrow w(u,x)$
$T \leftarrow T \cup \{(u,M[u])\}$ $\ll $ add edge $(u,M[u])$ to $ T\gg$
return $T$
$min \leftarrow +\infty$
$u \leftarrow 0$
for each $v \in V$
if $d[v]$ < $min$ and $v \not\in T$
$min \leftarrow d[v]$
$u \leftarrow v$
return $u$
Khi code giả mã trên, ta có thể nhận thấy từ mảng $M$, ta có thể xây dựng lại được cây $T$. Với mỗi $x$ mà $M[x] \not= 0$, $(x,M[x])$ chính là cạnh của cây $T$. Ta sẽ dùng thêm một mảng $inT[1,\ldots,n]$ trong đó $inT[u] = $ True nếu $u$ ở trong cây hiện tại và $inT[u] = $ False nếu ngược lại. Code C:
#define INFTY 100000000
#define TRUE 1
#define FALSE 0
// we represent a graph by a weighted matrix
int **W;
int n; // the number of vertices of the graph
int m; // the number of edges of the graph
int *Prim(){
int u = 0;
int *inT = (int *)malloc(n*sizeof(int)); // this array marks whether a vertex is in the currently built tree or not
memset(inT, FALSE, n*sizeof(int));
inT[u] = TRUE;
int *M = (int *)malloc(n*sizeof(int));
memset(M,-1, n*sizeof(int)); // set every elements of M[] to -1;
int *d = (int *)malloc(n*sizeof(int));
int x = 0;
for(; x < n; x++) d[x] = INFTY;// set every elements of d[] to infinity;
for(x = 0; x < n; x++){
if (W[u][x] > 0) {
d[x] = W[u][x];
M[x] = u;
}
}
int j = 0;
while(j < n-1){
u = find_smallest_vertex(d, inT);
for(x = 0; x < n ; x++){
if(W[x][u]> 0 && W[x][u] < d[x] && inT[x] == FALSE){
d[x] = W[u][x];
M[x] = u;
}
}
inT[u] = TRUE;
j++; // the number of vertices currently in the spanning tree
}
return M;
}
int find_smallest_vertex(int *d, int *inT){
int min = INFTY;
int u = -1;
int v = 0;
for(; v < n; v++) {
if (d[v] < min && inT[v] == FALSE){
min = d[v];
u = v;
}
}
return u;
}
Thực thi trong thời gian $O((m+n)\log n)$
Thao tác FindSmallestVertex tìm một đỉnh có nhãn nhỏ nhất trong tập các đỉnh không nằm trong $T$. Thao tác này gợi lại cho chúng ta cấu trúc Heap. Thực sự, chúng ta có thể thực thi thao tác này sử dụng Heap nhị phân với khóa là nhãn $d[1,\ldots,n]$.
pick any vertex $u$
$M[1,\ldots, n] \leftarrow \{0,\ldots,0\}$
$d[1, \ldots,n] \leftarrow \{\infty, \ldots, \infty\}$
for each neighbor $x$ of $u$
$M[x] \leftarrow u$
$d[x] \leftarrow w(u,x)$
initialize heap $H$ with keys $d[1,2,\ldots,n]$
$T \leftarrow \emptyset$
while $T \not= V$ $\ll T$ does not contain all vertices$\gg$
$u \leftarrow$ ExtractMin$(H)$
for each neighbor $x$ of $u$
if $x \not\in T$ and $w(u,x)$ < $d[x]$
$M[x] \leftarrow u$
$d[x] \leftarrow w(u,x)$
DecreaseKey$(H, x, d[x])$
$T \leftarrow T \cup \{(u,M[u])\}$ $\ll $ add edge $(u,M[u])$ to $ T\gg$
return $T$
Hai dòng màu đỏ chính là thay đổi so với thuật toán trước.
Khi thực thi giả mã này, ta sẽ dùng cấu trúc dữ liệu danh sách kề để biểu diễn đồ thị. Với mỗi đỉnh, ta sử dụng một danh sách liên kết lưu các đỉnh kề với nó. Code C:
#define INFTY 100000000
#define TRUE 1
#define FALSE 0
// we use linked lists to represent adjacency lists
// each arc u->v with weight w(u->v) is represented by a node with data field v and weight w in the adacency list of u
typedef struct vlist{
int v; // the head of the directed edge
int w; // the original weight of the directed edge
int Delta; // the modified weight using potential
struct vlist *next;
}vlist;
vlist **G; // G[i] is the adjacency list of vertex i
int n; // the number of vertices of the graph
int m; // the number of edges of the graph
int *d; // the distance array
int *Prim(){
int u = 0;
int *inT = (int *)malloc(n*sizeof(int)); // this array marks whether a vertex is in the currently built tree or not
memset(inT, FALSE, n*sizeof(int));
inT[u] = TRUE;
int *M = (int *)malloc(n*sizeof(int));
memset(M,-1, n*sizeof(int)); // set every elements of M[] to -1;
d = (int *)malloc(n*sizeof(int));
int x = 0;
for(; x < n; x++) d[x] = INFTY;// set every elements of d[] to infinity;
vlist *runner;
runner = G[u];
while(runner != NULL){ // iterate through neighbors of u
x = runner->v;
d[x] = runner->w;
M[x] = u;
runner = runner->next;
}
build_heap(n, u);
int j = 0;
while(j < n-1){
u = extract_min();
runner = G[u];
while(runner != NULL){ // iterate through neighbors of u
x = runner->v;
if(runner->w < d[x] && inT[x] == FALSE){
d[x]= runner->w;
M[x] = u;
decrease_key(x,d[x]);
}
runner = runner->next;
}
inT[u] = TRUE;
j++; // the number of vertices currently in the spanning tree
}
return M;
}
Phân tích thuật toán: Thao tác ExtractMin$(H)$ mất thời gian $O(\log n)$ và thao tác DecreaseKey$(H, x, d[x])$ mất thời gian $O(\log n)$ nếu ta sử dụng Heap nhị phân và mất $O(1)$ nếu ta sử dụng Fibonacci Heap. Do đó, mỗi vòng lặp sẽ mất $O(\deg(u)\log(n) + \log n)$ nếu sử dụng Heap nhị phân mất $O(\deg(u)+ \log n)$ nếu sử dụng Fibonacci Heap. Do đó, tổng thời gian của thuật toán là:
$\sum_{u \in V} O(\deg(u)\log(n) + \log n) = O((m+n)\log n) \qquad (1)$
nếu sử dụng Heap nhị phân, và tổng thời gian của thuật toán là:
$\sum_{u \in V} O(\deg(u) + \log n) = O(m + n\log n) \qquad (2)$
nếu sử dụng Fibonacci Heap.
Final Remark Với đồ thị dầy, ta nên sử dụng thuật toán $O(n^2)$ của Prim, vì thực thi đơn giản mà thời gian chạy lại tối ưu. Với đồ thị thưa, ta có hai lựa chọn: hoặc sử dụng thuật toán Prim, hoặc sử dụng thuật toán Kruskal. Trong thực tế, có lẽ không nên chọn Fibonacci Heap để thực thi Prim vì mặc dù thời gian tiệm cận nhỏ hơn, hằng số ẩn sau $O$ khá lớn và Fibonacci Heap cũng rất khó thực thi. Sử dụng Heap nhị phân, ta sẽ thu được thuật toán với thời gian giống Kruskal. Tuy nhiên, hằng số ẩn sau Big O của Kruskal nhỏ hơn của Prim nhiều do nhân tử $\log n$ trong độ phức tạp là do bước sắp xếp. Do đó, ta nên chọn thực thi Kruskal với đồ thị thưa.
Code đầy đủ: Prim, Prim-and-Heap.
Tham khảo
[1] Prim, Robert Clay. Shortest Connection Networks and some Generalizations. Bell System Technical Journal 36.6 (1957): 1389-1401
[2]Jarník, V. O jistém problému minimálním" [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti (in Czech) 6: 57–63, 1930.
[3] Uri Zwick. Notes on Minimum Spanning Tree. Tel Aviv University, 2013.
Recent Comments