โปรแกรม C++ หาค่าผกผันของเมทริกซ์กราฟ (Graph Matrix)

บทนำ

นี่คือโปรแกรม C++ สำหรับหาค่าผกผันของเมทริกซ์กราฟ ค่าผกผันของเมทริกซ์มีอยู่ก็ต่อเมื่อเมทริกซ์นั้นเป็น non-singular คือ determinant ไม่เป็นศูนย์ วิธีหาค่าผกผันมีหลายวิธี ตัวอย่างนี้ใช้ adjoint matrix และ determinant

ขั้นตอนการทำงาน

Begin
  function INV() หาค่าผกผันของเมทริกซ์:
    เรียกฟังก์ชัน DET()
    เรียกฟังก์ชัน ADJ()
    หาค่าผกผันด้วยสูตร: Inverse(matrix) = ADJ(matrix) / DET(matrix)
End

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

#include <bits/stdc++.h>
using namespace std;
#define N 5

void getCfactor(int M[N][N], int t[N][N], int p, int q, int n) {
    int i = 0, j = 0;
    for (int r = 0; r < n; r++) {
        for (int c = 0; c < n; c++) {
            if (r != p && c != q) {
                t[i][j++] = M[r][c];
                if (j == n - 1) {
                    j = 0;
                    i++;
                }
            }
        }
    }
}

int DET(int M[N][N], int n) {
    int D = 0;
    if (n == 1)
        return M[0][0];
    int t[N][N];
    int s = 1;
    for (int f = 0; f < n; f++) {
        getCfactor(M, t, 0, f, n);
        D += s * M[0][f] * DET(t, n - 1);
        s = -s;
    }
    return D;
}

void ADJ(int M[N][N], int adj[N][N]) {
    if (N == 1) {
        adj[0][0] = 1;
        return;
    }
    int s = 1;
    int t[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            getCfactor(M, t, i, j, N);
            s = ((i + j) % 2 == 0) ? 1 : -1;
            adj[j][i] = (s) * (DET(t, N - 1));
        }
    }
}

bool INV(int M[N][N], float inv[N][N]) {
    int det = DET(M, N);
    if (det == 0) {
        cout << "can't find its inverse";
        return false;
    }
    int adj[N][N];
    ADJ(M, adj);
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            inv[i][j] = adj[i][j] / float(det);
    return true;
}

template<class T>
void print(T A[N][N]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++)
            cout << A[i][j] << " ";
        cout << endl;
    }
}

int main() {
    int M[N][N] = {
        {1, 2, 3, 4, -2},
        {-5, 6, 7, 8, 4},
        {9, 10, -11, 12, 1},
        {13, -14, -15, 0, 9},
        {20, -26, 16, -17, 25}
    };
    float inv[N][N];
    cout << "Input matrix is :\n";
    print(M);
    cout << "\nThe Inverse is :\n";
    if (INV(M, inv))
        print(inv);
    return 0;
}

ผลลัพธ์

Input matrix is :
1 2 3 4 -2
-5 6 7 8 4
9 10 -11 12 1
13 -14 -15 0 9
20 -26 16 -17 25

The Inverse is :
0.0811847 -0.0643008 0.0493814 -0.0247026 0.0237006
-0.126819 -0.0161738 0.0745377 -0.0713976 0.0151639
0.0933664 0.0028245 -0.0111876 -0.0220437 0.0154006
0.143624 0.0582573 -0.0282371 0.0579023 -0.0175466
-0.15893 0.0724272 0.0259728 -0.00100988 0.0150219