Skip to content

SleekPanther/kruskals-algorithm-minimum-spanning-tree-mst

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

4 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Kruskal's Algorithm Minimum Spanning Tree (Graph MST)

Java Implementation of Kruskal's Algorithm using disjoing sets

##PseudoCode kruskal-pseudocode

##Detailed Implementation kruskal-detailed-implementation

##Code Notes Current code runs on this sample graph graph It produces this Minimum Spanning Tree mst

  • Requires distinct nodes named with consecutive integers. If they really do have the same "name", convert them to integer ID's to use this algorithm
    Example graph has 8 nodes numbered 1-8 (array ignores the 0th index)
  • You must hardcode the graph structure in constructor as a list of edges
  • Make sure nodeCount is accurate. There's no error checking between nodeCount & the actual edge list
  • My implementation has early termination. If a graph has N nodes the MST has (N-1) edges
    Hence && mstEdges.size()<(nodeCount-1) in my loop

####Sources