Algoritma penutupan transitif membandingkan algoritma pendaraban matriks dan algoritma penutupan reflektif

Bandingkan dua algoritma penutupan transitif berbeza: algoritma pendaraban matriks vs algoritma penutupan pantulan

Algoritma penutupan transitif digunakan untuk mencari penutupan transitif sesuatu hubungan, iaitu semua hubungan transitif pada hubungan. Dalam sains komputer, terdapat banyak cara untuk melaksanakan algoritma penutupan transitif. Dalam artikel ini, kami akan membandingkan dua algoritma penutupan transitif biasa: algoritma pendaraban matriks dan algoritma penutupan reflektif. Kami akan memperkenalkan prinsip dan contoh kod setiap algoritma secara terperinci, dan membandingkannya mengikut prestasi dan senario yang berkenaan.

Algoritma pendaraban matriks:
Algoritma pendaraban matriks ialah algoritma penutupan transitif yang cekap, yang menggunakan operasi pendaraban matriks untuk mengira penutupan transitif. Idea utama algoritma ini adalah untuk mengira secara beransur-ansur hubungan transitif antara semua pasangan nod melalui pendaraban matriks berulang. Langkah-langkah khusus adalah seperti berikut:

1. Memulakan matriks bersebelahan A, di mana Ai mewakili sama ada terdapat tepi dari nod i ke nod j.
2. Lakukan pendaraban berulang A sehingga A tidak lagi berubah. Dalam setiap lelaran, hasil darab A ditugaskan kepada A, dan unsur-unsur yang 0 dalam A ditukar kepada 1, menunjukkan bahawa terdapat hubungan transitif antara nod.
3. A akhir ialah penutupan transitif perhubungan.

Berikut ialah contoh kod algoritma pendaraban matriks:

void transitiveClosureMatrix(int[][] graph, int n) {
    int[][] tc = new int[n][n];
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            tc[i][j] = graph[i][j];
        }
    }
    
    for(int k = 0; k < n; k++) {
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                tc[i][j] = (tc[i][j] != 0) || (tc[i][k] != 0 && tc[k][j] != 0) ? 1 : 0;
            }
        }
    }
    
    // 输出传递闭包
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.print(tc[i][j] + " ");
        }
        System.out.println();
    }
}

Algoritma penutupan reflektif:
Algoritma penutupan reflektif ialah satu lagi algoritma penutupan transitif biasa, yang menggunakan rekursi untuk mengira penutupan transitif. Idea utama algoritma ini adalah untuk mencari hubungan transitif langsung nod dan secara rekursif mencari hubungan transitif tidak langsung. Langkah-langkah khusus adalah seperti berikut:

1. Memulakan matriks bersebelahan A, di mana Ai mewakili sama ada terdapat tepi dari nod i ke nod j.
2. Untuk setiap nod i, cari secara rekursif semua hubungan transitif langsung dan tidak langsung bermula dari i, dan tandakan pasangan nod yang sepadan sebagai 1 dalam A.
3. A akhir ialah penutupan transitif perhubungan.

Berikut ialah contoh kod algoritma penutupan reflektif:

void transitiveClosureReflexive(int[][] graph, int n) {
    int[][] tc = new int[n][n];
    for(int i = 0; i < n; i++) {
        transitiveClosureReflexiveUtil(graph, tc, i, i, n);
    }
    
    // 输出传递闭包
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            System.out.print(tc[i][j] + " ");
        }
        System.out.println();
    }
}

void transitiveClosureReflexiveUtil(int[][] graph, int[][] tc, int i, int j, int n) {
    tc[i][j] = 1;
    for(int k = 0; k < n; k++) {
        if(graph[j][k] == 1 && tc[i][k] == 0) {
            transitiveClosureReflexiveUtil(graph, tc, i, k, n);
        }
    }
}

Perbandingan prestasi dan senario yang berkenaan:
Kedua-dua algoritma pendaraban matriks dan algoritma penutupan reflektif boleh digunakan untuk mengira penutupan transitif, tetapi ia mempunyai prestasi dan prestasi yang berbeza. senario yang berkenaan. Kerumitan masa bagi algoritma pendaraban matriks ialah O(n^3) dan kerumitan ruang ialah O(n^2), yang sesuai untuk situasi di mana bilangan nod adalah kecil. Kerumitan masa bagi algoritma penutupan pantulan ialah O(n^2*m) dan kerumitan ruang ialah O(n^2), yang sesuai untuk situasi di mana bilangan nod adalah besar tetapi perhubungannya jarang.

Ringkasan:
Algoritma pendaraban matriks dan algoritma penutupan pantulan ialah dua algoritma penutupan transitif biasa. Algoritma pendaraban matriks mengira penutupan transitif melalui pendaraban matriks berulang dan sesuai untuk situasi di mana bilangan nod adalah kecil. Algoritma penutupan reflektif mengira penutupan transitif dalam cara rekursif, yang sesuai untuk situasi di mana bilangan nod adalah besar tetapi hubungannya jarang. Memilih algoritma yang sesuai berdasarkan situasi sebenar boleh meningkatkan kecekapan pengiraan.

Atas ialah kandungan terperinci Algoritma penutupan transitif membandingkan algoritma pendaraban matriks dan algoritma penutupan reflektif. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!