Bilangan komponen bersambung bagi graf yang diberikan selepas memadamkan bucu Q yang diberikan

Selepas mengalih keluar bucu yang ditentukan Q, bilangan subgraf terputus yang dicipta oleh bucu yang tinggal dalam graf diwakili oleh kiraan komponen yang disambungkan. Tiada sambungan tepi antara komponen individu sebaliknya, setiap komponen yang disambungkan terdiri daripada koleksi bucu yang disambungkan oleh tepi. Disebabkan penyingkiran bucu Q, beberapa bucu mungkin menjadi yatim, menyebabkan sambungan runtuh dan komponen baharu terbentuk. Kaedah ini bertujuan untuk menentukan bilangan subgraf terputus yang akan ada pada akhirnya. Banyak aplikasi, termasuk analisis rangkaian, penyelidikan rangkaian sosial dan kaedah pengoptimuman, memerlukan pengetahuan tentang bilangan komponen yang disambungkan.

Kaedah penggunaan

• Algoritma Kosaraju

• Kaedah berasaskan matriks

Algoritma Kosaraju

Selepas mengalih keluar bucu yang ditentukan Q daripada graf, algoritma Kosaraju digunakan untuk menentukan bilangan komponen yang dipautkan dalam rangkaian. Ia menggunakan carian pertama mendalam (DFS) dalam dua laluan. Ia mengkaji graf asal dalam pas pertama untuk mendapatkan "masa siap" bagi setiap bucu. Dalam laluan kedua, graf ditranspose (arah semua tepi diterbalikkan), dan DFS digunakan pada graf yang diubah bermula dari bucu dengan masa penyiapan paling lama. Kaedah ini menentukan bilangan komponen terpaut dalam graf yang diubah, mendedahkan bilangan subgraf yang rosak apabila pemadaman bucu dengan mengabaikan bucu Q yang dipadamkan dalam proses.

Algoritma

• Untuk menyimpan bucu saluran DFS awal, buat tindanan kosong.

• Pada graf asal, jalankan traversal DFS pertama:

  Gunakan DFS untuk meneroka komponen bucu bersambung bermula daripada bucu yang belum diterokai.

  Apabila semua bucu yang mengelilingi bucu telah dilawati, Mark mengakses bucu dan menolaknya ke tindanan.

• Terbalikkan arah setiap tepi untuk mengubah bentuk.

• Untuk pas DFS kedua, buat tatasusunan boolean untuk menjejak bucu yang dilawati.

• Jalankan graf yang diubah suai melalui pas DFS kedua:

  Alih keluar setiap bucu daripada tindanan secara bergilir-gilir.

  Gunakan DFS untuk meneroka komponen bucu yang berkaitan (jika tiada) tidak diakses atau dimusnahkan (bukan dalam Q). Sepanjang proses itu, Mark melawat puncak.

• Selepas mengalih keluar bucu Q, kiraan komponen yang disambungkan adalah sama dengan bilangan panggilan ke DFS kedua.

• Selepas mengalih keluar bucu Q, proses ini menjana bilangan komponen yang disambungkan dalam rangkaian.

Contoh

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

void dfs1(int vertex, vector<vector<int>>& graph, vector<bool>& visited, stack<int>& stk) {
    visited[vertex] = true;
    for (int neighbor : graph[vertex]) {
        if (!visited[neighbor])
            dfs1(neighbor, graph, visited, stk);
    }
    stk.push(vertex);
}

void dfs2(int vertex, vector<vector<int>>& transpose_graph, vector<bool>& visited) {
    visited[vertex] = true;
    for (int neighbor : transpose_graph[vertex]) {
        if (!visited[neighbor])
            dfs2(neighbor, transpose_graph, visited);
    }
}

int kosaraju(int N, vector<vector<int>>& graph, vector<vector<int>>& transpose_graph, vector<int>& Q) {
    vector<bool> visited(N + 1, false);
    stack<int> stk;

    for (int i = 1; i <= N; i++) {
        if (!visited[i])
            dfs1(i, graph, visited, stk);
    }

    fill(visited.begin(), visited.end(), false);

    for (int i = 0; i < Q.size(); i++) {
        visited[Q[i]] = true;
    }

    int count = 0;
    while (!stk.empty()) {
        int vertex = stk.top();
        stk.pop();
        if (!visited[vertex]) {
            dfs2(vertex, transpose_graph, visited);
            count++;
        }
    }

    return count;
}

