Je veux implémenter DFS (Depth first search) et BFS en utilisant java.Profondeur de la première recherche en utilisant Java
Est-ce que java a une structure de données arborescente intégrée que je peux utiliser facilement? Ou toute autre chose que je peux utiliser?
En supposant que vous ne voulez pas de doublons dans votre structure, TreeSet est un point de départ assez décent. Vous obtenez DFS gratuitement (itérateur()), et vous pouvez utiliser l'interface NavigableSet pour construire BFS.
Un couple de restrictions à garder à l'esprit: TreeSet applique que les données sous-jacentes sont modélisées comme un arbre binaire et qu'il est comparable. – Adamski
Non, il n'y a pas de structure intégrée. Étant donné que les bibliothèques de base Java ont tout, il est fou il n'y a pas d'équivalent à
Le plus proche est java.util.TreeSet, qui est conçu pour être un ensemble plutôt qu'un arbre (il y a aussi le JTree swing, mais il ne t'aidera pas).
c'est assez facile à créer un type de données Tree - pour une lib, il est difficile de le rendre assez général pour tous les cas d'utilisation, mais toutes les parties nécessaires sont déjà présentes dans java. – Chii
Vous pouvez utiliser DefaultMutableTreeNode pour créer votre structure de données. Il contient les méthodes breadthFirstEnumeration() et depthFirstEnumeration() et vous permet de joindre des données à chaque nœud en appelant setUserObject(Object). Malgré une partie du package javax.swing.tree, il s'agit d'un code "modèle" et n'a donc aucune dépendance directe au code d'interface utilisateur.
Jetez un oeil à http://www.jgrapht.org/ où une bibliothèque de graphe java gratuit est fourni. En utilisant cette bibliothèque, vous pouvez créer toutes sortes de graphiques, et comme l'arbre n'est qu'un sous-ensemble de graphes, vous pouvez également créer des arborescences avec cette bibliothèque. Un DFS (ou BFS) est facile à mettre en œuvre en utilisant cette bibliothèque, ou vous pouvez utiliser les algorithmes fournis par la bibliothèque. Cependant, la mise en œuvre d'un DFS (ou BFS) est un bon exercice.
Bonne chance!
t @ adamski. Merci mec. Je dint savoir que mon votinting aider quelqu'un. frm maintenant je vais – user156073