একটি গ্রাফের ট্রানজিটিভ ক্লোজার

ট্রানজিটিভ ক্লোজ করুন এটি একটি গ্রাফের শীর্ষবিন্দু থেকে শীর্ষবিন্দু v পর্যন্ত পৌঁছানোর জন্য পৌঁছানোর ম্যাট্রিক্স। একটি গ্রাফ দেওয়া হয়েছে, আমাদের একটি শীর্ষবিন্দু v খুঁজে বের করতে হবে যা অন্য শীর্ষবিন্দু থেকে পৌঁছানো যায়, সমস্ত শীর্ষ জোড়ার জন্য (u, v)।

চূড়ান্ত ম্যাট্রিক্স হল বুলিয়ান টাইপ। ভার্টেক্স u থেকে ভার্টেক্স v এর জন্য যখন একটি মান 1 থাকে, তখন এর মানে হল u থেকে v পর্যন্ত অন্তত একটি পথ আছে।

ইনপুট এবং আউটপুট

Input:
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1

Output:
The matrix of transitive closure
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

অ্যালগরিদম

transColsure(graph)

ইনপুট: প্রদত্ত গ্রাফ।
আউটপুট: ট্রানজিটিভ ক্লোজার ম্যাট্রিক্স।

Begin
   copy the adjacency matrix into another matrix named transMat
   for any vertex k in the graph, do
      for each vertex i in the graph, do
         for each vertex j in the graph, do
            transMat[i, j] := transMat[i, j] OR (transMat[i, k]) AND transMat[k, j])
         done
      done
   done
   Display the transMat
End

<2>উদাহরণ

#include<iostream>
#include<vector>
#define NODE 4
using namespace std;

/* int graph[NODE][NODE] = {
   {0, 1, 1, 0},
   {0, 0, 1, 0},
   {1, 0, 0, 1},
   {0, 0, 0, 0}
}; */

int graph[NODE][NODE] = {
   {1, 1, 0, 1},
   {0, 1, 1, 0},
   {0, 0, 1, 1},
   {0, 0, 0, 1}
};

int result[NODE][NODE];

void transClosure() {
   for(int i = 0; i<NODE; i++)
      for(int j = 0; j<NODE; j++)
         result[i][j] = graph[i][j];    //initially copy the graph to the result matrix
   for(int k = 0; k<NODE; k++)
      for(int i = 0; i<NODE; i++)
         for(int j = 0; j<NODE; j++)
            result[i][j] = result[i][j] || (result[i][k] && result[k][j]);
   for(int i = 0; i<NODE; i++) {          //print the result matrix
      for(int j = 0; j<NODE; j++)
         cout << result[i][j] << " ";
      cout << endl;
   }
}

int main() {
   transClosure();
}

আউটপুট

1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1