Prim's Algorithm using HeapImpl

Synopsis

Implementation of Prim's Algorithm using Heap data structure (coded in arrays from scratch) that can compute the overall spanning weight.

Software Specifications

• JDK 1.8
• JRE 1.8

Hardware Specifications

• i7 3rd Generation Quad Core Processor
• 16 Gb of RAM

Input data format requirements

n

v1 v2 w1,2

...

v3 v9 w3,9

...

How to run ?

Create a new folder in your system. Download this repository's files into that folder. Make sure the following commands are running from your terminal/command-line, Windows

javac -version
java -version

Ubuntu Linux

javac --version
java --version

Compile the TestHeapMain.java file using the below command

javac TestHeapMain.java

Compile the PrimsAlgoMain.java file using the below command

javac PrimsAlgoMain.java

3 class files gets generated, now run the main file with runtime arguments

java PrimsAlgoMain input8.txt

Average Running time to Estimate Time Complexity (Number of vertices vs Time in milliseconds)

References

1. Kleinberg, J., & Tardos, E. (2005). Algorithm design. Boston: Pearson/Addison-Wesley.
2. Lecture Slides - http://www.cs.princeton.edu/~wayne/kleinberg-tardos/

Graph Plot Credits

Venkadesan Gandhirajan

Email : [email protected]

Copyright © 2015 Vaikunth Sridharan