Skip to content

Latest commit

 

History

History
33 lines (27 loc) · 2.39 KB

README.md

File metadata and controls

33 lines (27 loc) · 2.39 KB
Raw

Kruskal's Algorithm Minimum Spanning Tree (Graph MST)

Java Implementation of Kruskal's Algorithm using disjoing sets
Kruskal's algorithm: Start with T = ∅. Consider edges in ascending order of weight. Insert edge e into T unless doing so would create a cycle.

  • Works on UN-directed graphs
  • Algorithm still works on edges with identical weight
    Edges are sorted by weight first. Depending on the order they are entered into the edge list in the constructor, you may get different Minimum Spanning Trees (but all still optimal solutions)

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)
  • Graph is created as an Edge List
  • Make sure nodeCount is accurate. There's no error checking between nodeCount & the actual edge list
  • DisjointSet nodeSet = new DisjointSet(nodeCount+1); skips the 0th index by creating a Disjoint Set 1 larger than the number of vertices
  • outputMessage is a string that records the steps the algorithm takes. It's printed to the screen & to a file once complete
  • My implementation has early termination (A Spanning Tree of a graph has N-1 edges so the algorithm stops whenn it has added N-1 Edges) Hence && mstEdges.size()<(nodeCount-1) in my loop
  • The Edge class simply packages an edge's weight & 2 vertices together as 1 object

Sources