Поиск в глубину с использованием Java

Question

Я хочу реализовать DFS (поиск в глубину) и BFS с использованием Java.

Есть ли в java встроенная древовидная структура данных, которую я могу легко использовать? Или что-нибудь еще, что я могу использовать?

Answer 1

Взгляните на http://www.jgrapht.org/, где предоставляется бесплатная библиотека графов Java. Используя эту библиотеку, вы можете создавать все виды графиков, и, поскольку дерево является лишь подмножеством графиков, вы также можете создавать деревья с помощью этой библиотеки. DFS (или BFS) легко реализовать с помощью этой библиотеки, или вы можете использовать алгоритмы, предоставляемые библиотекой. Однако реализация DFS (или BFS) - хорошее упражнение.

Удачи!

Answer 2

Вы можете использовать DefaultMutableTreeNode для построения структуры данных. Он содержит методы breadthFirstEnumeration() и depthFirstEnumeration() и позволяет вам присоединять данные к каждому узлу с помощью calilng setUserObject(Object). Несмотря на часть пакета javax.swing.tree, это код модели, поэтому он не имеет прямых зависимостей кода пользовательского интерфейса.

Answer 3

Если вы не хотите дубликатов в своей структуре, то TreeSet является достаточно приличной отправной точкой. Вы получаете DFS бесплатно (iterator ()) и можете использовать интерфейс NavigableSet для создания BFS.

Answer 4

Нет, встроенной структуры нет. Учитывая, что базовые библиотеки Java имеют все, это безумие, что нет эквивалента Data.Tree

Самым близким является java.util.TreeSet, который разработан как набор, а не как дерево (есть также свинг JTree, но он вам не поможет).