Skip to content

Kruskal Implemented #1352

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 3 commits into from
Jul 7, 2020
Merged

Kruskal Implemented #1352

Changes from 1 commit
Commits
Show all changes
3 commits
Select commit Hold shift + click to select a range
dd06589
Kruskal Algorithm Implemented
MarcosVillacanas Jun 17, 2020
bf0fdd7
Context added
MarcosVillacanas Jul 6, 2020
174b43c
link-Removed
MarcosVillacanas Jul 6, 2020
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Next Next commit
Kruskal Algorithm Implemented
  • Loading branch information
@MarcosVillacanas
MarcosVillacanas committed Jun 17, 2020
commit dd06589833e0117f3db2c196b82c0059c8107bba
94 changes: 94 additions & 0 deletions DataStructures/Graphs/Kruskal.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,94 @@
package Kruskal;
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

The repository is for educational purpose and therefore it will be great if you could add a description of your problem.


import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;

public class Kruskal {

//Complexity: O(E log V) time, where E is the number of edges in the graph and V is the number of vertices

private static class Edge{
private int from;
private int to;
private int weight;

public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
}

private static void addEdge (HashSet<Edge>[] graph, int from, int to, int weight) {
graph[from].add(new Edge(from, to, weight));
}

public static void main(String[] args) {
HashSet<Edge>[] graph = new HashSet[7];
for (int i = 0; i < graph.length; i++) {
graph[i] = new HashSet<>();
}
addEdge(graph,0, 1, 2);
addEdge(graph,0, 2, 3);
addEdge(graph,0, 3, 3);
addEdge(graph,1, 2, 4);
addEdge(graph,2, 3, 5);
addEdge(graph,1, 4, 3);
addEdge(graph,2, 4, 1);
addEdge(graph,3, 5, 7);
addEdge(graph,4, 5, 8);
addEdge(graph,5, 6, 9);

System.out.println("Initial Graph: ");
for (int i = 0; i < graph.length; i++) {
for (Edge edge: graph[i]) {
System.out.println(i + " <-- weight " + edge.weight + " --> " + edge.to);
}
}

Kruskal k = new Kruskal();
HashSet<Edge>[] solGraph = k.kruskal(graph);

System.out.println("\nMinimal Graph: ");
for (int i = 0; i < solGraph.length; i++) {
for (Edge edge: solGraph[i]) {
System.out.println(i + " <-- weight " + edge.weight + " --> " + edge.to);
}
}
}

public HashSet<Edge>[] kruskal (HashSet<Edge>[] graph) {
int nodes = graph.length;
int [] captain = new int [nodes];
//captain of i, stores the set with all the connected nodes to i
HashSet<Integer>[] connectedGroups = new HashSet[nodes];
HashSet<Edge>[] minGraph = new HashSet[nodes];
PriorityQueue<Edge> edges = new PriorityQueue<>((Comparator.comparingInt(edge -> edge.weight)));
for (int i = 0; i < nodes; i++) {
minGraph[i] = new HashSet<>();
connectedGroups[i] = new HashSet<>();
connectedGroups[i].add(i);
captain[i] = i;
edges.addAll(graph[i]);
}
int connectedElements = 0;
//as soon as two sets merge all the elements, the algorithm must stop
while (connectedElements != nodes && !edges.isEmpty()) {
Edge edge = edges.poll();
//This if avoids cycles
if (!connectedGroups[captain[edge.from]].contains(edge.to)
&& !connectedGroups[captain[edge.to]].contains(edge.from)) {
//merge sets of the captains of each point connected by the edge
connectedGroups[captain[edge.from]].addAll(connectedGroups[captain[edge.to]]);
//update captains of the elements merged
connectedGroups[captain[edge.from]].forEach(i -> captain[i] = captain[edge.from]);
//add Edge to minimal graph
addEdge(minGraph, edge.from, edge.to, edge.weight);
//count how many elements have been merged
connectedElements = connectedGroups[captain[edge.from]].size();
}
}
return minGraph;
}
}