যদি একটি ডিরেক্টেড গ্রাফ দেওয়া থাকে, তবে দেওয়া গ্রাফের সব ভের্টেক্স জোড়া (i, j) এর জন্য ভের্টেক্স i থেকে ভের্টেক্স j erreich্য (reachable) কিনা তা নির্ধারণ করুন। পৌঁছানোর অর্থ হল ভের্টেক্স i থেকে j-এ একটি পথ আছে। এই পৌঁছানোর ম্যাট্রিক্সকে গ্রাফের ট্রানজিটিভ ক্লোজার (Transitive Closure) বলা হয়। ওয়ার্শাল অ্যালগরিদম (Warshall algorithm) সাধারণত একটি দেওয়া গ্রাফ G-এর ট্রানজিটিভ ক্লোজার বের করতে ব্যবহৃত হয়। এখানে এই অ্যালগরিদম বাস্তবায়ন করার একটি সি++ প্রোগ্রাম দেওয়া হলো।
অ্যালগরিদম
শুরু ১. নোডের সর্বোচ্চ সংখ্যা ইনপুট নিন। ২. নোডগুলাকে a, b, c... হিসেবে লেবেল করুন। ৩. নোডগুলোর মধ্যে কোনো এজ আছে কিনা চেক করতে একটি ফর লুপ তৈরি করুন: // a-এর ASCII কোড ৯৭ for i = 97 to (97 + n_nodes)-1 for j = 97 to (97 + n_nodes)-1 যদি এজ থাকে, adj[i - 97][j - 97] = 1 অন্যথায় adj[i - 97][j - 97] = 0 লুপ শেষ লুপ শেষ। ৪. গ্রাফের ট্রানজিটিভ ক্লোজার প্রিন্ট করতে: for i = 0 to n_nodes-1 c = 97 + i লুপ শেষ। for i = 0 to n_nodes-1 c = 97 + i for j = 0 to n_nodes-1 Print 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; }
আউটপুট
গ্রাফে সর্বোচ্চ নোড সংখ্যা :4 'y' FOR 'YES' এবং 'n' FOR 'NO' ইনপুট দিন a থেকে a-তে এজ আছে? y a থেকে b-তে এজ আছে? y a থেকে c-তে এজ আছে? n a থেকে d-তে এজ আছে? n b থেকে a-তে এজ আছে? y b থেকে b-তে এজ আছে? n b থেকে c-তে এজ আছে? y b থেকে d-তে এজ আছে? n c থেকে a-তে এজ আছে? y c থেকে b-তে এজ আছে? n c থেকে c-তে এজ আছে? n c থেকে d-তে এজ আছে? n d থেকে a-তে এজ আছে? y d থেকে b-তে এজ আছে? n d থেকে c-তে এজ আছে? y d থেকে d-তে এজ আছে? n গ্রাফের ট্রানজিটিভ ক্লোজার: a b c d a 1 1 0 0 b 1 0 1 0 c 1 0 0 0 d 1 0 1 0
