Diberi graf, program C untuk melaksanakan traversal carian pertama mendalam (DFS) menggunakan matriks bersebelahan

Pengenalan

Teori graf membolehkan kita mengkaji dan menggambarkan hubungan antara objek atau entiti. Dalam teknologi sains komputer semasa, traversal graf memainkan peranan penting dalam meneroka dan menganalisis pelbagai jenis struktur data. Salah satu operasi utama yang dilakukan pada graf ialah traversal - mengikut laluan tertentu untuk melawati semua bucu atau nod. Traversal DFS berdasarkan pendekatan depth-first membolehkan kami meneroka kedalaman graf sebelum menjejak semula dan meneroka cawangan lain. Dalam artikel ini, kami akan melaksanakan traversal DFS menggunakan perwakilan matriks bersebelahan dalam C.

Menggunakan matriks bersebelahan untuk traversal DFS

Graf terdiri daripada dua komponen utama, iaitu bucu atau nod yang mewakili entiti atau elemen, dan tepi yang menghubungkan bucu ini, menerangkan hubungan antara mereka.

Satu-satunya cara untuk mewakili hubungan antara bucu dalam graf berwajaran atau tidak berwajaran adalah melalui matriks bersebelahan. Ia biasanya berbentuk matriks segi empat sama, di mana baris mewakili bucu sumber dan lajur mewakili bucu sasaran, dan setiap sel mengandungi maklumat tentang kewujudan atau berat tepi antara pasangan yang sepadan.

Contoh

Input diberikan oleh set elemen tertentu menggunakan empat bucu graf. Inputnya ialah:

1 0 0 1
0 1 1 0
0 1 1 0
1 0 0 1

Andaikan puncak permulaan graf ialah 2. Graf akan dilalui bermula dari bucu "2". Bucu bersebelahan bucu "2" jelas 1 dan 3. Memandangkan puncak permulaan ialah 2, ia tidak boleh diakses semula semasa traversal. Puncak 3 dilawati selepas bucu 2, maka kita perlu menyemak bucu 1 dan 2 bersebelahan bucu 3. Bucu 1 dan bucu 2 telah dilawati dan lintasan berhenti.

Kaedah 1: Program C yang melibatkan traversal DFS menggunakan matriks bersebelahan sebagai input dalam graf yang diberikan

Input ditakrifkan dengan beberapa nombor dan menggunakan gelung for ia akan mengulangi matriks bersebelahan dan mengembalikan traversal DFS.

Algoritma

Langkah 1: Program pertama mentakrifkan pemalar "MAX" untuk mewakili bilangan maksimum nod dalam graf yang diberikan, dan memulakan tatasusunan bernama "dilawati" untuk menjejak sama ada nod tertentu Telah dilawati semasa perjalanan.

Langkah 2: Fungsi "dfs()" mengambil matriks bersebelahan segi empat sama sebagai parameter, "adjMatrix" mewakili graf kami, jumlah bilangan bucu ialah "vCount", dan titik permulaan ialah ` Mula`. Fungsi ini melakukan rekursif carian mendalam-pertama bagi graf yang diberikan.

Langkah 3: Dalam fungsi "dfs()", kami menandakan setiap bucu yang sedang diproses sebagai " menggunakan indeks dalam tatasusunan "visited[]" berasaskan boolean Dilawati dan cetak nilainya dengan sewajarnya.

Langkah 4 : Gelung di dalam "dfs()" melelaran secara rekursif semua jiran nod semasa yang tidak dilawati sehingga mustahil untuk mendapatkan bucu yang disambungkan kepadanya.

Langkah 5: Dalam main(), kami menggunakan gelung bersarang untuk membaca input pengguna, seperti bilangan bucu "vCount" dan sambungannya yang sepadan ke dalam matriks bersebelahan.

Langkah 6: Kami kemudian menggesa pengguna untuk titik permulaan yang diingini dan kemudian memulakan setiap elemen tatasusunan "dilawati[]" kepada sifar (memandangkan tiada nod telah dilawati lagi ).

Langkah 7: Akhirnya, atur cara memanggil fungsi "dfs()" dengan parameter yang sesuai untuk memulakan traversal carian depth-first dan mencetak laluan traversal DFS.

Contoh

//Including the required header files
#include<stdio.h>
#define MAX 100

int visited[MAX];
//dfs function is defined with three arguments
void dfs(int adjMatrix[][MAX], int vCount, int start) {
   visited[start] = 1;
   printf("%d ", start);

   for(int i=0; i<vCount; i++) {
      if(adjMatrix[start][i] && !visited[i]) {
         dfs(adjMatrix,vCount,i);
      }
   }
}
//main function is used to implement the above functions
int main() {
   int adjMatrix[MAX][MAX];
   int vCount;

   // Assigning the variable with value of 4
   vCount = 4;

   // Assigning the adjacency matrix directly same the example given above
   adjMatrix[0][0] = 1;
   adjMatrix[0][1] = 0;
   adjMatrix[0][2] = 0;
   adjMatrix[0][3] = 1;
   adjMatrix[1][0] = 0;
   adjMatrix[1][1] = 1;
   adjMatrix[1][2] = 1;
   adjMatrix[1][3] = 0;
   adjMatrix[2][0] = 0;
   adjMatrix[2][1] = 1;
   adjMatrix[2][2] = 1;
   adjMatrix[2][3] = 0;
   adjMatrix[3][0] = 1;
   adjMatrix[3][1] = 0;
   adjMatrix[3][2] = 0;
   adjMatrix[3][3] = 1;
//Declaring the start variable as integer data type and later assigned with a value of 2
   int start;
   
   // Assigning the starting vertex directly
   start = 2;
   
   for(int i = 0; i < MAX; ++i) {
      visited[i] = 0;
   }

   printf("\nDFS Traversal: ");
   dfs(adjMatrix, vCount, start);
   

   return 0;
}

Output

DFS Traversal: 2 1

KESIMPULAN

Dengan menggunakan matriks bersebelahan sebagai perwakilan graf, kami boleh melaksanakan DFS dengan cekap pada set data yang besar atau kompleks. Dalam kertas kerja ini, kami menerangkan perkara ini secara terperinci dan mencadangkan program C yang melaksanakan traversal carian mendalam-pertama menggunakan perwakilan berasaskan matriks bersebelahan. Carian pertama mendalam ialah algoritma yang berkuasa untuk meneroka dan menganalisis struktur graf.

Atas ialah kandungan terperinci Diberi graf, program C untuk melaksanakan traversal carian pertama mendalam (DFS) menggunakan matriks bersebelahan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!