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

Logic-based expert systems - , Logic-based Expert Systems - Artificial inte...

Logic-based Expert Systems - Artificial intelligence: Expert systems are agents which are programmed to make decisions about real world situations. They are put together by uti

Calculate width and height of the grid, Given a cell, we must determine its...

Given a cell, we must determine its neighbouring cells i.e. those with which it shares a wall. The cells with an x are the neighbours of the cell c. Write the function getneighbour

Interface constructors, Describe a interface 'Human' with methods as walk' ...

Describe a interface 'Human' with methods as walk' and 'speak'. Describe a class 'User' implementing 'Human'. Describe a work() method in User class.Add a class 'Person' also execu

What is elapsed time of computer system, What is elapsed time of computer s...

What is elapsed time of computer system? The total time to implement the total program is known as elapsed time. It is affected by the speed of the processor, the disk and the

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

How music is produced and generated - cad, How music is produced and genera...

How music is produced and generated - CAD Computer software and hardware advances have changed how music is produced and generated. Some of the primary reasons for this have

Typicality of virtual addresses, The typicality of virtual addresses is tha...

The typicality of virtual addresses is that: They are longer than physical addresses because total addressed memory in virtual memory is more than actual physical memory.

Differences b/w user level and kernel supported threads, What are the diffe...

What are the differences between user level threads and kernel supported threads? A thread, sometimes termed a lightweight process (LWP), is a fundamental unit of CPU utilizati

Addressability of memory - computer architecture, Addressability: Loc...

Addressability: Location-addressable Each alone accessible unit of information in storage is chosen with its numerical memory address. In the modern computers, location-a

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