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

Rational Number Application, in the horizontal bar event the u.s.a scored 2...

in the horizontal bar event the u.s.a scored 28.636,gremany scroed 28.7,romnia scored 27.962,and chain scored 28.537 points.which list shows these scored in descending order

Product moment coefficient, Product Moment Coefficient This gives an i...

Product Moment Coefficient This gives an indication of the strength of the linear relationship among two variables. Note that this formula can be rearranged to have di

Example to compute limit, calculates the value of the following limit. ...

calculates the value of the following limit. Solution Now, notice that if we plug in θ =0 which we will get division by zero & so the function doesn't present at this

Randi takes the stairs at work whenever possible instead, Randi takes the s...

Randi takes the stairs at work whenever possible instead of the elevator. She must climb up 51 steps from her office to get to the accounting department. The human resources depa

Shares and dividends, suresh invested rs.1080 in shares of face value rs.50...

suresh invested rs.1080 in shares of face value rs.50 at rs.54.After receiving dividend on them at 8% he sold them at 52.In each of the transaction he paid 2 % brokerage.Hpw much d

Evaluate the perimeter of the plot of land, Evaluate the perimeter of the p...

Evaluate the perimeter of the plot of land. a. 260 m b. 340 m c. 360 m d. 320 m To evaluate the perimeter, we must know the length of all sides. According to the dia

Calenders, on which date of the week does 4th december 2001 falls?

on which date of the week does 4th december 2001 falls?

Calculate the price of the horseracing track, There are five horseracing tr...

There are five horseracing tracks in Kentucky. The Kentucky legislature allows only one track to be open at a time. How does this restriction affect the price the track can charge

Total linear attenuation, Consider the task of identifying a 1 cm thick bre...

Consider the task of identifying a 1 cm thick breast cancer that is embedded inside a 4.2 cm thick fibroglandular breast as depicted in Fig. The cancerous tumor has a cross

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