int main() {
    int N = 7; 
    int M = 8; 
    int E = 2; 

    vector<vector<int>> graph(N + 1);
    vector<vector<int>> transpose_graph(N + 1);

    vector<pair<int, int>> edges = {{1, 2}, {2, 3}, {3, 1}, {2, 4}, {4, 5}, {5, 6}, {6, 4}, {7, 6}};

    for (const auto& edge : edges) {
        int u = edge.first;
        int v = edge.second;
        graph[u].push_back(v);
        transpose_graph[v].push_back(u);
    }

    vector<int> Q = {3, 4};

    int result = kosaraju(N, graph, transpose_graph, Q);
    cout << result << endl;

    return 0;
}

Output

5

Kaedah berasaskan matriks

Matriks bersebelahan atau senarai bersebelahan digunakan untuk mewakili graf dalam kaedah berasaskan matriks. Kemudian keluarkan bucu Q yang ditentukan daripada matriks. Bilangan komponen yang disambungkan pada graf yang diubah kemudiannya ditentukan dengan menggunakan algoritma traversal graf seperti carian mendalam-dahulu (DFS) atau carian luas-dahulu (BFS). Rekod merentasi bucu untuk mengelakkan pemprosesan semula. Kiraan komponen yang disambungkan dalam graf selepas mengalihkan bucu Q sepadan dengan bilangan kali kaedah traversal telah dijalankan. Kaedah ini boleh mengira kiraan komponen pautan dengan cekap untuk analisis graf yang berbeza dan aplikasi berkaitan rangkaian.

Algoritma

• Gunakan matriks bersebelahan atau senarai bersebelahan untuk mewakili graf.

• Graf yang diubah suai dijana dengan mengalih keluar bucu Q tertentu daripada matriks atau senarai.

• Tetapkan pembolehubah untuk menjejaki bilangan komponen yang disambungkan.

• Pada mulanya mengemas kini setiap bucu dalam graf secara berulang.

• Gunakan algoritma traversal graf (DFS atau BFS) pada setiap bucu yang belum diterokai.

• Tandakan bucu yang dilawati semasa traversal untuk mengelakkan pemprosesan semula.

• Teruskan melintasi sehingga semua bucu yang berkaitan dengan bucu awal telah dilihat.

• Untuk setiap set unik bucu bersambung yang ditemui, tambahkan bilangan komponen bersambung dalam persamaan sebanyak 1.

• Untuk mengakses setiap bucu dalam graf yang dikemas kini, ulangi langkah 5 hingga 8 mengikut keperluan.

• Selepas mengalih keluar bucu yang diperlukan, jumlah bilangan subgraf yang terputus dalam graf diwakili oleh nilai akhir kiraan komponen yang disambungkan.

Contoh

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

void dfs(vector<vector<int>>& graph, vector<bool>& visited, int node) {
    visited[node] = true;
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(graph, visited, neighbor);
        }
    }
}

int countReachableNodes(vector<vector<int>>& graph) {
    int N = graph.size();
    vector<bool> visited(N, false);
    int count = 0;

    for (int i = 0; i < N; ++i) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            count++;
        }
    }

    return count;
}

int main() {
    // Create the graph (Adjacency List representation)
    vector<vector<int>> graph = {
        {1},
        {0, 2},
        {1},
        {4},
        {3}
    };

    int reachableNodes = countReachableNodes(graph);
    cout << "Number of nodes accessible from all other nodes: " << reachableNodes << endl;

    return 0;
}

Output

Number of nodes accessible from all other nodes: 2

Kesimpulan

Ringkasnya, metrik utama dalam analisis rangkaian dan medan berkaitan ialah bilangan komponen bersambung yang tinggal dalam graf selepas mengalih keluar bilangan bucu tertentu. Kedua-dua kaedah berasaskan matriks dan algoritma Kosaraju menyediakan cara yang cekap untuk mengira kiraan ini. Kaedah berasaskan matriks menggunakan algoritma traversal graf seperti DFS atau BFS pada graf yang direka bentuk semula untuk mencari komponen terpaut dengan cekap, manakala algoritma Kosaraju menggunakan carian pertama mendalam dalam dua traversal untuk mengenal pasti komponen bersambung kuat. Kedua-dua kaedah menghasilkan hasil yang boleh dipercayai walaupun selepas mengalih keluar beberapa bucu, membantu memahami ketersambungan dan ciri-ciri struktur graf. Sifat graf dan keperluan khusus cabaran semasa menentukan pendekatan yang akan digunakan.

Atas ialah kandungan terperinci Bilangan komponen bersambung bagi graf yang diberikan selepas memadamkan bucu Q yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!