หากกราฟแบบมีทิศทางถูกกำหนด ให้ตรวจสอบว่าจุดย (vertex j) เข้าถึงได้จากจุด i สำหรับคู่จุดทั้งหมด (i, j) ในกราฟที่กำหนด "เข้าถึงได้" หมายถึงมีเส้นทางจากจุด i ไป j เมทริกซ์ความเข้าถึงได้นี้เรียกว่า Transitive Closure ของกราฟ อัลกอริทึม Warshall มักใช้เพื่อหา Transitive Closure นี่คือโปรแกรม C++ ที่ใช้งานอัลกอริทึมนี้
อัลกอริทึม
Begin
1. รับจำนวนโหนดสูงสุด
2. ติดป้ายกำกับโหนดเป็น a, b, c...
3. ตรวจสอบว่ามีขอบระหว่างโหนดหรือไม่ โดย for loop:
// ASCII code ของ a คือ 97
for i = 97 ถึง (97 + n_nodes) - 1
for j = 97 ถึง (97 + n_nodes) - 1
ถ้ามีขอบ ให้ adj[i - 97][j - 97] = 1
มิฉะนั้น adj[i - 97][j - 97] = 0
4. พิมพ์ transitive closure ของกราฟ:
for i = 0 ถึง n_nodes - 1
c = 97 + i
for i = 0 ถึง n_nodes - 1
c = 97 + i
for j = 0 ถึง n_nodes - 1
พิมพ์ adj[i][j]
End
ตัวอย่างโค้ด
#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 << "\n\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;
}
ผลลัพธ์
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
