Tanya sama ada bucu X dan Y berada dalam komponen bersambung yang sama bagi graf tidak berarah

Teori graf merangkumi kajian komponen bersambung, iaitu subgraf dalam graf tidak berarah di mana setiap pasangan bucu dipautkan oleh laluan dan tidak mempunyai bucu lain dengannya bersambung .

Dalam artikel ini, kita akan menyelidiki cara menggunakan bahasa pengaturcaraan C/C++ untuk menentukan sama ada dua bucu X dan Y tergolong dalam komponen bersambung yang sama dalam graf tidak berarah. Kami akan menjelaskan sintaks dan rasional kaedah sebelum menjelaskan sekurang-kurangnya dua cara berbeza untuk menyelesaikan masalah ini. Di samping itu, kami akan menyediakan contoh kod khusus dan hasil yang sepadan untuk setiap kaedah.

tatabahasa

Coretan kod yang disediakan mengisytiharkan tiga fungsi dalam C++ untuk perwakilan grafik. Fungsi isConnected mengambil dua bucu X dan Y dan mengembalikan nilai Boolean yang menunjukkan sama ada ia tergolong dalam komponen bersambung yang sama. Fungsi addEdge mengambil dua bucu X dan Y dan mewujudkan sambungan antara mereka dalam graf. Fungsi InitializeGraph mengambil nilai integer n sebagai input dan menyediakan graf dengan n bucu. Fungsi ini boleh dilaksanakan menggunakan pelbagai algoritma graf, seperti carian mendalam-dahulu atau carian luas-dahulu, untuk menyemak ketersambungan dua bucu dan mewujudkan sambungan antara bucu dalam graf.

bool isConnected(int X, int Y)
{
   // Code to check if X and Y are in the same connected component
   // Return true if X and Y are in the same connected component, false otherwise
}

void addEdge(int X, int Y)
{
   // Code to add an edge between vertices X and Y in the graph
}
void initializeGraph(int n)
{
   // Code to initialize the graph with 'n' vertices
}

Algoritma

Langkah 1 - Gunakan fungsi mulakan Graf untuk memulakan graf dengan bilangan bucu yang ditentukan.

Langkah 2 - Gunakan fungsi addEdge untuk menambah tepi

antara bucu

Langkah 3 - Laksanakan kaedah traversal graf untuk melintasi setiap bucu yang berkaitan dengan bucu dan tandakannya sebagai dilawati.

Langkah 4 - Gunakan kaedah lintasan graf yang dibina untuk menentukan sama ada kedua-dua bucu X dan Y telah dilawati.

Langkah 5 - Jika kedua-dua bucu X dan Y dilawati, kembalikan benar;

kaedah

• Kaedah 1 - Menggunakan DFS; ia ialah algoritma lintasan graf yang melawati bucu secara berulang dan menandakannya sebagai dilawati untuk mengkaji graf.

• Kaedah 2 - Gunakan kaedah carian kesatuan, yang menggunakan struktur data untuk memantau pembahagian koleksi kepada subkumpulan yang berbeza. Ia boleh mengenal pasti bahagian bersambung graf tidak terarah dengan berkesan.

Kaedah 1

Dalam kaedah ini, ia menggunakan DFS untuk menyemak sama ada bucu X dan Y berada dalam komponen yang disambungkan yang sama, kita boleh bermula dari bucu X dan melintasi graf menggunakan DFS.

Contoh 1

Kod dinilai untuk mengesahkan sama ada dua bucu X dan Y tergolong dalam komponen bersambung yang sama dalam graf. Ia menggunakan algoritma carian pertama mendalam (DFS) untuk merentasi graf dan menentukan ketersambungan bucu. Graf diterangkan menggunakan senarai bersebelahan, di mana tepi antara bucu disimpan sebagai senarai bucu jiran setiap bucu. Kod ini memulakan tatasusunan yang dilawati untuk memantau bucu yang telah diterokai semasa traversal DFS. Laksanakan fungsi DFS pada bucu X. Jika bucu Y didapati dilawati semasa proses DFS, ini bermakna kedua-dua X dan Y adalah sebahagian daripada komponen yang disambungkan yang sama. Fungsi utama menyediakan graf dengan mencipta senarai bersebelahan dan menambah tepi padanya, dan kemudian melakukan berbilang pertanyaan untuk mengesahkan bahawa dua bucu berada dalam komponen yang disambungkan yang sama.

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

vector<int> adjList[100005];
bool visited[100005];

void dfs(int u) {
   visited[u] = true;
   for (int v : adjList[u])
      if (!visited[v])
   dfs(v);
}

