使用java进行深度优先搜索
我想使用java实现DFS(深度优先搜索)和BFS。
java 是否有一个我可以轻松使用的内置树数据结构?或者我可以使用任何其他东西吗?
I want to implement DFS (Depth first search) and BFS using java.
Does java have a built in tree data structure that I can use readly? Or any other thing that I can use?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(4)
看一下http://www.jgrapht.org/,其中提供了免费的java图形库。使用此库,您可以创建所有类型的图形,并且由于树只是图形的子集,您也可以使用此库创建树。使用此库可以轻松实现 DFS(或 BFS),或者您也可以使用该库提供的算法。然而,实现 DFS(或 BFS)是一个很好的练习。
祝你好运!
Take a look at http://www.jgrapht.org/ where a free java graph library is provided. Using this library you can create all kind of graphs, and since tree's is just a subset of graphs you can also create tree's with this library. A DFS (or BFS) is easy to implement using this library, or you can use the algorithms provided by the library. However, implementing a DFS (or BFS) is a good exercise.
Good Luck!
您可以使用 DefaultMutableTreeNode 来构建你的数据结构。它包含方法
breadthFirstEnumeration()
和depthFirstEnumeration()
,并允许您通过调用setUserObject(Object)
将数据附加到每个节点。尽管它是 javax.swing.tree 包的一部分,但它是“模型”代码,因此没有任何直接的 UI 代码依赖项。You could use DefaultMutableTreeNode to build your data structure. It contains methods
breadthFirstEnumeration()
anddepthFirstEnumeration()
and allows you to attach data to each node by calilngsetUserObject(Object)
. Despite part of thejavax.swing.tree
package this is "model" code and so doesn't have any direct UI code dependencies.假设您不想在结构中出现重复项,那么 TreeSet 是一个足够好的起点。您可以免费获得 DFS(iterator()),并且可以使用 NavigableSet 接口来构建 BFS。
Assuming you don't want duplicates in your structure, then TreeSet is a decent enough starting point. You get DFS for free (iterator()), and you can make use of the NavigableSet interface to build BFS.
不,没有内置结构。鉴于 Java 基础库拥有一切,没有相当于 Data.Tree
最接近的是java.util.TreeSet,它被设计为Set而不是Tree(还有swing JTree,但它不会帮助你)。
No, there is no built-in structure. Given the Java base libraries have everything, it is crazy there is no equivalent to Data.Tree
The closest is java.util.TreeSet, which is designed to be a Set rather than a Tree (there's also the swing JTree, but it won't help you).