ওয়ারশালের অ্যালগরিদম ব্যবহার করে ট্রানজিটিভ ক্লোজার নির্মাণের জন্য C++ প্রোগ্রাম

যদি একটি নির্দেশিত গ্রাফ দেওয়া হয়, প্রদত্ত গ্রাফের সমস্ত শীর্ষ জোড়ার (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:
      for i = 97 to less than 97 + number of nodes
         for j = 97 to less than 97 + number of nodes
            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 number of nodes
         c = 97 + i
      end loop.
      for i = 0 to number of nodes
         c = 97 + i;
      for j = 0 to n_nodes
         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 << "\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