Cấu trúc dữ liệu

 giá không âm thì ta luôn luôn tìm được một đường đi ngắn nhất như vậy mà chỉ đi qua 
các đỉnh đã tồn tại trong S. Để chi tiết hoá giải thuật, giả sử G có n đỉnh và nhãn trên mỗi 
cung được lưu trong mảng hai chiều C, tức là C[i,j] là giá (có thể xem như độ dài) của cung 
(i,j), nếu i và j không nối nhau thì C[i,j]=∞. Ta dùng mảng 1 chiều D có n phần tử để lưu độ 
dài của đường đi ngắn nhất từ mỗi đỉnh của đồ thị đến v. Khởi đầu khoảng cách này chính 
là độ dài cạnh (v,i), tức là D[i]=C[v,i]. Tại mỗi bước của giải thuật thì D[i] sẽ được cập 
nhật lại để lưu độ dài đường đi ngắn nhất từ đỉnh v tới đỉnh i, đường đi này chỉ đi qua các 
đỉnh đã có trong S. 
Để cài đặt giải thuật dễ dàng, ta giả sử các đỉnh của đồ thị được đánh số từ 1 đến n, tức là 
V={1,..,n} và đỉnh nguồn là 1. Dưới dây là giải thuật Dijkstra để giải bài toán trên. 
void Dijkstra() 
{ 
 Trang 143
Cấu trúc dữ liệu Chương V: Đồ thị 
 S = [1]; //Tập hợp S chỉ chứa một đỉnh nguồn 
 for (i =2; i<=n; i++) 
 D[i-1] = C[0,i-1]; //khởi đầu các giá trị cho D 
 for (i=1; i<n; i++) 
 { 
 Lấy đỉnh w trong V-S sao cho D[w-1] nhỏ nhất; 
 Thêm w vào S; 
 for (mỗi đỉnh u thuộc V-S) 
 D[u-1] = min(D[u-1], D[w-1] + C[w-1,u-1]); 
 } 
} 
Nếu muốn lưu trữ lại các đỉnh trên đường đi ngắn nhất để có thể xây dựng lại đường đi 
này từ đỉnh nguồn đến các đỉnh khác, ta dùng một mảng P. Mảng này sẽ lưu P[u]=w với u 
là đỉnh "trước" đỉnh w trong đường đi. Lúc khởi đầu P[u]=1 với mọi u. 
Giải thuật Dijkstra được viết lại như sau: 
void Dijkstra() 
{
 S =[1]; //S chỉ chứa một đỉnh nguồn 
 for(i=2; i<=n; i++) 
 { 
 P[i-1] =1; //khởi tạo giá trị cho P 
 D[i-1] =C[0,i-1]; //khởi đầu các giá trị cho D 
 } 
 for (i=1; i<n; i++) 
 { 
 Lấy đỉnh w trong V-S sao cho D[w-1] nhỏ nhất; 
 Thêm w vào S; 
 for (mỗi đỉnh u thuộc V-S) 
 if (D[w-1] + C[w-1,u-1] < D[u-1]) 
 Trang 144
Cấu trúc dữ liệu Chương V: Đồ thị 
 { 
 D[u-1] =D[w-1] + C[w-1,u-1]; 
 P[u-1] =w; 
 } 
 } 
} 
Ví dụ: áp dụng giải thuật Dijkstra cho đồ thị hình V.5 
Kết quả khi áp dụng giải thuật 
Lần lặp S W D[2] D[3] D[4] D[5]
Khởi đầu {1} - 10 ∞ 30 100
1 {1,2} 2 10 60 30 100
2 {1,2,4} 4 10 40 30 90 
3 {1,2,3,4} 3 10 40 30 50 
4 {1,2,3,4,5} 5 10 40 30 50 
Mảng P có giá trị như sau: 
P 1 2 3 4 5 
 1 4 1 3 
Từ kết quả trên ta có thể suy ra rằng đường đi ngắn nhất từ đỉnh 1 đến đỉnh 3 là 
1 → 4 → 3 có độ dài là 40. đường đi ngắn nhất từ 1 đến 5 là 1 → 4 → 3→ 5 có độ dài 
50. 
2. Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh 
Giả sử đồ thị G có n đỉnh được đánh số từ 1 đến n. Khoảng cách hay giá giữa các cặp đỉnh 
được cho trong mảng C[i,j]. Nếu hai đỉnh i,j không được nối thì C[i,j]= ¥. Giải thuật Floyd 
xác định đường đi ngắn nhất giữa hai cặp đỉnh bất kỳ bằng cách lặp k lần, ở lần lặp thứ k sẽ 
 Trang 145
