shallow nodes and deeper nodes.

Question

0.00/5 (No votes)

See more:

Hi...
I found that in some tutorial the breadth first search

the shallow nodes are expanded befor deeper nodes.

I am realy confuse what is the meaning of each of them?

Thank you

Posted 18-Dec-11 2:31am

dedoooo

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Manfred Rudolf Bihy · Answer 1 · 2011-12-18T02:56:00

Solution 1

Consider a tree data structure where starting from the root node there are anything from zero to n children for any node in the tree. BFS just visits all the m children of any node before it descends to inspect the next deeper level while DFS always tries to descend to the next level as soon as it finds a node that still has child nodes.

Cheers!

Posted 18-Dec-11 2:56am

Manfred Rudolf Bihy

Updated 18-Dec-11 3:07am

v2

Comments

dedoooo 18-Dec-11 9:16am

Ok but let say we have a tree with 3 nodes , the right child and left child have the same depth from the root , (equals number of edges ,right? so why expand the left child first?

Manfred Rudolf Bihy 18-Dec-11 15:51pm

Left to right or right to left or any other order are all the same regarding BFS & DFS as this only concerns the order of processing the children of a node.

Manfred Rudolf Bihy 18-Dec-11 15:53pm

In implementing a special version of DFS or BFS you are free to choose any direction in child traversal that you fancy or even a non linear traversal would be fine for example choosing the next child node randomly.