GitHub - harmankumar/Prim-Fredman-Tarjan-Fibonacci-Heap: An implementation of Fredman Tarjan Algorithm using Fibonacci Heap to compute the MST in near linear time

harmankumar / Prim-Fredman-Tarjan-Fibonacci-Heap Public

Notifications You must be signed in to change notification settings
Fork 0
Star 1

An implementation of Fredman Tarjan Algorithm using Fibonacci Heap to compute the MST in near linear time

Notifications

Name		Name	Last commit message	Last commit date
Latest commit History 38 Commits
src		src
Automated_Tester.py		Automated_Tester.py
DesignDocument.pdf		DesignDocument.pdf
Fredman-Tarjan_FIbonacciHeap.pdf		Fredman-Tarjan_FIbonacciHeap.pdf
Prim_BinaryHeap.pdf		Prim_BinaryHeap.pdf
README		README
README.txt		README.txt
Random_Graph.cpp		Random_Graph.cpp
Report.pdf		Report.pdf
UFTester.cpp		UFTester.cpp
chaos.py		chaos.py
count.txt		count.txt
fredman-tarjan_fibonacci_heap.cpp		fredman-tarjan_fibonacci_heap.cpp
help.cpp		help.cpp
helper.py		helper.py
order.py		order.py
prim_binary_heap.cpp		prim_binary_heap.cpp
src1.zip		src1.zip
util.h		util.h
util1.h		util1.h

Repository files navigation

This Project Compares the running times of Prims algorithm and Fredman-Tarjan algorithm for computing the MST of graphs.
Prims algorithm uses binary heap as it's base data structure whwreas the fredman-tarjan algorithm uses the fibonacci heap.
In order to implement the algorithms, Fibonacci Heap, Union Find and Binary Heap data structures were implemented. 
The running times of the algorithms were tested on randomly generated graphs, classified as very sparse, sparse and dense.
The number of vertices in the graphs vaaaried between a few hundred and a few million.