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

Subtraction of 01000-01001 using 2's complement method, Subtraction of 0100...

Subtraction of 01000-01001 using 2's complement method. Ans. Firstly 1's complement of 01001 is 10110 and 2's complement is 10110+ 1 =10111. Thus   01000 =  01000 - 01001

Process of world wide web, Q. Process of World Wide Web? When you type ...

Q. Process of World Wide Web? When you type a URL in a web browser, this is what happens: 1. If URL contains a domain name, browser first connects to a domain name server an

Traditional schema model, (a) Why did SAP introduce the extended star schem...

(a) Why did SAP introduce the extended star schema? Explain why it is reported to be better than the traditional schema model? (b) What is the difference between a dimension use

What do you mean by supercomputers, Q. What do you mean by Supercomputers? ...

Q. What do you mean by Supercomputers? The upper end of state of art mainframe machine is supercomputers. These are among the fastest machines in terms of processing speed and

Physics, what is fresnel''s biprism?how it is used to determine wavelength ...

what is fresnel''s biprism?how it is used to determine wavelength of monochromatic source of light

Explain busy tone in strowger telephony, Explain Busy tone in strowger tele...

Explain Busy tone in strowger telephony. Busy tone pattern is demonstrated in figure. This is a bursty 400 Hz signal with silence era in between. The burst and silence durati

Make your simulation run faster, Ameliorating the mechanical delays of seek...

Ameliorating the mechanical delays of seeks and rottion are usually regardeed as major aspects of device drivers for disks. The simplest way for a disk device driver to service dis

Explain about candidate check, The process which is underlined throughout t...

The process which is underlined throughout the check of base data is called as candidate check. When performing candidate check performance varies either towards the positive side

What is the difference among character and block devices, a. What is the di...

a. What is the difference among character and block devices? b. Discuss the method to make a Kernel Driver for the PC Speaker. c. Explain the socket structure with the help o

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