Cho đồ thị có hướng, xác định xem đỉnh j có đạt được từ đỉnh i không với mọi cặp (i, j). Ma trận đạt được này gọi là bao truyền dịch (transitive closure). Thuật toán Warshall thường được dùng. Chương trình C++ dưới đây cài đặt 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 a, b, c...
3. Kiểm tra cạnh giữa các nút bằng vòng lặp:
for i = 97 to (97 + n_nodes)-1
for j = 97 to (97 + n_nodes)-1
Nếu có cạnh: adj[i-97][j-97] = 1 else 0
4. In bao truyền dịch:
for i = 0 to n_nodes-1: c = 97+i
for i, j: in adj[i][j]
Kết thúc
Ví dụ
#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\tMaximum number of nodes in the graph :";
cin >> n;
n_nodes = n;
cout << "\nEnter 'y'for 'YES' and 'n' for 'NO' \n";
for (i = 97; i < 97 + n_nodes; i++)
for (j = 97; j < 97 + n_nodes; j++) {
cout << "\n\tIs there an edge from " << i << " to " << j << " ? ";
cin >> res;
if (res == 'y')
adj[i - 97][j - 97] = 1;
else
adj[i - 97][j - 97] = 0;
}
cout << "\nTransitive Closure of the Graph:\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ả
Maximum number of nodes in the graph :4 Enter 'y'for 'YES' and 'n' for 'NO' Is there an edge from a to a ? y Is there an edge from a to b ? y Is there an edge from a to c ? n Is there an edge from a to d ? n Is there an edge from b to a ? y Is there an edge from b to b ? n Is there an edge from b to c ? y Is there an edge from b to d ? n Is there an edge from c to a ? y Is there an edge from c to b ? n Is there an edge from c to c ? n Is there an edge from c to d ? n Is there an edge from d to a ? y Is there an edge from d to b ? n Is there an edge from d to c ? y Is there an edge from d to d ? n Transitive Closure of the Graph: a b c d a 1 1 0 0 b 1 0 1 0 c 1 0 0 0 d 1 0 1 0