Difference between depth first and breadth first traversing, Computer Engineering

Assignment Help:

Explain the difference between depth first and breadth first traversing techniques of a graph.  

Depth-first search is dissimilar from Breadth-first search in the following ways: A depth search traversal method goes to the deepest level of the tree first and then works up whereas a breadth-first search looks at all possible paths at the similar depth before it goes to a deeper level. When we come to a dead end in a depth-first search, we back up as little as possible. We try another route from a new vertex-the route on top of our stack. In a breadth-first search, we need to back up as far as possible to search a route originating from the previous vertices. So the stack is not an appropriate structure for searching an early route because it keeps track of things in the order opposite of their occurrence-the new route is on top. To keep track of things in the order in which they happened, we use a FIFO queue. The route at the front of the queue is a route from an previous vertex; the route at the back of the queue is from a later vertex.

 


Related Discussions:- Difference between depth first and breadth first traversing

Qwerty-based keyboards, QWERTY-based keyboards In addition the standard...

QWERTY-based keyboards In addition the standard alphabet keys having QWERTY arrangement, a computer keyboard also comprises the control (alt, Del, Ctrl etc. keys) and function

Problem based on banker''s algorithm, A system contains 10 units of resourc...

A system contains 10 units of resource class Ru. The resource requirements of three user processes P1, P2 and P3 are as follows

Explain load sharing processor configuration of spc, Explain how a centrali...

Explain how a centralized SPC organization works under load sharing operation. Under load sharing operation, an incoming call is allocated randomly or in a predetermined sequen

Write miss policy - cache memories, WRITE MISS POLICY:   Write allo...

WRITE MISS POLICY:   Write allocate   fetch on write   fetch entire block, then write word into block   allocate a new block on each writ   allocate block, but

Explain extended binary coded decimal interchange code, Q. Explain Extended...

Q. Explain Extended Binary Coded Decimal Interchange Code? Extended Binary Coded Decimal Interchange Code (EBCDIC) is a character-encoding format employed by IBM mainframes. It

How many address bits are needed to show a 32 K memory, How many address bi...

How many address bits are required to represent a 32 K memory ? Ans. 32K = 25 x 210 = 215, Hence 15 address bits are needed; Only 16 bits can address this.

The current image in gimp, How do we merge an image from a file to the curr...

How do we merge an image from a file to the current image in GIMP? Ans) Use "File then Open as Layers" menu command or just take the file to a window and drop it there. The file w

Identify the main enhancements brought along by tkip, Question: (a) Id...

Question: (a) Identify the four main enhancements brought along by TKIP on WPA to solve the problems in WEP. (b) The term WarDriving has been frequently used while talking

Explain the term electronic data interchange (edi), Explain the term Electr...

Explain the term Electronic Data Interchange (EDI). Electronic Data Interchange (EDI) may be generally easy to understand as the replacement of paper-based purchase orders alon

Show the conflict in register, Q. Show the conflict in register? All mi...

Q. Show the conflict in register? All micro-operations written on a line are to be executed at same time provided the statements or a group of statements to be implemented toge

Write Your Message!

Captcha
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd