0
$\begingroup$

I'm new to DFS algorithm and I'm trying to figure it out.

The main concepts I get from it is that you have a stack of nodes, and they have a value, and can contain children-nodes (Even called branches or leaves) that can contains nodes with values.

So let's say that I have a Tree containing 15 nodes like this.

enter image description here

I would understand that the algorithm goes A-N-O-B-D-J-L-M-K-C-E-F-H-G-I, If you were to go in alphabetic order.

My confusion is this how to put this algorithm into practice (such as coding it). How should I see this tree like (Array, List?)

And if some of the children are connected to each other can it still be a DFS algorithm? enter image description here

$\endgroup$

closed as unclear what you're asking by Evil, David Richerby, Juho, Rick Decker, Tom van der Zanden Feb 22 '17 at 11:11

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ I don't understand what you're asking. DFS is a well-defined algorithm that works perfectly well when the graph isn't a tree. And, although implementation questions are off-topic, here, you'd implement the tree/graph using any appropriate data structure. $\endgroup$ – David Richerby Feb 11 '17 at 10:38
  • $\begingroup$ @DavidRicherby Yes I can understand now to why my question is confusing. In this case I was asking in how I should think regarding implementing DFS to code. How should I implement the tree structure in the best-case scenario. $\endgroup$ – Bojje Feb 11 '17 at 19:16
1
$\begingroup$

The first thing you need to do is pick a data structure - i.e a representation for your node graph. For this I suggest you pick up any undergraduate-level book on data structures and read it carefully, and choose something appropriate. For example, given the tree above, I would represent each node with a record containing whatever data is to be stored in that node (e.g the name - A, B, etc) plus a list of (pointers to) child nodes. E.g your root would have the list {A, B, C}, node A would have the list {N}, node J would have the list {K, L, M}, and so on. Each childless node ('leaf') would have an empty list.

Then you code your DFS procedure, which you may find easier to do if you use recursion to process children (although there are ways to make this non-recursive if you insist). Regardless of implementation, the core behavior of DFS is: To process each node, you must do something with the node, then scan the list of children and process each child -and its entire subtree- before processing the next child. You can get different effects according to whether you process each node before its children, or after [if each node has at most two children AND explicitly distinguishes 'left' child from 'right' child, then there is also the option of processing each node -between- left and right].

And yes, you can still perform DFS if there are cross-connections. The key new thing to do here is to keep track of whether the node you are about to process has already been processed; generally what you will want to do in that case is skip that node and go back up to the parent. This is particularly true if 'children' really means 'neighbors', so the edges between nodes aren't directed; then you really need to avoid running in cycles.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.