C++ প্রোগ্রাম: গ্রাফের ট্রানজিটিভ ক্লোজার (Warshall's Algorithm)

ট্রানজিটিভ ক্লোজার কী?

একটি ডায়রেক্টেড গ্রাফের ট্রানজিটিভ ক্লোজার হলো একটি রিচার্জিবিলিটি ম্যাট্রিক্স যেখানে `reach[i][j] = 1` যদি নোড `i` থেকে নোড `j`-এ পৌঁছানো সম্ভব হয় (পাথ বিদ্যমান থাকে)। ওয়ারশল অ্যালগরিদম এটি O(V³) 시간에 কম্পিউট করে।

এলগরিদম (Warshall's Algorithm)

অ্যাডজেসেন্সি ম্যাট্রিক্স `adj` ইনপুট নিন।
`reach = adj` কপি করুন।
ত্রিক লুপ: `for k, for i, for j` → `reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j])`
ফাইনাল `reach` ম্যাট্রিক্সই ট্রানজিটিভ ক্লোজার।

উদাহরণ কোড

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cout << "নোড সংখ্যা: ";
    int n; cin >> n;

    vector<vector<int>> reach(n, vector<int>(n));
    cout << "অ্যাডজেসেন্সি ম্যাট্রিক্স লিখুন (0/1):\n";
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> reach[i][j];

    // Warshall's Algorithm
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);

    cout << "\nট্রানজিটিভ ক্লোজার ম্যাট্রিক্স:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            cout << reach[i][j] << " ";
        cout << "\n";
    }
    return 0;
}

আউটপুট উদাহরণ

ইনপুট:
নোড সংখ্যা: 4
অ্যাডজেসেন্সি ম্যাট্রিক্স:
1 1 0 0
1 0 1 0
1 0 0 0
1 0 1 0

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

ব্যাখ্যা

Warshall's Algorithm ডাইনামিক প্রোগ্রামিং ব্যবহার করে সব জোড়া নোডের মধ্যে পাথ আছে কিনা তা নির্ণয় করে। আউটপুট ম্যাট্রিক্সে `reach[i][j] = 1` মানে `i` থেকে `j`-এ পাওয়া যায়। এটি ফ্লয়েড-ওয়ারশল অ্যালগরিদমের বুলিয়ান ভার্সন।