Algorithme DFS en Java

L'algorithme DFS est un algorithme de traversée qui est défini comme un algorithme de recherche abrégé en recherche en profondeur d'abord, également connu sous le nom d'algorithme de graphe car il recherche dans la structure arborescente qui ressemble à une structure de graphe et part donc du racine et traverse avec le graphique ci-dessous avec différentes branches. En général, l'algorithme DFS en Java est défini comme un algorithme de traversée qui traverse une structure arborescente ou graphique qui commence à partir du nœud racine au point initial et va en profondeur avec chaque branche jusqu'à ce qu'il atteigne le dernier nœud de toute dernière branche. comme recherche en profondeur d'abord et cela fournit 3 méthodes différentes de DFS telles que les recherches traversantes de précommande, d'ordre et de post-commande.

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Algorithme :

DFS est un algorithme uniforme qui aboutit à des solutions non optimales, et l'algorithme DFS fonctionne comme suit :

Étape 1 : Commencez par le nœud racine d'un graphique ou d'un arbre donné.

Étape 2 : Considérez maintenant le nœud racine comme premier nœud du graphique et placez ce nœud en haut de la pile ou de la liste.

Étape 3 : Recherchez maintenant les nœuds adjacents du nœud racine, qui était le premier nœud, et ajoutez ces nœuds adjacents à l'autre liste de nœuds adjacents.

Étape 4 : Continuez ensuite à ajouter les nœuds adjacents de chaque nœud dans la pile ou la liste après le nœud racine.

Étape 5 : Continuez les étapes 3 à 4 jusqu'à ce que vous atteigniez le nœud de fin de la dernière branche dans le graphique ou que la liste des nœuds adjacents devienne vide.

Par conséquent, l'algorithme DFS en Java est l'un des algorithmes de recherche traversante qui recherchent en profondeur jusqu'au nœud final à partir du nœud initial. Cependant, il est parfois déroutant de parcourir le graphique, que ce soit par une branche gauche ou une branche droite ; pour résoudre ce problème, il existe 3 types différents de précommande, d'ordre et de post-ordre DFS pour parcourir l'arborescence selon l'ordre spécifié.

Comment fonctionne l'algorithme DFS avec les exemples ?

En Java, l'algorithme DFS fonctionne selon l'algorithme décrit ci-dessus. L'algorithme DFS pour graphe non orienté commencera à partir du nœud racine en plaçant d'abord ce nœud racine dans la pile qui peut être considérée comme la pile visitée qui contient les nœuds visités, puis placera tous les nœuds adjacents du nœud racine dans cette pile. pile visitée où le nœud racine est présent. Parcourez ensuite le graphique, puis trouvez un nœud adjacent au nœud adjacent de chaque racine et continuez jusqu'au dernier nœud du graphique et parcourez ces nœuds en plaçant tous les nœuds dans une autre pile. Ainsi, après avoir terminé la recherche, la pile visitée s'affiche, ce qui donne les nœuds qui ont été parcourus à travers le graphique.

Exemple n°1

Voyons maintenant un exemple simple d'algorithme DFS qui est implémenté dans le langage de programmation Java sur un graphe déconnecté.

