Java/DataStructures/Graphs/KruskalsAlgorithm.java at master · Spiff77/Java · GitHub

History

174 lines (147 loc) · 4.98 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

// Java program for Kruskal's algorithm to find Minimum Spanning Tree

// of a given connected, undirected and weighted graph

import java.util.*;

import java.lang.*;

import java.io.*;

class Graph

{

// A class to represent a graph edge

class Edge implements Comparable<Edge>

{

int src, dest, weight;

// Comparator function used for sorting edges based on

// their weight

public int compareTo(Edge compareEdge)

{

return this.weight-compareEdge.weight;

}

};

// A class to represent a subset for union-find

class subset

{

int parent, rank;

};

int V, E; // V-> no. of vertices & E->no.of edges

Edge edge[]; // collection of all edges

// Creates a graph with V vertices and E edges

Graph(int v, int e)

{

V = v;

E = e;

edge = new Edge[E];

for (int i=0; i<e; ++i)

edge[i] = new Edge();

}

// A utility function to find set of an element i

// (uses path compression technique)

int find(subset subsets[], int i)

{

// find root and make root as parent of i (path compression)

if (subsets[i].parent != i)

subsets[i].parent = find(subsets, subsets[i].parent);

return subsets[i].parent;

}

// A function that does union of two sets of x and y

// (uses union by rank)

void Union(subset subsets[], int x, int y)

{

int xroot = find(subsets, x);

int yroot = find(subsets, y);

// Attach smaller rank tree under root of high rank tree

// (Union by Rank)

if (subsets[xroot].rank < subsets[yroot].rank)

subsets[xroot].parent = yroot;

else if (subsets[xroot].rank > subsets[yroot].rank)

subsets[yroot].parent = xroot;

// If ranks are same, then make one as root and increment

// its rank by one

else

{

subsets[yroot].parent = xroot;

subsets[xroot].rank++;

}

// The main function to construct MST using Kruskal's algorithm

void KruskalMST()

{

Edge result[] = new Edge[V]; // Tnis will store the resultant MST

int e = 0; // An index variable, used for result[]

int i = 0; // An index variable, used for sorted edges

for (i=0; i<V; ++i)

result[i] = new Edge();

// Step 1: Sort all the edges in non-decreasing order of their

// weight. If we are not allowed to change the given graph, we

// can create a copy of array of edges

Arrays.sort(edge);

// Allocate memory for creating V ssubsets

subset subsets[] = new subset[V];

for(i=0; i<V; ++i)

subsets[i]=new subset();

// Create V subsets with single elements

for (int v = 0; v < V; ++v)

{

subsets[v].parent = v;

subsets[v].rank = 0;

}

i = 0; // Index used to pick next edge

// Number of edges to be taken is equal to V-1

while (e < V - 1)

{

// Step 2: Pick the smallest edge. And increment the index

// for next iteration

Edge next_edge = new Edge();

next_edge = edge[i++];

int x = find(subsets, next_edge.src);

int y = find(subsets, next_edge.dest);

// If including this edge does't cause cycle, include it

// in result and increment the index of result for next edge

if (x != y)

{

result[e++] = next_edge;

Union(subsets, x, y);

}

// Else discard the next_edge

}

// print the contents of result[] to display the built MST

System.out.println("Following are the edges in the constructed MST");

for (i = 0; i < e; ++i)

System.out.println(result[i].src+" -- "+result[i].dest+" == "+

result[i].weight);

}

// Driver Program

public static void main (String[] args)

{

/* Let us create following weighted graph

0--------1

| \ |

6| 5\ |15

| \ |

2--------3

4 */

int V = 4; // Number of vertices in graph

int E = 5; // Number of edges in graph

Graph graph = new Graph(V, E);

// add edge 0-1

graph.edge[0].src = 0;

graph.edge[0].dest = 1;

graph.edge[0].weight = 10;

// add edge 0-2

graph.edge[1].src = 0;

graph.edge[1].dest = 2;

graph.edge[1].weight = 6;

// add edge 0-3

graph.edge[2].src = 0;

graph.edge[2].dest = 3;

graph.edge[2].weight = 5;

// add edge 1-3

graph.edge[3].src = 1;

graph.edge[3].dest = 3;

graph.edge[3].weight = 15;

// add edge 2-3

graph.edge[4].src = 2;

graph.edge[4].dest = 3;

graph.edge[4].weight = 4;

graph.KruskalMST();

}

Java/DataStructures/Graphs/KruskalsAlgorithm.java at master · Spiff77/Java · GitHub

Expand file tree

Breadcrumbs

KruskalsAlgorithm.java

Latest commit

History

Breadcrumbs

KruskalsAlgorithm.java

File metadata and controls