Cari jika terdapat laluan antara dua bucu dalam graf terarah

Dalam sains komputer dan teori graf, penyelesaian kepada pelbagai senario model kehidupan sebenar sangat bergantung pada graf terarah. Graf khusus ini terdiri daripada bucu yang disambungkan oleh tepi terarah yang menunjuk ke bucu lain. Menentukan sama ada laluan wujud antara dua titik yang ditentukan ialah masalah sukar biasa menggunakan graf terarah. Dalam artikel ini, kami akan meneroka pelbagai cara untuk menyelesaikan dilema ini menggunakan C++, termasuk sintaks yang diperlukan untuk setiap proses untuk memastikan perkara mudah difahami. Selain itu, kami akan memperincikan algoritma yang menggambarkan setiap kaedah dan menyertakan dua contoh kod boleh laku.

tatabahasa

Sebelum menyelami butiran khusus, adalah penting untuk memahami struktur bahasa yang menyokong metodologi di sini. Jadi, sebelum beralih kepada contoh kod, mari kita semak sintaks ini dahulu.

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph);

Algoritma

Mencari laluan antara dua bucu dalam graf terarah boleh diselesaikan menggunakan pelbagai teknik. Artikel ini akan memberi tumpuan kepada dua kaedah yang digunakan secara meluas −

Kaedah 1: Carian Pertama Kedalaman (DFS)

• Buat tatasusunan yang dilawati untuk menjejak bucu yang dilawati semasa traversal.

• Mulakan semua elemen tatasusunan yang dilawati kepada palsu.

• Tandakan startVertex sebagai dilawati.

• Jika bucu permulaan dan bucu penghujung adalah sama, kembalikan benar, menunjukkan bahawa terdapat laluan.

• Untuk setiap bucu bersebelahan bucu semasa, gunakan bucu bersebelahan sebagai bucu permulaan baharu dan panggil fungsi isPathExists secara rekursif.

• Kembalikan benar jika sebarang panggilan rekursif kembali benar.

• Jika tiada panggilan rekursif mengembalikan benar, panggilan itu kembali palsu.

Kaedah 2: Breadth First Search (BFS)

• Buat tatasusunan yang dilawati untuk menjejak bucu yang dilawati semasa traversal.

• Mulakan semua elemen tatasusunan yang dilawati kepada palsu.

• Buat baris gilir untuk menyimpan bucu yang belum selesai.

• Tambahkan startVertex pada baris gilir dan tandakannya sebagai dilawati.

• Jika baris gilir tidak kosong, lakukan operasi berikut:

• Nyah gilir satu bucu daripada baris gilir.

• Jika bucu dequeued adalah sama dengan endVertex, ia kembali benar, menunjukkan bahawa terdapat laluan.

• Bagi setiap bucu yang bersebelahan dengan bucu dequeued, jika ia belum dilawati lagi, masukkannya dalam baris gilir dan tandakannya sebagai telah dilawati.

• Mengembalikan palsu jika baris gilir menjadi kosong dan tiada laluan ditemui.

