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 missing offset, Q. What is Missing offset? The xxxx in machine ...

Q. What is Missing offset? The xxxx in machine language for instruction at line 0010 is there since the assembler doesn't know DATA segment location which will be determined at

Methodology and data collection in e-commerce, Introduction Our resear...

Introduction Our research methodology requires gathering relevant data from the specified documents in order to analyze the material and arrive at more complete understanding

Find the conversion time & conversion rate of A/D converter, Find the conve...

Find the conversion time of a Successive Approximation A/D converter which uses a 2 MHz clock and a 5-bit binary ladder containing 8V reference. What is the Conversion Rate? An

Explain in detail companding, Explain in detail companding. Companding...

Explain in detail companding. Companding: It is the process of compressing and expanding. This includes compressing the signal at the transmitter and expanding this at the re

Write a program that will solve a puzzle, You will write a program that wil...

You will write a program that will solve a version of the common newspaper puzzle \word search." In the puzzle you are given a grid lled with characters and a list of words to nd

Explain processing of an interrupt, Q. Explain Processing of an Interrupt? ...

Q. Explain Processing of an Interrupt? The interrupt is processed as: Step 1: Number field in INT instruction is multiplied by 4 to get its entry in interrupt vector table.

Simplify the expression by using karnaugh map, Simplify   the   following  ...

Simplify   the   following   expression   into   sum   of   products   using   Karnaugh   map F(A, B, C, D) = ∑ (1,3,4,5,6,7,9,12,13) Ans. Simplification of the giv

Write an xpath expression, Question: (a) Explain the five different t...

Question: (a) Explain the five different types of element content defined by DTDs. (b) Compare XML schema's against DTDs. (c) Consider the following two element decla

How do we save a selected sub-image to a file in gimp, Use "Edit->Paste As-...

Use "Edit->Paste As->New Image" menu command or press Ctrl-Shift-V key combination, then save newly created image.The script-fu-selection-to image can also be used to cut a selecti

Multidimensional arrays defined in terms of an array, How is multidimension...

How is multidimensional arrays defined in terms of an array of pointer? An element in a multidimensional array like two-dimensional array can be shown by pointer expression as

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