Cet article montre la procédure pour implémenter le DFS pour un arbre ou un graphique fourni.
Comment implémenter Depth First Search ou DFS pour un graphe en Java ?
Le DFS est principalement utilisé pour rechercher un graphe en visitant chaque branche/sommet exactement une fois. Il peut détecter ou identifier des cycles dans un graphique qui aide à prévenir les blocages. Il peut être utilisé pour résoudre des énigmes ou des problèmes de labyrinthe. Le DFS peut être implémenté/utilisé dans les algorithmes de graphes, l'exploration Web et la conception de compilateurs.
Pour une explication, visitez le code ci-dessous de Depth First Search ou DFS :
classe Graphique {
privé Liste liée addNode [ ] ;
privé booléen Traversé [ ] ;
Graphique ( entier sommets ) {
addNode = nouveau Liste liée [ sommets ] ;
Traversé = nouveau booléen [ sommets ] ;
pour ( entier je = 0 ; je < sommets ; je ++ )
addNode [ je ] = nouveau Liste liée ( ) ;
}
annuler addEdge ( entier src, entier commencer ) {
addNode [ src ] . ajouter ( commencer ) ;
}
Description du code ci-dessus :
- Tout d'abord, la classe nommée ' Graphique ' est créé. A l'intérieur, déclare un ' Liste liée ' nommé ' addNode[] ' et un tableau de type booléen nommé ' Traversé[] ”.
- Ensuite, passez les sommets pour le constructeur du ' Graphique ” classe en paramètre.
- Après cela, le « pour ” boucle est créée pour se déplacer à travers chaque nœud de la branche sélectionnée.
- Au final, le type vide ' ajouterEdge() ” est utilisé pour ajouter des arêtes entre les sommets. Cette fonction prend deux paramètres : la source du sommet ' src ' et le sommet de destination ' commencer ”.
Après la création d'un graphe, ajoutons maintenant le code de recherche en profondeur ou DFS pour le graphe créé ci-dessus :
annuler DFS ( entier sommet ) {
Traversé [ sommet ] = vrai ;
Système . dehors . imprimer ( sommet + ' ' ) ;
Itérateur ce = addNode [ sommet ] . itérateur de liste ( ) ;
alors que ( ce. aSuivant ( ) ) {
entier adj. = ce. suivant ( ) ;
si ( ! Traversé [ adj. ] )
DFS ( adj. ) ;
}
}
Dans le bloc de code ci-dessus :
- Premièrement la ' SDF() ' la fonction est créée qui obtient ' sommet ” comme paramètre. Ce sommet est marqué comme visité.
- Ensuite, imprimez le sommet visité en utilisant le ' out.print() ' méthode.
- Ensuite, créez une instance de ' Itérateur ” qui itère sur les sommets adjacents du sommet actuel.
- Si le sommet n'est pas visité, alors il passe ce sommet au ' SDF() ' fonction.
Maintenant, créons un ' principal() ' partie fonction pour créer le graphique, puis appliquer DFS à cela :
public statique annuler principal ( Chaîne arguments [ ] ) {
Graphique k = nouveau Graphique ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
Système . dehors . println ( 'Ce qui suit est la première traversée en profondeur' ) ;
k. DFS ( 1 ) ;
}
}
Explication du code ci-dessus :
- Tout d'abord, créez un objet ' k ' pour le ' Graphique() ' méthode.
- Ensuite, le « ajouterEdge() ” est utilisée pour ajouter des arêtes entre plusieurs sommets. Cela crée la structure de notre graphique.
- À la fin, passez n'importe quelle valeur de sommet comme argument au déjà créé ' SDF() ' fonction. Pour trouver ce chemin de sommet à partir de la racine, utilisez un algorithme de recherche en profondeur d'abord. Par exemple, une valeur de ' 1 » est passé au « SDF() ' fonction.
Après la fin de la phase de compilation :
La sortie montre que la recherche en profondeur d'abord a été implémentée avec succès.
Conclusion
Depth First Search est un algorithme de parcours de graphe qui constitue la base de nombreux algorithmes de graphe, tels que la recherche du chemin le plus court, les arbres couvrants et l'analyse de la connectivité. Il commence à partir du nœud racine, puis se déplace aussi profondément que possible jusqu'au nœud de sortie ou au dernier nœud de cette branche avant de revenir en arrière. Cet article a démontré la procédure pour implémenter la recherche en profondeur d'abord ou DFS pour un graphique en Java.