Semak sama ada terdapat kitaran panjang 3 dalam graf yang memenuhi syarat yang diberikan

. Jika bucu mempunyai dua jiran yang terlalu bersambung, kitaran panjang 3 wujud. Keadaan ini menjamin bahawa terdapat kelebihan antara dua jiran, sehingga membentuk segitiga. Dengan menapis semua bucu dan bucu jiran mereka, kami akan mengenal pasti sama ada kitaran sedemikian wujud. Jika kita mendapati bahawa satu bucu mempunyai dua jiran yang berkaitan, kita boleh membuat kesimpulan bahawa graf menunjukkan kitaran panjang 3 yang memenuhi syarat yang diberikan.

Kaedah penggunaan

Kaedah Adjacency Matrix

• Kaedah senarai bersebelahan

• Kaedah bersebelahan

Untuk menyemak sama ada terdapat kitaran panjang 3 dalam graf yang memenuhi syarat tertentu, kita boleh menggunakan kaedah berjangkit. Dalam pendekatan ini, kami mengulang untuk setiap bucu dalam graf dan menyemak bucu jirannya. Untuk setiap bucu, kami menyemak sama ada mana-mana dua bucu bersebelahan dengannya terlalu berkait rapat. Jika perlawanan sedemikian ditemui, kami menyemak sama ada syarat untuk perlawanan itu dipenuhi. Jika syarat dipenuhi, ia menunjukkan gelung panjang 3 yang hampir memenuhi syarat yang diberikan. Dengan melihat semua bucu dalam graf, kita boleh menentukan sama ada kitaran sedemikian wujud.

Algoritma

Mulakan pembolehubah boolean bernama "cycleExists" kepada false.

• Lelaran pada setiap bucu dalam graf:

• Untuk setiap bucu, ulang bucu bersebelahannya.

  • Untuk setiap bucu bersebelahan, tekankan bucu bersebelahannya (kecuali bucu semasa).

  • Jika mana-mana dua bucu bersebelahan berkaitan, teruskan ke langkah seterusnya.

  Periksa sama ada gabungan bucu yang berkaitan yang terdapat dalam langkah 2c memenuhi syarat.

• Jika syarat dipenuhi, tetapkan "cycleExists" kepada benar dan keluar dari gelung.

  Selepas melengkapkan kitaran, semak nilai "cycleExists".

• Jika "cycleExists" adalah benar, maka terdapat kitaran panjang 3 dalam graf yang memenuhi syarat yang diberikan.

  • Jika "cycleExists" salah, tiada kitaran sedemikian wujud.

  Hasil keluaran.

• Pengiraan ini mengulangi bucu graf, menganalisis bucu bersebelahan mereka dan menyemak sama ada sebarang padanan bucu bersebelahan membentuk kitaran panjang 3 yang memenuhi syarat yang diberikan.

• Contoh

  #include <iostream>
  #include <vector>
  
  using namespace std;
  
  bool checkCycle(vector<vector<int>>& graph, int v, vector<bool>& visited, int parent, int condition) {
      visited[v] = true;
  
      for (int u : graph[v]) {
          if (!visited[u]) {
              visited[u] = true;
  
              for (int w : graph[u]) {
                  if (visited[w] && w != parent && condition == graph[v][u] + graph[u][w]) {
                      return true;
                  }
              }
  
              visited[u] = false;
          }
      }
  
      return false;
  }
  
  bool hasCycleOfLength3(vector<vector<int>>& graph, int condition) {
      int numVertices = graph.size();
      vector<bool> visited(numVertices, false);
  
      for (int v = 0; v < numVertices; v++) {
          visited[v] = true;
  
          for (int u : graph[v]) {
              if (checkCycle(graph, u, visited, v, condition)) {
                  return true;
              }
          }
  
          visited[v] = false;
      }
  
      return false;
  }
  
  int main() {
      int numVertices, numEdges;
      cout << "Enter the number of vertices and edges: ";
      cin >> numVertices >> numEdges;
  
      vector<vector<int>> graph(numVertices);
  
      cout << "Enter the connections between vertices (u, v) and their corresponding weights: " << endl;
      for (int i = 0; i < numEdges; i++) {
          int u, v, weight;
          cin >> u >> v >> weight;
  
          graph[u].push_back(v);
          graph[v].push_back(u);
  
          // Store the weight/condition between u and v
          graph[u][v] = weight;
          graph[v][u] = weight;
      }
  
      int condition;
      cout << "Enter the condition to be satisfied: ";
      cin >> condition;
  
      if (hasCycleOfLength3(graph, condition)) {
          cout << "Cycle of length 3 satisfying the condition exists." << endl;
      } else {
          cout << "Cycle of length 3 satisfying the condition does not exist." << endl;
      }
  
      return 0;
  }
  
  
  

  Output

