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

Determine the measure of a base angle, The angle calculate of the base angl...

The angle calculate of the base angles of an isosceles triangle are shown by x and the vertex angle is 3x + 10. Determine the measure of a base angle. a. 112° b. 42.5° c.

What is universal set, A non-empty set or group of which all the sets under...

A non-empty set or group of which all the sets under concern are subsets is known as the universal set. In any part of application of set theory, all the sets under concern might l

Fuzzy decisionmaking using minimization of regret, why we use decision maki...

why we use decision making using minimization of regret method in uncertainty?

Solve the form x2 - bx + c, The form x2 - bx + c ? This tutorial will ...

The form x2 - bx + c ? This tutorial will help you factor quadratics that look something like this: x 2 -7x + 12 (No leading coefficient; negative middle coefficient; p

Calcukus, A drug has a decay rate of k = - ¼ ln(¾) / hr. How soon after an ...

A drug has a decay rate of k = - ¼ ln(¾) / hr. How soon after an initial dose of 1600 mg will the drug reach its minimum therapeutic value of 900 mg in the body?

Trigonometry, In the riangle ABC the AB=12 cm,AC=28 cm and angle ABC=120 de...

In the riangle ABC the AB=12 cm,AC=28 cm and angle ABC=120 degrees.BC=?

Linear equation, The ratio between the length and breadth of a rectangular ...

The ratio between the length and breadth of a rectangular field is 11:7. The cost of fencing it is Rs. 75,000. Find the dimensions of the field

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