Cấu trúc dữ liệu Chương V: Đồ thị 
xác định khoảng cách ngắn nhất giữa hai đỉnh i,j theo công thức: Ak[i,j]=min(Ak-1[i,j], Ak-
1[i,k]+Ak-1[k,j]). Ta cũng dùng mảng P để lưu các đỉnh trên đường đi. 
float A[n,n], C[n,n]; 
int P[n,n]; 
void Floyd() 
{ 
int i,j,k; 
 for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
 { 
 A[i-1,j-1] = C[i-1,j-1]; 
 P[i-1,j-1]=0; 
} 
 for (i=1; i<=n; i++) 
 A[i-1,i-1]=0; 
 for (k=1; k<=n; k++) 
 for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
 if (A[i-1,k-1] + A[k-1,j-1] < A[i-1,j-1) 
{
 A[i-1,j-1] = A[i-1,k-1] + A[k-1,j-1]; 
 P[i-1,j-1] = k; 
 } 
}
3. Bài toán tìm bao đóng chuyển tiếp (transitive closure) 
Trong một số trường hợp ta chỉ cần xác định có hay không có đường đi nối giữa hai đỉnh i,j 
bất kỳ. Giải thuật Floyd có thể đặc biệt hoá để giải bài toán này. Bây giờ khoảng cách giữa 
 Trang 146
Cấu trúc dữ liệu Chương V: Đồ thị 
i,j là không quan trọng mà ta chỉ cần biết i,j có nối nhau không do đó ta cho C[i,j]=1 (~true) 
nếu i,j được nối nhau bởi một cạnh, ngược lại C[i,j]=0 (~false). Lúc này mảng A[i,j] không 
cho khoảng cách ngắn nhất giữa i,j mà nó cho biết là có đường đi từ i đến j hay không. A 
gọi là bao đóng chuyển tiếp của đồ thị G có biểu diễn ma trận kề là C. Giải thuật Floyd sửa 
đổi như trên gọi là giải thuật Warshall. 
int A[n,n], C[n,n]; 
void Warshall() 
{ 
int i,j,k; 
 for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
 A[i-1,j-1] = C[i-1,j-1]; 
 for (k=1; k<=n; k++) 
 for (i=1; i<=n; i++) 
 for (j=1; j<=n; j++) 
if (A[i-1,j-1] == 0) then 
A[i-1,j-1] =A[i-1,k-1] && A[k-1,j-1]; 
} 
4. Bài toán tìm cây bao trùm tối thiểu (minimum-cost spanning tree) 
Giả sử ta có một đồ thị vô hướng G=(V,E). Đồ thị G gọi là liên thông nếu tồn tại đường 
đi giữa hai đỉnh bất kỳ. Bài toán tìm cây bao trùm tối thiểu (hoặc cây phủ tối thiểu) là tìm 
một tập hợp T chứa các cạnh của một đồ thị liên thông G sao cho V cùng với tập các cạnh 
này cũng là một đồ thị liên thông, tức là (V,T) là một đồ thị liên thông. Hơn nữa tổng độ dài 
các cạnh trong T là nhỏ nhất. Một thể hiện của bài toán này trong thực tế là bài toán thiết 
lập mạng truyền thông, ở đó các đỉnh là các thành phố còn các cạnh của cây bao trùm là 
đường nối mạng giữa các thành phố. 
Giả sử G có n đỉnh được đánh số 1..n. Giải thuật Prim để giải bài toán này như sau: 
Bắt đầu, tập ta khởi tạo tập U bằng 1 đỉnh nào đó, đỉnh 1 chẳng hạn, U = {1}, T=U 
Sau đó ta lặp lại cho đến khi U=V, tại mỗi bước lặp ta chọn cạnh nhỏ nhất (u,v) sao cho 
u ∈ U và v ∈ V-U. Thêm v vào U và (u,v) vào T. Khi giải thuật kết thúc thì (U,T) là một 
cây phủ tối tiểu. 
 Trang 147
Cấu trúc dữ liệu Chương V: Đồ thị 
Ví dụ, áp dụng giải thuật Prim để tìm cây bao trùm tối thiểu của đồ thị liên thông hình 
V.6. 
¾ Bước khởi đầu: U={1}, T=∅. 
¾ Bước kế tiếp ta có cạnh (1,3)=1 là cạnh ngắn nhất thoả mãn điều kiện trong giải 
thuật Prim nên: U={1,3}, T={(1,3)}. 
¾ Kế tiếp thì cạnh (3,6)=4 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6}, T={(1,3),(3,6)}. 
¾ Kế tiếp thì cạnh (6,4)=2 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6,4}, T={(1,3),(3,6),(6,4)}. 
¾ Tiếp tục, cạnh (3,2)=5 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6,4,2}, T={(1,3),(3,6),(6,4),(3,2)}. 
¾ Cuối cùng, cạnh (2,5)=3 là cạnh ngắn nhất thoả mãn điều kiện trong giải thuật Prim 
nên: U={1,3,6,4,2,5}, T={(1,3),(3,6),(6,4),(3,2),(2,5)}. Giải thuật dừng và ta có cây 
bao trùm như trong hình V.7. 
Giải thuật Prim được viết lại như sau: 
void Prim(graph G, set_of_edges *T) 
{ 
 set_of_vertices U; //tập hợp các đỉnh 
 vertex u,v; //u,v là các đỉnh 
 T = ∅; 
 U = [1]; 
 Trang 148
Cấu trúc dữ liệu Chương V: Đồ thị 
 while (U≠V) do // V là tập hợp các đỉnh của G 
 { 
gọi (u,v) là cạnh ngắn nhất sao cho u ∈ U và v ∈ V-U; 
 U = U ∪ [v]; 
 T = T ∪ [(u,v)]; 
 } 
} 
Bài toán cây bao trùm tối thiểu còn có thể được giải bằng giải thuật Kruskal như sau: 
Khởi đầu ta cũng cho T= ∅ giống như trên, ta thiết lập đồ thị khởi đầu G'=(V,T). 
Xét các cạnh của G theo thứ tự độ dài tăng dần. Với mỗi cạnh được xét ta sẽ đưa nó vào T 
nếu nó không làm cho G' có chu trình. 
Ví dụ áp dụng giải thuật Kruskal để tìm cây bao trùm cho đồ thị hình V.6. 
Các cạnh của đồ thị được xếp theo thứ tự tăng dần là. 
(1,3)=1, (4,6)=2, (2,5)=3, (3,6)=4, (1,4)=(2,3)=(3,4)=5, (1,2)=(3,5)= (5,6)=6. 
Ò Bước khởi đầu T= ∅ 
Ò Lần lặp 1: T={(1,3)} 
Ò Lần lặp 2: T={(1,3),(4,6)} 
Ò Lần lặp 3: T={(1,3),(4,6),(2,5)} 
Ò Lần lặp 4: T={(1,3),(4,6),(2,5),(3,6)} 
Ò Lần lặp 5: 
 Cạnh (1,4) không được đưa vào T vì nó sẽ tạo ra chu trình 1,3,6,4,1. 
 Kế tiếp cạnh (2,3) được xét và được đưa vào T. 
