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?
+1
A:
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.
GaryF
2009-09-16 10:06:01
A couple of restrictions to bear in mind: TreeSet enforces that the underlying data is modelled as a binary tree and that it is comparable.
Adamski
2009-09-16 11:03:20
A:
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).
David Crawshaw
2009-09-16 10:08:48
its pretty easy to crate a Tree data type - for a lib, its hard to make it general enough for all use cases, but all the needed parts are there in java already.
Chii
2009-09-16 10:44:59
+2
A:
You could use DefaultMutableTreeNode to build your data structure. It contains methods breadthFirstEnumeration() and depthFirstEnumeration() and allows you to attach data to each node by calilng setUserObject(Object). Despite part of the javax.swing.tree package this is "model" code and so doesn't have any direct UI code dependencies.
Adamski
2009-09-16 11:02:27
+3
A:
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!
Clean
2009-09-16 11:33:27