Apply depth-first-search to find out the spanning tree, Mathematics

Assignment Help:

Apply depth-first-search to find out the spanning tree for the subsequent graph with vertex d as the starting vertex.       

1410_Apply depth-first-search to find out the spanning tree.png

Ans: Let us begin with node'd'. Mark d as visited node. Node'd' comprises two child 'e' and 'f'. After that Visit node 'e' and mark it as visited. Select edge (d, e) and add it to spanning tree T. So, T = {(d, e)}  Now e has e has two children: c and f. Visit c, add (e, c) to T, and mark c as visited. After that visit a and after that b. Mark them visited node and add arcs (c, a) and (c, b) to T. Up to here 

T = {(d, e), (e, c), (c, a), (c, b)}

Now here c has one more child e, which is previously visited, so exit recursion and go up to e that one more unvisited child f. Visit it, mark it as visited and we add (e, f) to T.  f comprise three (3) children: d, g and h. d is visited so leave it. Visit g, and doing the basic work of marking as visited and adding the arc utilized to visit the node in T, we at last get T as 

T = {(d, e), (e, c), (c, a), (c, b), (e, f), (f, g), (g, h), (h, i), (h, k), (k, j)}


Related Discussions:- Apply depth-first-search to find out the spanning tree

Cirlce Division, How can i calculate arc length for dividing a circle into ...

How can i calculate arc length for dividing a circle into 10 parts

Probability, two coins are flipped once.what is the probability of getting ...

two coins are flipped once.what is the probability of getting two tails?

What percent of the figure below is shaded, What percent of the figure belo...

What percent of the figure below is shaded? Break the rectangle into eighths as shown below. The shaded part is 6/8 or 3/4 ; 3/4 is 75%.

Highest common factor (hcf), We know that a factor is a quantity whic...

We know that a factor is a quantity which divides the given quantity without leaving any remainder. Similar to LCM above we can find a highest common factor (HCF)

Unitary method, what is history of Unitary method

what is history of Unitary method

Fractions, how to divide fractions?

how to divide fractions?

Prime number, Prime number A prime number is a number whose only +ve fa...

Prime number A prime number is a number whose only +ve factors are 1 and itself. For instance 2, 3, 5, and 7 are all of the examples of prime numbers.  Examples of numbers whic

Probability of chosen number from 1st 500 divisble by 3or5 , IN THIS WE HAV...

IN THIS WE HAVE TO ADD THE PROBABILITY of 3 and 5  occuring separtely and subtract prob. of 3 and 5 occuring together therefore p=(166+100-33)/500=233/500=0.466

How many ounces of soup does she required, Sharon needs to make 25 half-cup...

Sharon needs to make 25 half-cup servings of soup. How many ounces of soup does she required? One cup is 8 ounces, so half a cup is 4 ounces. Multiply 25 by 4 ounces to find ou

Linear equations in one variable, three prices are to be distributed in a q...

three prices are to be distributed in a quiz contest.The value of the second prize is five sixths the value of the first prize and the value of the third prize is fourfifth that of

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