Skip to content

Wa4.

Statement

Develop an implementation of Prim’s algorithms that determines the MST (Minimum Spanning Tree) of the graph from the Unit 2 assignment that we developed the data structure for.

Graph

For this assignment, develop an implementation using Java in the Cloud9 environment (or your own Java IDE) that:

  • First, implement the graph in a data structure.
  • Provide the algorithm that can determine the Minimum spanning tree within this graph in terms of cost.
    • The cost will be the sum of the lengths of the edges that must be traversed.
    • The cost of each edge is represented by the number on the edge.
    • For example the cost of edge 1,3 is 4 and the cost of edge 6,7 is 8.
  • Your algorithm must output the total cost of spanning the tree as determined by your implementation of Prim’s algorithm.
  • The algorithm must produce output which is the total cost of the path.

Assessment:

You will have ONE WEEK to complete this assignment. It will be due the end of this unit. You will be graded on the following:

  • Was a java implementation of a minimum spanning tree algorithm provided? (Yes/No)
  • Is the code documented to give the reader an idea of what the author is trying to do within the code? (Scale of 1-4 where 1 is no comments and 4 is comprehensive comments)
  • Does the java algorithm execute in the Java IDE environment (yes/no)
  • When executed does the algorithm produce output indicating the total cost of spanning the tree? (yes/no)
  • Does the cost reported by the algorithm match the cost provided by the instructor? (yes/no)
  • Does the assignment include an asymptotic analysis describing the complexity of the algorithm in terms of Big-O (Big-Θ, or Big-Ω as appropriate)? (Yes/No)