bool areVerticesInSameComponentDFS(int X, int Y, int n) {
   for (int i = 1; i <= n; i++)
      visited[i] = false;
   dfs(X);
   return visited[Y];
}

int main() {
   int n = 5;
   int m = 4;
   int edges[][2] = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
   for (int i = 0; i < m; i++) {
      int u = edges[i][0];
      int v = edges[i][1];
      adjList[u].push_back(v);
      adjList[v].push_back(u);
   }
   int q = 2;
   int queries[][2] = {{1, 4}, {2, 5}};
   for (int i = 0; i < q; i++) {
      int X = queries[i][0];
      int Y = queries[i][1];
      if (areVerticesInSameComponentDFS(X, Y, n))
         cout << "Vertices " << X << " and " << Y << " are in the same connected component." << endl;
      else
         cout << "Vertices " << X <<" and " << Y << " are not in the same connected component." << endl;
   }
   return 0;
}

Output

Vertices 1 and 4 are in the same connected component.
Vertices 2 and 5 are in the same connected component.

Kaedah 2

Dalam pendekatan ini, kita boleh mula-mula menetapkan setiap bucu kepada set bercapah untuk menggunakan kaedah dan cari untuk menentukan sama ada bucu X dan Y berada dalam komponen terpaut yang sama. Pengumpulan titik akhir tepi kemudiannya boleh digabungkan untuk setiap tepi dalam graf. Akhir sekali, kita boleh menentukan sama ada bucu X dan Y adalah ahli set yang sama, menunjukkan bahawa ia adalah komponen yang berkaitan.

Contoh 2

Kod ini melaksanakan dan mencari algoritma untuk menyemak sama ada dua bucu berada dalam komponen graf yang disambungkan yang sama. Input dikodkan keras dalam bentuk bilangan bucu n, bilangan tepi m dan tatasusunan tepi Tepi[m][2], dan nombor pertanyaan q dan tatasusunan pertanyaan Pertanyaan[q][2]. Fungsi merge(u, v) menggabungkan set yang mengandungi bucu u dengan set yang mengandungi bucu v. Fungsi areVerticesInSameComponentUnionFind(X, Y) menyemak sama ada bucu X dan Y berada dalam komponen bersambung yang sama dengan mencari nod induknya dan menyemak sama ada ia sama. Jika ia adalah sama, bucu berada dalam komponen bersambung yang sama, jika tidak, ia tidak. Hasil pertanyaan akan dicetak ke konsol.

#include <iostream>
using namespace std;
int parent[100005];
// Function to find the parent of a set using the Union-Find algorithm
int find(int u) {
    if (parent[u] == u) {
        return u;
    }
    return find(parent[u]);
}
void merge(int u, int v) {
    int parentU = find(u); // find the parent of u
    int parentV = find(v);
    if (parentU != parentV) {
        parent[parentU] = parentV;
    }
}
bool areVerticesInSameComponentUnionFind(int X, int Y) {
    int parentX = find(X); // find the parent of X
    int parentY = find(Y); // find the parent of Y
    return parentX == parentY;
}
int main() {
    int n = 5, m = 4;
    int edges[m][2] = {{1, 2}, {2, 3}, {3, 4}, {4, 5}};
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        merge(u, v);
    }
    int q = 3;
    int queries[q][2] = {{1, 5}, {3, 5}, {1, 4}};
    for (int i = 0; i < q; i++) {
        int X = queries[i][0], Y = queries[i][1];
        if (areVerticesInSameComponentUnionFind(X, Y)) {
            cout << "Vertices " << X << " and " << Y << " are in the same connected component." << endl;
        } else {
            cout << "Vertices " << X << " and " << Y << " are not in the same connected component." << endl;
        }
    }
    return 0;
}

Output

Vertices 1 and 5 are in the same connected component.
Vertices 3 and 5 are in the same connected component.
Vertices 1 and 4 are in the same connected component.

KESIMPULAN

Dalam kod ini, kami memperkenalkan dua kaedah untuk menentukan sama ada dua bucu graf tidak terarah X dan Y berkaitan antara satu sama lain. Strategi kedua menggunakan algoritma pencarian kesatuan untuk menjejaki set terputus-putus, manakala pendekatan pertama menggunakan carian mendalam-pertama (DFS) untuk merentasi graf untuk menandakan bucu yang dilawati.

Atas ialah kandungan terperinci Tanya sama ada bucu X dan Y berada dalam komponen bersambung yang sama bagi graf tidak berarah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!