Cho một đồ thị có hướng, xác định xem đỉnh j có thể đạt được từ đỉnh i cho mọi cặp đỉnh (i, j) trong đồ thị. "Đạt được" nghĩa là tồn tại đường đi từ i đến j. Ma trận đạt được này gọi là bao bao tranzitif (transitive closure) của đồ thị. Thuật toán Warshall thường dùng để tìm bao bao tranzitif của đồ thị G. Dưới đây là chương trình C++ triển khai thuật toán này.
Thuật toán
Bắt đầu
1. Nhập số nút tối đa.
2. Gán nhãn nút là a, b, c...
3. Kiểm tra cạnh giữa các nút bằng vòng lặp:
// Mã ASCII của 'a' là 97
với i = 97 đến (97 + n_nodes) - 1
với j = 97 đến (97 + n_nodes) - 1
Nếu có cạnh thì adj[i-97][j-97] = 1
ngược lại adj[i-97][j-97] = 0
Kết thúc vòng lặp
4. In bao bao tranzitif của đồ thị:
với i = 0 đến n_nodes-1
c = 97 + i
Kết thúc vòng lặp
với i = 0 đến n_nodes-1
c = 97 + i
với j = 0 đến n_nodes-1
In adj[i][j]
Kết thúc vòng lặp
Kết thúc vòng lặp
Kết thúc
Ví dụ mã nguồn
#include <iostream>
using namespace std;
const int n_nodes = 20;
int main() {
int n_nodes, k, n;
char i, j, res, c;
int adj[10][10], path[10][10];
cout << "\n\tSố nút tối đa trong đồ thị: ";
cin >> n;
n_nodes = n;
cout << "\nNhập 'y' cho 'CÓ' và 'n' cho 'KHÔNG' \n";
for (i = 97; i < 97 + n_nodes; i++)
for (j = 97; j < 97 + n_nodes; j++) {
cout << "\n\tCó cạnh từ " << i << " đến " << j << " ? ";
cin >> res;
if (res == 'y')
adj[i - 97][j - 97] = 1;
else
adj[i - 97][j - 97] = 0;
}
cout << "\n\nBao bao tranzitif của đồ thị:\n";
cout << "\n\t\t\t ";
for (i = 0; i < n_nodes; i++) {
c = 97 + i;
cout << c << " ";
}
cout << "\n\n";
for (int i = 0; i < n_nodes; i++) {
c = 97 + i;
cout << "\t\t\t" << c << " ";
for (int j = 0; j < n_nodes; j++)
cout << adj[i][j] << " ";
cout << "\n";
}
return 0;
}
Kết quả
Số nút tối đa trong đồ thị: 4
Nhập 'y' cho 'CÓ' và 'n' cho 'KHÔNG'
Có cạnh từ a đến a ? y
Có cạnh từ a đến b ? y
Có cạnh từ a đến c ? n
Có cạnh từ a đến d ? n
Có cạnh từ b đến a ? y
Có cạnh từ b đến b ? n
Có cạnh từ b đến c ? y
Có cạnh từ b đến d ? n
Có cạnh từ c đến a ? y
Có cạnh từ c đến b ? n
Có cạnh từ c đến c ? n
Có cạnh từ c đến d ? n
Có cạnh từ d đến a ? y
Có cạnh từ d đến b ? n
Có cạnh từ d đến c ? y
Có cạnh từ d đến d ? n
Bao bao tranzitif của đồ thị:
a b c d
a 1 1 0 0
b 1 0 1 0
c 1 0 0 0
d 1 0 1 0