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

Ida* search - artificial intelligence, IDA* Search - artificial intelligenc...

IDA* Search - artificial intelligence: A* search is a sophisticated and successful search strategy. In fact, a problem with A* search is that it must keep all states in its me

Breadth first search, Breadth First Search: Given a set of operators o...

Breadth First Search: Given a set of operators o1, ..., on in a breadth first search, every time a new state is reached, an action for each operator on  s  is added to the bot

Stepwise refinement of the program, What do you understand by stepwise refi...

What do you understand by stepwise refinement of the program? The method of "Stepwise refinement" means to take an object and move it from a general perspective to a exact leve

Which technique allows executing a program not in memory, A set of techniqu...

A set of techniques that allow executing a program which is not entirely in memory is called ? Ans. virtual memory which allows executing a program that is not entirely in me

Define the message queues, The message queue provides the information about...

The message queue provides the information about sizes of queues under utilization of various processors. It points to size of every processor incoming message queue that would be

Indian standard code for information interchange, The ISCII is an 8-bit cod...

The ISCII is an 8-bit code which contains standard ASCII values till 127 from 128-225 it contains characters necessary in ten Brahmi-based Indian scripts. It is defined in IS 13194

Conversion of data types done between abap/4 & db layer, How is conversion ...

How is conversion of data types done between ABAP/4 & DB layer? Conversion among ABAP/4 data types and the database layer is complete within the database interface

Uniform memory access model (uma), Uniform Memory Access Model (UMA) In...

Uniform Memory Access Model (UMA) In this model, the main memory is uniformly shared by all processors in multiprocessor systems and each processor has equal access time to sha

DBMS, DEFINE FILE ORGANISATION

DEFINE FILE ORGANISATION

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