Étant donné un graphique, programme C pour implémenter une traversée de recherche en profondeur (DFS) à l'aide d'une matrice de contiguïté

Présentation

La théorie des graphes nous permet d'étudier et de visualiser les relations entre des objets ou des entités. Dans la technologie informatique actuelle, le parcours de graphes joue un rôle crucial dans l’exploration et l’analyse de différents types de structures de données. L'une des opérations clés effectuées sur un graphe est le parcours : suivre un chemin spécifique pour visiter tous les sommets ou nœuds. Le parcours DFS basé sur une approche axée sur la profondeur nous permet d'explorer la profondeur du graphique avant de revenir en arrière et d'explorer d'autres branches. Dans cet article, nous allons implémenter le parcours DFS en utilisant la représentation matricielle de contiguïté en C.

Utilisation de la matrice de contiguïté pour le parcours DFS

Un graphe se compose de deux composants principaux, les sommets ou nœuds qui représentent des entités ou des éléments, et les arêtes qui relient ces sommets, décrivant les relations entre eux.

La seule façon de représenter la relation entre les sommets dans un graphique pondéré ou non pondéré consiste à utiliser une matrice de contiguïté. Il prend généralement la forme d'une matrice carrée, où les lignes représentent les sommets sources et les colonnes représentent les sommets cibles, et chaque cellule contient des informations sur l'existence ou le poids d'une arête entre les paires correspondantes.

Exemple

L'entrée est donnée via un ensemble spécifique d'éléments utilisant les quatre sommets du graphique. L'entrée est :

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

Supposons que le sommet de départ du graphique soit 2. Le graphe sera parcouru à partir du sommet "2". Les sommets adjacents du sommet « 2 » sont évidemment 1 et 3. Puisque le sommet de départ est 2, il n’est plus accessible pendant le parcours. Le sommet 3 est visité après le sommet 2, nous devons alors vérifier les sommets adjacents 1 et 2 du sommet 3. Le sommet 1 et le sommet 2 ont été visités et le parcours s'arrête.

Méthode 1 : programme C impliquant un parcours DFS utilisant une matrice de contiguïté comme entrée dans un graphique donné

L'entrée est définie avec quelques nombres et à l'aide d'une boucle for, elle parcourra la matrice de contiguïté et renverra le parcours DFS.

Algorithme

Étape 1 : Le programme définit d'abord une constante "MAX" pour représenter le nombre maximum de nœuds dans le graphique donné, et initialise un tableau nommé "visité" pour savoir si un nœud spécifique a été visité pendant le parcours.

Étape 2 : La fonction "dfs()" prend une matrice de contiguïté carrée comme paramètre, "adjMatrix" représentant notre graphique, le nombre total de sommets est "vCount" et le sommet de départ est "start". Cette fonction effectue une recherche récursive en profondeur d'abord du graphe donné.

Étape 3 : Dans la fonction "dfs()", nous marquons chaque sommet actuellement traité comme "visité" en utilisant l'index dans le tableau booléen "visité[]" et l'imprimons en conséquence.

Étape 4 : La boucle à l'intérieur de "dfs()" parcourt récursivement tous les voisins non visités du nœud actuel jusqu'à ce qu'il soit impossible d'y connecter un sommet.

Étape 5 : Dans main(), nous utilisons une boucle imbriquée pour lire les entrées de l'utilisateur, telles que le nombre de sommets de "vCount" et leurs connexions correspondantes dans la matrice de contiguïté.

Étape 6 : Nous demandons ensuite à l'utilisateur le sommet de départ souhaité, puis initialisons chaque élément du tableau "visité[]" à zéro (puisqu'aucun nœud n'a encore été visité).

Étape 7 : Enfin, le programme appelle la fonction "dfs()" avec les paramètres appropriés pour démarrer le parcours de recherche en profondeur d'abord et imprime le chemin de parcours DFS.

Exemple

//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;
}

Sortie

DFS Traversal: 2 1

Conclusion

En utilisant la matrice de contiguïté comme représentation du graphique, nous pouvons effectuer efficacement des DFS sur des ensembles de données volumineux ou complexes. Dans cet article, nous expliquons cela en détail et proposons un programme C qui implémente un parcours de recherche en profondeur en utilisant une représentation basée sur une matrice de contiguïté. La recherche en profondeur est un algorithme puissant pour explorer et analyser les structures graphiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!