Warshall's Algorithm สร้าง Transitive Closure ของกราฟใน C++

Transitive Closure ของ directed graph คือเมทริกซ์ที่บอกว่า vertex j ไปถึงจาก vertex i ได้หรือไม่ (มี path หรือไม่) Warshall's Algorithm คำนวณได้ใน O(n³)

หลักการ

ใช้ Dynamic Programming: พิจารณาว่า path จาก i ไป j สามารถผ่าน vertex k ได้หรือไม่

T[i][j] = T[i][j] OR (T[i][k] AND T[k][j])

โดย T คือ adjacency matrix (T[i][j] = 1 ถ้ามี edge i→j)

อัลกอริทึม

for k = 0 to n-1:
    for i = 0 to n-1:
        for j = 0 to n-1:
            T[i][j] = T[i][j] || (T[i][k] && T[k][j])

ตัวอย่างโค้ด

#include <iostream>
#include <vector>
#include <iomanip>

using namespace std;

using Matrix = vector<vector<int>>;

Matrix warshall(const Matrix& adj) {
    int n = adj.size();
    Matrix T = adj;  // Copy
    
    // Warshall's algorithm
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                T[i][j] = T[i][j] || (T[i][k] && T[k][j]);
            }
        }
    }
    return T;
}

void printMatrix(const Matrix& M, const string& label = "") {
    if (!label.empty()) cout << label << endl;
    int n = M.size();
    cout << "   ";
    for (int j = 0; j < n; ++j) cout << setw(3) << char('a' + j);
    cout << endl;
    
    for (int i = 0; i < n; ++i) {
        cout << char('a' + i) << "  ";
        for (int j = 0; j < n; ++j) {
            cout << setw(3) << M[i][j];
        }
        cout << endl;
    }
}

int main() {
    // Example graph
    Matrix adj = {
        {1, 1, 0, 0},  // a -> a, b
        {1, 0, 1, 0},  // b -> a, c
        {1, 0, 0, 0},  // c -> a
        {1, 0, 1, 0}   // d -> a, c
    };
    
    cout << "Original Adjacency Matrix:" << endl;
    printMatrix(adj);
    
    Matrix closure = warshall(adj);
    
    cout << "\nTransitive Closure (Warshall):" << endl;
    printMatrix(closure);
    
    // Interactive input
    cout << "\n--- Interactive Input ---" << endl;
    int n;
    cout << "Number of vertices (max 10): ";
    cin >> n;
    
    if (n > 0 && n <= 10) {
        Matrix userAdj(n, vector<int>(n, 0));
        char ans;
        
        cout << "Enter 'y' for edge, 'n' for no edge:\n";
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                cout << "Edge " << char('a'+i) << " -> " << char('a'+j) << "? ";
                cin >> ans;
                userAdj[i][j] = (ans == 'y' || ans == 'Y') ? 1 : 0;
            }
        }
        
        Matrix userClosure = warshall(userAdj);
        cout << "\nTransitive Closure:" << endl;
        printMatrix(userClosure);
    }
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

Original Adjacency Matrix:
     a  b  c  d
a    1  1  0  0
b    1  0  1  0
c    1  0  0  0
d    1  0  1  0

Transitive Closure (Warshall):
     a  b  c  d
a    1  1  1  0
b    1  1  1  0
c    1  1  1  0
d    1  1  1  0

การวิเคราะห์

• Time Complexity: O(n³) - เหมาะสำหรับ n ≤ ~400
• Space Complexity: O(n²)
• Bitwise Optimization: ใช้ bitset ได้เร็วขึ้น 32-64 เท่า

Bitwise Optimization (C++)

#include <bitset>
#include <vector>

using namespace std;

const int MAX_N = 1000;

vector<bitset<MAX_N>> warshallBitset(vector<bitset<MAX_N>> adj) {
    int n = adj.size();
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            if (adj[i][k]) {
                adj[i] |= adj[k];  // Bitwise OR ทั้งแถว
            }
        }
    }
    return adj;
}

การประยุกต์ใช้

• Database: Query optimization, reachability
• Compiler: Control flow analysis, dead code elimination
• Network: Routing, connectivity analysis
• Social Networks: Friend-of-friend recommendations
• Game AI: State reachability in planning

เปรียบเทียบกับ Floyd-Warshall

Warshall: Transitive closure (boolean) - O(n³)
Floyd-Warshall: All-pairs shortest paths (weighted) - O(n³)