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

Trigonomitry, Ask if tanA+sinA=m and m^2-n^2=4 rute mn show that tanA-sinA=...

Ask if tanA+sinA=m and m^2-n^2=4 rute mn show that tanA-sinA=n

Rational numbers, Although the set of integers caters to a larger aud...

Although the set of integers caters to a larger audience, it is inadequate. This inadequacy has led to the formulation of Rational numbers. Rational numbers are of

Problems with applying algorithms , PROBLEMS WITH APPLYING ALGORITHMS :  F...

PROBLEMS WITH APPLYING ALGORITHMS :  From your experience, you would agree that children are expected to mechanically apply the algorithms for adding or subtracting numbers, regar

Using a number strip substract , Another aid that can help children pract...

Another aid that can help children practise subtraction is the number strip. TGS can be used to improve their ability to count backwards. For example, subtracting 4 from 9 means

Trigonometry, important trigonometric formulas for class 10th CBSC board

important trigonometric formulas for class 10th CBSC board

MATH HELP: URGENT, the andersons are buying a new home and need to fence th...

the andersons are buying a new home and need to fence their yard. the yard is 40 ft by 80 ft. each fencing section is 8ft. how many sections will they need?how many posts will they

Numerical analysis and computer techniques, write a fortan programme to gen...

write a fortan programme to generate prime number between 1 to 100

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