SIT221 Data Structures And Algorithms Deakin University AU

In this task, answer all the following questions and complement each answer with a detailed explanation. 

1. Conduct a small research on the minimum spanning tree problem and efficient algorithms to solve it.  You  can find all required details in chapter 14.7 of the course book “Data Structures and Algorithms in Java”. 

Learn how to solve the problem via the two particular solution techniques, Prim‐Jarnik’s and Kruskal’s algorithms, described, respectively, in sections 14.7.1 and 14.7.2 of the book. You may of course explore and refer to any other resources covering this topic. We expect you to grasp the idea and important facts about the problem as well as the runtime complexity, implementation issues, and advantage(s) of each of the two algorithms. As the result of your study, you must be able to explain the both algorithms and how they work. 

2. Solve the following numeric example. For the given undirected (bi‐directed) graph, compute a minimum spanning tree using Prim‐Jarnik’s algorithm. Show the structure of your partial minimum spanning tree after each edge insertion and indicate for each edge whether it is included in the minimum spanning tree.