যদি একটি ডাইরেক্টেড গ্রাফ দেওয়া থাকে, সব ভের্টেক্স পেয়ার (i, j) এর জন্য ভের্টেক্স j কি ভের্টেক্স i থেকে রিচেবল তা নির্ধারণ করো। রিচেবল মানে ভের্টেক্স i থেকে j-এ পথ রয়েছে। এই রিচেবিলিটি ম্যাট্রিক্সকে গ্রাফের ট্রানজিটিভ ক্লোজার বলা হয়। ওয়ার্শাল অ্যালগরিদম সাধারণত একটি দিয়ে गये গ্রাফ G-এর ট্রানজিটিভ ক্লোজার খুঁজে বের করতে ব্যবহৃত হয়। এখানে এই অ্যালগরিদম ইমপ্লিমেন্ট করার একটি C++ প্রোগ্রাম দেওয়া হলো।
অ্যালগরিদম
শুরু
1. সর্বোচ্চ নোড সংখ্যা ইনপুট নাও।
2. নোডগুলাকে a, b, c... হিসেবে লেবেল করো।
3. নোডগুলোর মধ্যে এজ আছে কিনা চেক করার জন্য ফর লুপ:
for i = 97 to less than 97 + number of nodes
for j = 97 to less than 97 + number of nodes
যদি এজ থাকে তবে,
adj[i - 97][j - 97] = 1
অন্যথায়
adj[i - 97][j - 97] = 0
লুপ শেষ
লুপ শেষ
4. গ্রাফের ট্রানজিটিভ ক্লোজার প্রিন্ট করতে:
for i = 0 to number of nodes
c = 97 + i
লুপ শেষ
for i = 0 to number of nodes
c = 97 + i;
for j = 0 to n_nodes
adj[i][j] প্রিন্ট করো
লুপ শেষ
লুপ শেষ
শেষউদাহরণ কোড
#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;
}আউটপুট
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