Code :

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class vertex
{
int root, dest;
public vertex(int root, int dest)
{
this.root = root;
this.dest = dest;
}
}
class graphstruc
{
List<List<Integer>> adjList = null;
graphstruc(List<vertex> v, int N)
{
adjList = new ArrayList<>();
for (int i = 0; i < N; i++) {
adjList.add(new ArrayList<>());
}
for (vertex e: v)
{
int src = e.root;
int dest = e.dest;
adjList.get(src).add(dest);
adjList.get(dest).add(src);
}
}
}
class Main
{
public static void DFS(graphstruc graph, int v, boolean[] d)
{
d[v] = true;
System.out.print(v + " ");
for (int u: graph.adjList.get(v))
{
if (!d[u]) {
DFS(graph, u, d);
}
}
}
public static void main(String[] args)
{
List<vertex> v = Arrays.asList(
new vertex(1, 2), new vertex(1, 7), new vertex(1, 8),
new vertex(2, 3), new vertex(2, 6), new vertex(3, 4),
new vertex(3, 5), new vertex(8, 9), new vertex(8, 12),
new vertex(9, 10), new vertex(9, 11), new vertex(10, 12),
new vertex(10, 13), new vertex(11, 14)
);
final int N = 15;
graphstruc g = new graphstruc(v, N);
boolean[] d = new boolean[N];
System.out.println("Demonstration of Depth First Search algorithm in Java is as follows:");
for (int i = 0; i < N; i++)
{
if (!d[i]) {
DFS(g, i, d);
}
}
}
}

Sortie :

Dans l'exemple ci-dessus, nous définissons d'abord un sommet de classe dans lequel nous déclarerons la racine et le sommet de destination dans le graphe où ce sommet de classe stocke les sommets du graphe. Ensuite, nous définissons la classe graphstruc pour déclarer les sommets adjacents du nœud racine et ajoutons ces nœuds adjacents dans la liste. Nous stockons les sommets adjacents et ajoutons plus tard les sommets adjacents de ces sommets dans la liste. Ensuite, pour effectuer DFS, nous déclarons une classe DFS à travers laquelle nous identifierons le nœud actuel à partir du graphe donné, et nous continuons à identifier les nœuds adjacents de chaque nœud et à ajouter les nœuds de liste adjacents. Enfin, dans la classe principale, nous définirons une liste de sommets du graphique sous forme de tableau avec un nombre total de nœuds, et après avoir appelé la fonction DFS, elle affichera la liste dans la liste de recherche DFS comme indiqué dans la capture d'écran ci-dessus. , qui est la sortie.

Exemple n°2

Voyons maintenant l'implémentation DFS avec différents types d'ordres de traversée tels que la traversée en précommande, en ordre et après commande en Java. Dans ce qui suit, nous verrons l'implémentation des précommandes en Java.

Code :

class vertex
{
int data;
vertex l, r;
public vertex(int k)
{
data = k;
l = r = null;
}
}
class Main
{
public static void preorder(vertex root)
{
if (root == null) {
return;
}
System.out.print(root.data + " ");
preorder(root.l);
preorder(root.r);
}
public static void main(String[] args)
{
vertex root = new vertex(2);
root.l = new vertex(3);
root.r = new vertex(1);
root.l.l = new vertex(6);
root.r.l = new vertex(4);
root.r.r = new vertex(5);
root.r.l.l = new vertex(8);
root.r.l.r = new vertex(7);
preorder(root);
}
}

Sortie :

L'exemple ci-dessus est également similaire à l'exemple précédent où ici la seule différence est que nous définissons les ordres de parcours dans l'algorithme DFS. En cela, nous définissons uniquement l'ordre de parcours de pré-ordre, qui, une fois défini, parcourra le graphe en profondeur en premier dans l'ordre en tant que nœud racine, nœud gauche et nœud droit. Par conséquent, ici, nous avons déclaré le nœud 2 comme nœud racine et le nœud 3 comme nœud gauche et le nœud 6 comme nœud droit, et ainsi de suite. Le résultat est tel qu'indiqué dans la capture d'écran ci-dessus.

Conclusion

Cet article conclut que l'algorithme DFS en Java est un algorithme de traversée pour trouver ou rechercher en profondeur le graphique jusqu'à ce que le dernier nœud soit visité. La complexité temporelle de l'algorithme DFS est généralement représentée en O(E+V), où E pour les arêtes et V pour les sommets du graphe. Il existe de nombreuses applications différentes de l'algorithme DFS basées sur ses ordres de parcours qui sont classés en parcours DFS dans l'ordre, le pré-ordre et le post-ordre à travers le graphique.

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!