Enter the number of vertices and edges:  

Kaedah senarai bersebelahan

Kaedah senarai bersebelahan boleh menjadi struktur maklumat yang digunakan untuk bercakap dengan gambar rajah. Dalam pendekatan ini, setiap bucu graf dikaitkan dengan senarai yang mengandungi semua bucu bersebelahannya. Untuk menyemak sama ada terdapat kitaran panjang 3 dalam graf yang memenuhi syarat yang diberikan, kami akan mengulangi setiap bucu dan bucu jirannya. Untuk setiap bucu bersebelahan, kami menyemak sama ada ia mengandungi bucu bersebelahan yang sama dengan bucu semasa. Jika bucu sepunya seperti itu wujud, maka gelang dengan panjang 3 ditemui. Pendekatan ini menjamin penyiasatan graf yang cekap dengan menyimpan data penting tentang hampir semua bucu dalam senarai berjangkit dan perkaitannya.

Algoritma

Buat senarai berjangkit yang bercakap dengan graf, di mana setiap bucu mengandungi senarai bucu jirannya.

• Lelaran pada setiap bucu dalam graf.

• Untuk setiap bucu, ulang bucu bersebelahannya.

• Untuk setiap bucu bersebelahan, tekankan bucu bersebelahannya (kecuali bucu semasa).

• Periksa sama ada terdapat bucu sepunya antara bucu semasa dan bucu bersebelahan bucu bersebelahan.

• Jika bucu sepunya ditemui, gelang panjang 3 wujud. Kembali benar.

• Jika tiada cincin dengan panjang 3 ditemui, kembalikan palsu.

• Contoh

  #include <iostream>
  #include <vector>
  #include <unordered_set>
  
  using namespace std;
  
  bool hasCycleOfLength3(vector<vector<int>>& graph) {
      int n = graph.size();
      
      for (int u = 0; u < n; ++u) {
          unordered_set<int> adjSet(graph[u].begin(), graph[u].end());
  
          for (int v : graph[u]) {
              for (int w : graph[v]) {
                  if (w != u && adjSet.count(w) > 0) {
                      return true; // Cycle of length 3 found
                  }
              }
          }
      }
  
      return false; // No cycle of length 3 found
  }
  
  int main() {
      // Create the graph as an adjacency list
      vector<vector<int>> graph = {
          {1, 2},
          {0, 2},
          {0, 1, 3},
          {2, 4},
          {3}
      };
  
      // Check if a cycle of length 3 exists
      bool cycleExists = hasCycleOfLength3(graph);
  
      // Print the result
      if (cycleExists) {
          cout << "A cycle of length 3 exists in the graph." << endl;
      } else {
          cout << "No cycle of length 3 exists in the graph." << endl;
      }
  
      return 0;
  }
  

Output

A cycle of length 3 exists in the graph.

Kesimpulan

Artikel ini melihat cara untuk menyemak sama ada terdapat gelung panjang 3 dalam graf yang memenuhi syarat tertentu. Ia menggambarkan dua pendekatan, khususnya pendekatan bingkai menular dan pendekatan senarai menular. Artikel ini mengesan proses pengiraan dan memberikan bit kod C untuk kedua-dua kaedah. Pendekatan rangkaian berjangkit melibatkan penekanan setiap bucu dan bucu bersebelahannya untuk mengenal pasti kitaran panjang 3 yang memenuhi syarat. Kaedah senarai berjangkit mengeksploitasi struktur maklumat yang bercakap dengan graf dan meneliti bucu biasa antara bucu bersebelahan untuk menentukan kehampiran kitaran.

Atas ialah kandungan terperinci Semak sama ada terdapat kitaran panjang 3 dalam graf yang memenuhi syarat yang diberikan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!