Contoh 1: Kaedah Carian Pertama Kedalaman (DFS)

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

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   if (startVertex == endVertex)
      return true;
  
   for (int adjVertex : graph[startVertex]) {
      if (!visited[adjVertex] && isPathExists(adjVertex, endVertex, graph))
         return true;
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

Output

A path exists between 0 and 5

Kod bermula dengan mentakrifkan fungsi yang dipanggil isPathExists, yang menerima startVertex, endVertex dan graf yang diwakili oleh senarai bersebelahan sebagai parameter. Ia memulakan vektor boolean yang dipanggil visited yang menjejaki bucu yang dilawati. Semasa melaksanakan fungsi ini, ia mula-mula menyemak sama ada startVertex dan endVertex adalah sama dengan membandingkannya.

Apabila bucu ini bertepatan sepenuhnya dalam konteks ini, fungsi kembali benar serta-merta.

Jika ini tidak berlaku, dan mereka berbeza antara satu sama lain, tindakan lain akan diambil untuk menyemak jarak antara mereka untuk menentukan sama ada laluan wujud di antara mereka.

Proses ini melibatkan berulang kali melelaran bucu bersebelahan bucu permulaan; setiap lelaran akan menggunakan bucu yang baru dicari sebagai titik permulaan baharu dan terus mencari laluan yang tersedia dengan memanggil "isPathExists" secara rekursif. Kitaran ini berulang sehingga semua laluan yang mungkin habis atau laluan yang berjaya ditemui.

Jika mana-mana panggilan berulang ini mengesan pinggir berpotensi yang menyambungkan nod permulaan dan nod akhir, maka output penapisan ini bermakna bahawa memang terdapat interkoneksi yang boleh digunakan antara kedua-dua nod ini. Oleh itu, True akan dikembalikan serta-merta.

Jika tidak, apabila kerumitan yang ditetapkan dalam algoritma menyebabkan tiada laluan tersedia, tindakan gelung selamat gagal akan dimulakan. Sekiranya keputusan sedemikian, ia mengembalikan Palsu, menyesali bahawa sambungan antara nod gagal.

Contoh 2: Kaedah Breadth First Search (BFS)

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

bool isPathExists(int startVertex, int endVertex, const vector<vector<int>>& graph) {
   vector<bool> visited(graph.size(), false);
   visited[startVertex] = true;
  
   queue<int> verticesQueue;
   verticesQueue.push(startVertex);
  
   while (!verticesQueue.empty()) {
      int currVertex = verticesQueue.front();
      verticesQueue.pop();
  
      if (currVertex == endVertex)
         return true;
  
      for (int adjVertex : graph[currVertex]) {
         if (!visited[adjVertex]) {
            visited[adjVertex] = true;
            verticesQueue.push(adjVertex);
         }
      }
   }
  
   return false;
}

int main() {
   // Example usage
   int numVertices = 6;
   vector<vector<int>> graph(numVertices);
   graph[0] = {1, 2};
   graph[1] = {3};
   graph[2] = {1};
   graph[3] = {4, 5};
   graph[4] = {};
   graph[5] = {4};

   int startVertex = 0;
   int endVertex = 5;

   if (isPathExists(startVertex, endVertex, graph))
      cout << "A path exists between " << startVertex << " and " << endVertex << endl;
   else
      cout << "No path exists between " << startVertex << " and " << endVertex << endl;

   return 0;
}

Output

A path exists between 0 and 5

Kod ini mentakrifkan fungsi isPathExists, yang menerima startVertex, endVertex dan graf yang diwakili oleh senarai bersebelahan sebagai parameter. Ia memulakan vektor boolean yang dipanggil visited untuk menjejak bucu yang dilawati, dan baris gilir dipanggil verticesQueue untuk menyimpan bucu yang belum selesai.

Fungsi ini bermula dengan beratur startVertex dan menandakannya sebagai dilawati. Operasi algoritma kami bermula dengan memasukkan gelung berulang yang berterusan selagi terdapat item dalam struktur baris gilir pemprosesannya. Semasa lelaran berstruktur ini diteruskan, dua semakan dilakukan setiap kitaran: mula-mula mengesahkan bahawa bucu dequeued lelaran semasa sepadan dengan titik akhir sasaran yang dinyatakan dalam pelaksanaan sebelumnya, jika kedua-duanya berjaya dipadankan, kembalikan 'benar' jika tidak Teruskan ke langkah seterusnya, iaitu untuk meneroka tempat-tempat terpencil yang berdekatan. Semasa proses penerokaan ini, sebarang bucu yang belum diterokai bersebelahan ditandakan sebagai 'dilawati' sebelum dimasukkan ke dalam baris gilir untuk lelaran dan ujian yang lebih mendalam untuk melihat sama ada ia sepadan dengan endVertex.

Selepas semua penerokaan dan pengesahan berjaya, jika tiada apa-apa ditambahkan pada baris gilir, fungsi tersebut akan kembali palsu.

Kesimpulan

Dalam pembangunan sains komputer, kerumitan menavigasi graf terarah mungkin menimbulkan masalah asas. Untuk mengurangkan cabaran ini, salah satu matlamat kami adalah untuk meneroka dua pendekatan biasa yang dilaksanakan menggunakan C++. Carian mendalam-dahulu (DFS) dan carian luas-dahulu (BFS) berada di barisan hadapan teknik ini, dan ia menyediakan prosedur langkah demi langkah dan contoh kod kerja yang menunjukkan setiap algoritma. Setelah dikuasai, kaedah ini membuka potensi baharu apabila berhadapan dengan halangan mencari laluan dalam berbilang tetapan (seperti rangkaian penghalaan atau menganalisis rangka kerja ketersambungan sosial) dan berfungsi sebagai titik permulaan yang berharga dalam fasa pembangunan peningkatan.

Atas ialah kandungan terperinci Cari jika terdapat laluan antara dua bucu dalam graf terarah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!