যদি একটি নির্দেশিত গ্রাফ দেওয়া হয়, প্রদত্ত গ্রাফের সমস্ত শীর্ষ জোড়ার (i, j) জন্য একটি শীর্ষবিন্দু j অন্য শীর্ষ i থেকে পৌঁছানো যায় কিনা তা নির্ধারণ করুন। পৌঁছানো যায় মানে যে শীর্ষবিন্দু i থেকে j পর্যন্ত একটি পথ আছে। এই পৌঁছানোর ম্যাট্রিক্সকে গ্রাফের ট্রানজিটিভ ক্লোজার বলা হয়। Warshall অ্যালগরিদম সাধারণত একটি প্রদত্ত গ্রাফ G-এর ট্রানজিটিভ ক্লোজার খুঁজে পেতে ব্যবহৃত হয়। এই অ্যালগরিদমটি বাস্তবায়নের জন্য এখানে একটি C++ প্রোগ্রাম রয়েছে।
অ্যালগরিদম
Begin 1. Take maximum number of nodes as input. 2. For Label the nodes as a, b, c….. 3. To check if there any edge present between the nodes make a for loop: // ASCII code of a is 97 for i = 97 to (97 + n_nodes)-1 for j = 97 to (97 + n_nodes)-1 If edge is present do, adj[i - 97][j - 97] = 1 else adj[i - 97][j - 97] = 0 End loop End loop. 4. To print the transitive closure of graph: for i = 0 to n_nodes-1 c = 97 + i End loop. for i = 0 to n_nodes-1 c = 97 + i for j = 0 to n_nodes-1 Print adj[I][j] End loop End loop 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
