Hi it's a me again! Today we will get into a little more difficult topic of Graphs! I will start out with some basic Theory stuff and Pseudocodes and then we will talk about the 2 main Algorithms called Kruskal and Prim that are used to get a MST out of a Graph! I will again implement all this in Java. So, without further do let's get started!
MST Theory:
A Minimum Spanning Tree is a Tree that contains all Vertices connected with the less-weighted Edges. This Tree contains no circles and the sum of weights is the least possible. So, we use MST's to get a subset out of a Graph.
When adding a Edge to the MST we will have to make sure that no circle is formed. So, how do we make sure that the Edge being added creates no Circle? Well, there are many ways of doing it. The best implementation uses Sets and checks if the Edge connects 2 different Sets. If it does then it can be inserted. But, I won't get into that cause there is plenty of Code for that. You can find this implementation here.
Me myself will use a boolean array that checks if we already have an Edge that goes to a specific Vertex. Everytime we add an Edge we will set the EndingPoint/Vertex index into true. In both algorithms we will also set the StartingVertex to true.
So, why do we have 2 algorithms? Well, the answer is simple. Kruskal gets the least weighted Edge out of a PriorityQueue of all Edges the Graph contains. Prim in the other hand starts from a specific Vertex and adds Edges with the least weight that connect to the Tree we have.
The Pseudocode for Kruskal is:
- Create Priority Queue with all Edges of the Graph in ascending order
- Insert least-weighted Edge to MST checking if doesn't make a circle
- Continue the process until no more Edges are in the Queue
The Pseudocode for Prim is:
- Insert StartingIndex neighbour-Edges into the PriorityQueue in ascending order
- Insert least-weighted Edge to MST cheking if it doesn't make a circle
- Insert neighbours of EndingPoint of Edge inserted
- Continue the process until no more Edges are in the Queue
Graph Implementation:
I will change the Graph implemented last time a lot and will make the Adjacency Lists be PriorityQueues and we also don't have Queue of Integers, but of Edges that will be a new class that describes a Edge!
The Edge looks like this:
public class Edge implements Comparable{ private int startPoint; private int endPoint; private float weight;
public Edge(int startPoint, int endPoint, float weight) { this.startPoint = startPoint; this.endPoint = endPoint; this.weight = weight; }
public int getStartPoint() { return startPoint; }
public int getEndPoint() { return endPoint; }
public float getWeight() { return weight; }
public boolean equals(Edge other) { if (this.startPoint == other.startPoint) { if (this.endPoint == other.endPoint) { return true; } } return false; } public int compareTo(Object o) { Edge other = (Edge) o; return Double.compare(this.weight, other.weight); }
public String toString() { return startPoint + "-" + endPoint + " (" + weight + ")"; }}You can see that a object of type Edge contains the Start and EndPoint and a weight value and a lot of functions. We have getters, a method for checking equality, a method to compare (for PriorityQueue natural ordering, so that the Queue will be in ascending order) and the toString() method for printing.
The Graph changes a little! Even though MST's get performed on an Undirected Graph I will use a Directed Graph to make the changes in the MST more visible! We just have to include some functions that take in Edges directly instead of values for all 3 variables and also change the ArrayList into PriorityQueue.
The Graph looks like this:
import java.util.Iterator;import java.util.PriorityQueue;public class Graph { private int vCount; private PriorityQueue<Edge>[] adj;
public int getvCount() { return vCount; }
public Graph(int vCount) { this.vCount = vCount; adj = new PriorityQueue[vCount]; for (int i = 0; i < vCount; i++) adj[i] = new PriorityQueue<Edge>(); }
public void addEdge(int i, int j, float weight) { adj[i].add(new Edge(i, j, weight)); }
public void addEdge(Edge e) { adj[e.getStartPoint()].add(e); }
public void removeEdge(int i, int j) { Iterator<Edge> it = adj[i].iterator(); Edge other = new Edge(i, j, 0); while (it.hasNext()) { if (it.next().equals(other)) { it.remove(); return; } } }
public boolean hasEdge(Edge e) { return adj[e.getStartPoint()].contains(e); }
public PriorityQueue<Edge> neighbours(int vertex) { return adj[vertex]; }
public void printGraph() { for (int i = 0; i < vCount; i++) { PriorityQueue<Edge> edges = neighbours(i); Iterator<Edge> it = edges.iterator(); System.out.print(i + ": "); for (int j = 0; j < edges.size(); j++) { System.out.print(it.next() + " "); } System.out.println(); } }}So, now into the Algorithms part! I will just give you the Code, cause it's pretty good commented and I also gave you the pseudocode before. After the Algorithms we will also test them out on the same Graph!
Kruskal Implemenation:
public static Graph Kruskal(Graph g) { Graph mst = new Graph(g.getvCount()); boolean[] marked = new boolean[g.getvCount()];
// create queue of all edges in ascending order PriorityQueue<Edge> edges = new PriorityQueue<Edge>(); for (int i = 0; i < g.getvCount(); i++) { Iterator<Edge> it = g.neighbours(i).iterator(); while (it.hasNext()) { edges.add(it.next()); } }
// first edge insert Edge e = edges.remove(); mst.addEdge(e); marked[e.getStartPoint()] = true;
// loop until no edges remain while (!edges.isEmpty()) { // get the edge with the less weight Edge temp = edges.remove();
// if no circle is being made if (!marked[temp.getEndPoint()]) { if (!mst.hasEdge(temp)) { mst.addEdge(temp); marked[temp.getEndPoint()] = true; } }
} return mst;}Prim Implementation:
public static Graph Prim(Graph g, int startVertex) { Graph mst = new Graph(g.getvCount()); boolean[] marked = new boolean[g.getvCount()];
// insert neighbours of first vertex PriorityQueue<Edge> edges = new PriorityQueue<Edge>(); Iterator<Edge> it = g.neighbours(startVertex).iterator(); while (it.hasNext()) { edges.add(it.next()); } marked[startVertex] = true;
// loop until no edges remain while (!edges.isEmpty()) { Edge e = edges.remove();
// if adding makes no circle if (!marked[e.getEndPoint()]) { mst.addEdge(e); marked[e.getEndPoint()] = true;
// add neighbour edges of vertex if don't marked yet Iterator<Edge> i = g.neighbours(e.getEndPoint()).iterator(); while (i.hasNext()) edges.add(i.next()); marked[e.getEndPoint()] = true; } } return mst;}
Testing Algorithms on same Graph:
import java.util.Iterator;import java.util.PriorityQueue;public class TestGraphs {
public static void main(String[] args) { Graph g = new Graph(5);
System.out.println("Graph:"); // add Edges g.addEdge(0, 1, 5.2f); g.addEdge(0, 3, 7.1f); g.addEdge(1, 3, 5.9f); g.addEdge(1, 4, 3.4f); g.addEdge(2, 1, 1.5f); g.addEdge(2, 3, 2.3f); g.addEdge(3, 4, 8.5f); g.addEdge(4, 2, 2.7f);
// print Graph g.printGraph();
// MST Algorithms System.out.println("Kruskal MST:"); Graph mst_1 = Kruskal(g); mst_1.printGraph(); System.out.println("Prim MST:"); Graph mst_2 = Prim(g, 0); mst_2.printGraph(); }}The results are different MST's, but both are MST's! There is not only one, but more then one MST's for each Graph, but both of them are great!
The Console print looks like this:
Graph:
0: 0-1 (5.2) 0-3 (7.1)
1: 1-4 (3.4) 1-3 (5.9)
2: 2-1 (1.5) 2-3 (2.3)
3: 3-4 (8.5)
4: 4-2 (2.7)
Kruskal MST:
0: 0-1 (5.2)
1: 1-4 (3.4)
2: 2-1 (1.5) 2-3 (2.3)
3:
4:
Prim MST:
0: 0-1 (5.2)
1: 1-4 (3.4)
2: 2-3 (2.3)
3:
4: 4-2 (2.7)
And this is actually it! Hope you enjoyed this post!
It took my quite some time to make all this! Graph algorithms can get really difficult :)
Bye!