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

What is replacement policy in cache, Q.What is Replacement Policy in cache?...

Q.What is Replacement Policy in cache? When a new block has to be fetched in cache the other block may have to be replaced to make room for new block. Replacement policy determ

What is CRC, In a frame transmission, CRC stands for? CRC stands for Cy...

In a frame transmission, CRC stands for? CRC stands for Cyclic Redundancy Check, in a frame transmission.

What is block started by symbol, What is BSS(Block Started by Symbol)? ...

What is BSS(Block Started by Symbol)? A data showing at the machine level, that has initial values when a program begins and tells about how much space the kernel assigns for t

Objectives of parallel computing, Objectives of Parallel Computing Aft...

Objectives of Parallel Computing After reading this topic, you would be able to: Tell historical details of parallel computing; Explain the fundamental ideas of dis

Unix for multiprocessor system, The UNIX operating system for a multiproces...

The UNIX operating system for a multiprocessor system has a number of extra features as compared to normal UNIX operating system.  Let's first consider the design objectives of mul

What is a file, What is a file? A file is a named collection of relate...

What is a file? A file is a named collection of related information that is recorded on secondary storage. A file having either programs or data. A file has sure "structure" b

Explain about olap, OLAP is called as online analytical processing which gi...

OLAP is called as online analytical processing which gives answers to queries which are multi dimensional in nature. It composes relational reporting and data mining for giving sol

Risks by financial service provider perspective, What are the risks by fina...

What are the risks by financial service provider's perspective in Electronic Payment Systems? Through the financial service provider's perspective: • Stolen service or c

Computer graphics, What is intractive graphics and user dialouge in comput...

What is intractive graphics and user dialouge in computer graphics

Define thread cancellation and target thread, Define thread cancellation & ...

Define thread cancellation & target thread.  The thread cancellation is the task of terminating a thread before it has done. A thread that is to be cancelled is often referred

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