T={(1,3),(4,6),(2,5),(3,6),(2,3)} 
Không còn cạnh nào có thể được đưa thêm vào T mà không tạo ra chu trình. Vậy ta có cây 
bao trùm tối thiểu cũng giống như trong hình V.7. 
 Trang 149
Cấu trúc dữ liệu Chương V: Đồ thị 
BÀI TẬP 
1. Viết biểu diễn đồ thị V.8 bằng: 
- Ma trận kề. 
- Danh sách các đỉnh kề. 
2. Duyệt đồ thị hình V.8 (xét các đỉnh theo thứ tự a,b,c...) 
 - Theo chiều rộng bắt đầu từ a. 
 - Theo chiều sâu bắt đầu từ f 
3. Áp dụng giải thuật Dijkstra cho đồ thị hình V.8, với đỉnh nguồn là 
a. 
4. Viết biểu diễn đồ thị V.9 bằng: 
 Ma trận kề. 
 Danh sách các đỉnh kề. 
5. Duyệt đồ thị hình V.9 (xét các đỉnh theo thứ tự A,B,C...) 
 Theo chiều rộng bắt đầu từ A. 
 Theo chiều sâu bắt đầu từ B. 
6. Áp dụng giải thuật Dijkstra cho đồ thị hình V.9, với đỉnh nguồn là A. 
7. Tìm cây bao trùm tối thiểu của đồ thị hình V.9 bằng 
 Giải thuật Prim. 
 Giải thuật Kruskal. 
8. Cài đặt đồ thị có hướng bằng ma trận kề rồi viết các giải thuật: 
 Duyệt theo chiều rộng. 
 Duyệt theo chiều sâu. 
 Tìm đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra). 
 Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd). 
9. Cài đặt đồ thị có hướng bằng danh sách các đỉnh kề rồi viết các giải thuật: 
 Duyệt theo chiều rộng. 
 Trang 150
Cấu trúc dữ liệu Chương V: Đồ thị 
 Duyệt theo chiều sâu. 
10. Cài đặt đồ thị vô hướng bằng ma trận kề rồi viết các giải thuật: 
 Duyệt theo chiều rộng. 
 Duyệt theo chiều sâu. 
 Tìm đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra). 
 Tìm đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd). 
 Tìm cây bao trùm tối thiểu (Prim, Kruskal). 
 Cài đặt thuật toán Greedy cho bài toán tô màu đồ thị (Gợi ý: xem giải thuật trong 
chương 1) 
11. Cài đặt đồ thị vô hướng bằng danh sách các đỉnh kề rồi viết các giải thuật: 
 Duyệt theo chiều rộng. 
 Duyệt theo chiều sâu. 
12. Hãy viết một chương trình, trong đó, cài đặt đồ thị vô hướng bằng cấu trúc ma trận 
kề rồi viết các thủ tục/hàm sau: 
Nhập toạ độ n đỉnh của đồ thị. 
Giả sử đồ thị là đầy đủ, tức là hai đỉnh bất kỳ đều có cạnh nối, và giả sử giá của mỗi cạnh 
là độ dài của đoạn thẳng nối hai cạnh. Hãy tìm: 
Đường đi ngắn nhất từ một đỉnh cho trước (Dijkstra). 
Đường đi ngắn nhất giữa tất cả các cặp đỉnh (Floyd). 
Cây bao trùm tối thiểu (Prim, Kruskal). 
Thể hiện đồ thị lên màn hình đồ hoạ, các cạnh thuộc cây bao trùm tối thiểu được vẽ bằng 
một màu khác với các cạnh khác. 
 Trang 151