গ্রাফের ট্রানজিটিভ ক্লোজার (Transitive Closure of a Graph)

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

ফাইনাল ম্যাট্রিক্স বুলিয়ান টাইপের। যখন u থেকে v-এ যেতে ১ থাকে, তার মানে u থেকে v-এ কমপক্ষে একটি পথ আছে।

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

ইনপুট:
1 1 0 1
0 1 1 0
0 0 1 1
0 0 0 1
আউটপুট: ট্রানজিটিভ ক্লোজার ম্যাট্রিক্স
1 1 1 1
0 1 1 1
0 0 1 1
0 0 0 1

এলগরিদম

transColsure(graph)

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

শুরু
  অ্যাডজেসেন্সি ম্যাট্রিক্সকে অন্য একটি ম্যাট্রিক্স transMat-এ কপি করুন
  গ্রাফের যেকোনো ভার্টেক্স k এর জন্য, করুন
    গ্রাফের প্রতিটি ভার্টেক্স i এর জন্য, করুন
      গ্রাফের প্রতিটি ভার্টেক্স j এর জন্য, করুন
        transMat[i, j] := transMat[i, j] OR ((transMat[i, k]) AND transMat[k, j])
      শেষ লুপ
    শেষ লুপ
  শেষ লুপ
  transMat প্রদর্শন করুন
শেষ

উদাহরণ (C++ কোড)

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

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];  // প্রাথমিকভাবে গ্রাফকে রেজাল্ট ম্যাট্রিক্সে কপি করুন
  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++) {
    // রেজাল্ট ম্যাট্রিক্স প্রিন্ট করুন
    for(int j = 0; j < NODE; j++)
      cout << result[i][j] << " ";
    cout << endl;
  }
}

int main() {
  transClosure();
}

আউটপুট