10 pts 3 Use Prims algorithm to draw and label a minimum wei

(10 pts) 3. Use Prim\'s algorithm to draw and label a minimum weight Spanning tree for the graph below. As you find the tree, step by step, list the edges and their weights below the graph in the order that you add them to your Spanning tree.

Solution

Step 1:before S={a}

        V \\ S ={b,c,d,e,f,g,h,i,j}

        A={} | lighted edge={a,e}

Step2:after step1{a.e}

V \\ S = {b,c,d,f,g,h,i,j}

       A = {{a,e}} | lighted edge{e,i}

Step3:after step2{{a.e},{e,i}

V \\ S = {b,c,d,f,g,h,j}

       A = {{a,e},{e,i}} | lighted edge{i,c}

Step4:after step3{{a.e},{e,i},{i,c}}

V \\ S = {b,d,f,g,h,i,j}

       A = {{a,e},{e,i},{i,c}} | lighted edge{c,b}

Step5:after step4{{a.e},{e,i},{i,c},{c,b}}

V \\ S = {d,f,g,h,i,j}

       A = {{a,e},{e,i},{i,c},{c,b}} | lighted edge{b,f}

Step:after step4{{a.e},{e,i},{i,c},{c,b}}

V \\ S = {d,f,g,h,i,j}

       A = {{a,e},{e,i},{i,c},{c,b}} | lighted edge{b,f}

so on -----all nodes.{{a,e},{e,i},{i,c},{c,b},{b,f},{f,h},{h,d},{d,j},{j,g}}

finally prim\'s algorithm with minimum waight spening tree:1+2+3+1+4+2+3+1+2=19.