Apply the following two algorithms to find the minimum spanning tree to the graph in Figure 8.15a. a. Probably the first algorithm for finding the minimum spanning tree was devised in 1926 by Otakar...

Apply the following two algorithms to find the minimum spanning tree to the graph in Figure 8.15a.

a. Probably the first algorithm for finding the minimum spanning tree was devised in 1926 by Otakar Bor˚uvka (pronounced: boh-roof-ka). In this method, we start with |V| one-vertex trees, and for each vertex v, we look for an edge(vw) of minimum weight among all edges outgoing from v and create small trees by including these edges. Then, we look for edges of minimal weight that can connect the resulting trees to larger trees. The process is finished when one tree is created. Here is a pseudocode for this algorithm:

b. Another algorithm was discovered by Vojtech Jarník (pronounced: yar-neek) in 1936 and later rediscovered by Robert Prim. In this method, all of the edges are also initially ordered, but a candidate for inclusion in the spanning tree is an edge that not only does not lead to cycles in the tree, but also is incident to a vertex already in the tree:

                                                                            Figure 8.15a