package main import "fmt" import "sort" var myMap map[string]Node var vertices []string var edgeList []Edge type Node struct { data string rank int parent *Node } type Edge struct { startVertex string endVertex string value int } func insertVertex(vertex string) { vertices = append(vertices, vertex) } func insertEdge(vertex1 string, vertex2 string, edgeVal int) { var edge Edge myMap = make(map[string]Node) edge.startVertex = vertex1 edge.endVertex = vertex2 edge.value = edgeVal edgeList = append(edgeList, edge) } // Create groups with only one vertex. func createSet(data string){ var node Node node.data = data node.rank = 0 node.parent = &node myMap[data] = node } //Combines two groups into one. Does union by rank. func union(vertex1 string, vertex2 string){ node1 := myMap[vertex1] node2 := myMap[vertex2] parent1 := findSetNode(node1) parent2 := findSetNode(node2) //If they are in the same group, do nothing. if(parent1.data == parent2.data) { return } //Else whose rank is higher becomes parent of other. if (parent1.rank <= parent2.rank) { //Increment rank only if both sets have same rank. if (parent1.rank == parent2.rank) { parent1.rank = parent1.rank + 1 } //parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 : parent1.rank; parent2.parent = parent1 } else { parent1.parent = parent2 } } // Find the representative of this set func findSetString(data string) string{ return findSetNode(myMap[data]).data } // Finds the leader/representative recursivly and does PATH COMPRESSION as well. func findSetNode(node Node) *Node{ parentNode := *node.parent if (parentNode == node) { return node.parent } node.parent = findSetNode(*node.parent) return node.parent } // Find Minimum Spanning Tree using Kruskal's Algorithm. func createMST() []Edge { //Sort all edges in Ascending order. sort.SliceStable(edgeList, func(i, j int) bool { return edgeList[i].value < edgeList[j].value }) //Create as many groups as the total vertices. for _, vertex := range vertices { createSet(vertex) } var resultEdge []Edge for _, edge := range edgeList { //Get the sets of two vertices of the edge. root1 := findSetString(edge.startVertex) root2 := findSetString(edge.endVertex) //check if the vertices are on the same or different set. if (root1 == root2) { continue } else { // If vertices are in different sets then add the edge to result and union // these two sets into one. resultEdge = append(resultEdge, edge) union(edge.startVertex, edge.endVertex) } } return resultEdge; } func main() { // Adding vertices one by one insertVertex("a") insertVertex("b") insertVertex("c") insertVertex("d") insertVertex("e") //Adding edges with values. insertEdge("a", "b", 1) insertEdge("b", "e", 8) insertEdge("e", "d", 3) insertEdge("d", "a", 4) insertEdge("a", "c", 5) insertEdge("c", "e", 9) insertEdge("c", "d", 12) mstList := createMST() for _, edge := range mstList { fmt.Println("The edge : ",edge.startVertex," -- ",edge.endVertex," with value : ",edge.value) } }
So, we will be dealing with the below Graph,
1st Group - {a} --- rank 0 2nd Group - {b} --- rank 0 3rd Group - {c} --- rank 0 4th Group - {d} --- rank 0 5th Group - {e} --- rank 0
a --- b
1st Group - {a} --- rank 0 2nd Group - {b} --- rank 0
1st Group - {a,b}
In the above code, we have a Structure called Node. Which looks a little different.
type Node struct { data string rank int parent *Node }
You can think of the Node class as a representation of a Vertex.
And how is that so?
Just think, a vertex should have a rank and its name. And so we have
data string rank int
But the only mystery is, what is parent *Node?
A Node type variable inside a Node Structure! Looks Strange! Right?
Well ! It is like a connection, we are trying to establish between Vertices.
So, when the vertices are created for the first time, they should the leader of their group and off course they should be their parent.
Say for example when vertex a and b is created, a is in group 1 and b is in group 2.
parent *Node for vertex b is the Address of Node b (Since vertex b is the leader of group 2).
And Node parent for vertex a is Node a (Since vertex a is the leader of group 1).
Next, when b is put into group 1, the leader of group 1 is a.
So, vertex b is a child of a.
And Node parent of b is Node a now.
The vertex a is named as Node a and vetex b is named as Node b. We have seen how the connection is established.
As we have seen, the Node Structure is used to store the contents of the Vertices.
Similarly, the Edge Structure is used to store the contents of the Edges.
type Edge struct { startVertex string endVertex string value int }
The Edge Structure has three attributes,
The above one is the example of an edge that has,
startVertex = a endVertex = b value = 1
So, firstly we construct the graph by adding the vertices.
// Adding vertices one by one insertVertex("a") insertVertex("b") insertVertex("c") insertVertex("d") insertVertex("e")
Then adding the edges with its values,
//Adding edges with values. insertEdge("a", "b", 1) insertEdge("b", "e", 8) insertEdge("e", "d", 3) insertEdge("d", "a", 4) insertEdge("a", "c", 5) insertEdge("c", "e", 9) insertEdge("c", "d", 12)
Then we call the createMST() method to construct Minimum Spanning Tree using Kruskal's Algorithm.
mstList := createMST()
func createMST() []Edge { //Sort all edges in Ascending order. sort.SliceStable(edgeList, func(i, j int) bool { return edgeList[i].value < edgeList[j].value }) //Create as many groups as the total vertices. for _, vertex := range vertices { createSet(vertex) } var resultEdge []Edge for _, edge := range edgeList { //Get the sets of two vertices of the edge. root1 := findSetString(edge.startVertex) root2 := findSetString(edge.endVertex) //check if the vertices are on the same or different set. if (root1 == root2) { continue } else { // If vertices are in different sets then add the edge to result and union // these two sets into one. resultEdge = append(resultEdge, edge) union(edge.startVertex, edge.endVertex) } } return resultEdge; }
As we know, the first task is to sort the Edges,
sort.SliceStable(edgeList, func(i, j int) bool { return edgeList[i].value < edgeList[j].value })
The next task would be, to create individual groups for each Vertex using the createSet() method.
//Create as many groups as the total vertices. for _, vertex := range vertices { createSet(vertex) }
As we know vertices
var vertices []string
contains an Array of Vertices. So, we take the vertices one by one using the for range loop and call the creteSet() method.
createSet(vertex)
// Create groups with only one vertex. func createSet(data string){ var node Node node.data = data node.rank = 0 node.parent = &node myMap[data] = node }
The parameter data string contains the vertex(Say a for vertex a).
So, we create a Node object to hold the actual vertex
var node Node
(Say value a for vertex a)
node.data = data
the rank of the vertex.
node.rank = 0
rank is initialised to 0 because initially all the vertices would be the leader of their group and the leader is ranked 0.
The next line is extremely important,
node.parent = &node
Now since, vertex a is the leader of their group. node.parent is vertex a itself. And thus, node.parent would be holding the address of vertex a itself (i.e. &node).
Below is the example of vertex a.
Then we put the created node in the Map myMap,
var myMap map[string]Node
With the key as the value of vertex(a in this case) and value as the created node.
myMap = make(map[string]Node)
All the Nodes/vertices are created in the same way and put in the map.
Let us come back to the createMST() method again,
And since we got all the groups created.
Now, it's time for us to implement the actual logic.
And we have declared resultEdge Array that will store all the edges included in the Minimum Spanning Tree.
var resultEdge []Edge
Now, we know that the Array edgeList,
var edgeList []Edge
Contains the List of all the edges in the Graph(Off course Sorted in ascending order done earlier).
And what will will do is take List edgeList one by one and try constructing the Minimum Spanning Tree.
for _, edge := range edgeList { //Get the sets of two vertices of the edge. root1 := findSetString(edge.startVertex) root2 := findSetString(edge.endVertex) //check if the vertices are on the same or different set. if (root1 == root2) { continue } else { // If vertices are in different sets then add the edge to result and union // these two sets into one. resultEdge = append(resultEdge, edge) union(edge.startVertex, edge.endVertex) } }
So, the for range loop, takes the sorted edges one by one,
for _, edge := range edgeList
And the first thing it does is, tries to find the leader of each vertex using the findSet() method,
//Get the sets of two vertices of the edge. root1 := findSetString(edge.startVertex) root2 := findSetString(edge.endVertex)
func findSetString(data string) string{ return findSetNode(myMap[data]).data }
Now, the cool thing to note is, the return statement,
return findSetNode(myMap[data]).data
Calls another findSetNode(...) method.
Let's dive in to understand,
myMap[data] from the return statement,
return findSetNode(myMap[data]).data
gives us a Node type variable.
How ?
Because, we have seen map holds Key as the Vertex name (Say a) and its Node as value.
And if we pass the value a to the Map,
myMap[a]
We get the Node object of a.
So, this time we will be calling the findSetNode(...) method, that accepts Node as parameter.
And, we have the func findSetNode(node Node) *Node method that gets called.
func findSetNode(node Node) *Node{ parentNode := *node.parent if (parentNode == node) { return node.parent } node.parent = findSetNode(*node.parent) return node.parent }
So, in the first line, we have created a Node variable called parentNode and initialised the parentNode variable with the *parent from the parameter node Node.
Now let's say, we have passed Node a and the parent of Node a is Node a(Because Node a is the leader).
parentNode := *node.parent
Then we check if the Node parentNode is equal to the node from parameter Node node.
if (parentNode == node) { return node.parent }
In this case Node parentNode and Node node are equal.
So, the Node parent is returned.
But ! Yes there is a BUT.
Say, the node b was passed, when it was a child of a.
Now, let us relook the steps for Node b,
parentNode := *node.parent
So, Node parentNode would be Node a.
And Node parentNode would be holding the Node a.
Then we check if the Node parentNode is equal to the node from parameter Node node.
if (parentNode == node) { return node.parent }
And if condition is not satisfied as
Node parentNode is holding Node a and node is holding Node b.
Fair enough !
Then we go to the next line, where findSet(Node node) method is called recursively,
node.parent = findSetNode(*node.parent)
Until it finds the parent and finally node.parent is returned.
return node.parent;
So, let us come back to createMST() method again.
Let us take the example of edge
root1 := findSetString(edge.startVertex) root2 := findSetString(edge.endVertex)
Where, edge.startVertex is a and edge.endVertex is b.
And we found the parent of a is a itself and parent of b is b.
So,
root1 = "a"
and
root2 = "b"
And, if we see the code again,
for _, edge := range edgeList { //Get the sets of two vertices of the edge. root1 := findSetString(edge.startVertex) root2 := findSetString(edge.endVertex) //check if the vertices are on the same or different set. if (root1 == root2) { continue } else { // If vertices are in different sets then add the edge to result and union // these two sets into one. resultEdge = append(resultEdge, edge) union(edge.startVertex, edge.endVertex) } }
There is this if statement that checks,
if (root1 == root2)
But in this case root1 is a and root2 is b.
So, we come to the else part.
else { // If vertices are in different sets then add the edge to result and union // these two sets into one. resultEdge = append(resultEdge, edge) union(edge.startVertex, edge.endVertex) }
Now since, we are in the else part. This edge,
must be included in the Minimum Spanning Tree.
resultEdge = append(resultEdge, edge)
And thus, we have added it to the resultEdge list.
So, the next task would be to combine a and b in the same group.
union(edge.startVertex, edge.endVertex)
And this task of combining is done by the union(...) method.
func union(vertex1 string, vertex2 string){ node1 := myMap[vertex1] node2 := myMap[vertex2] parent1 := findSetNode(node1) parent2 := findSetNode(node2) //If they are in the same group, do nothing. if(parent1.data == parent2.data) { return } //Else whose rank is higher becomes parent of other. if (parent1.rank <= parent2.rank) { //Increment rank only if both sets have same rank. if (parent1.rank == parent2.rank) { parent1.rank = parent1.rank + 1 } //parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 : parent1.rank; parent2.parent = parent1 } else { parent1.parent = parent2 } }
Let us take the example of
to explain the union(...) method.
node1 := myMap[vertex1] node2 := myMap[vertex2]
And
node2 will have the contents of Node b and node1 will have the contents of Node a.
In the next two lines,
parent1 := findSetNode(node1) parent2 := findSetNode(node2)
We try to find the parents/leaders of node1 and node2 using func findSetNode(node Node) *Node method which we have already seen.
And in this case, the parent of a is a and the parent of b is b.
Next, we check, if both the parent of the vertices are equal or not,
if(parent1.data == parent2.data) { return }
If both the parents are equal, we do nothing.
But in this case, they are not equal as
parent1.data = "a"
and
parent2.data = "b"
So, we come to the next if statement.
//Else whose rank is higher becomes parent of other. if (parent1.rank <= parent2.rank) { //Increment rank only if both sets have same rank. if (parent1.rank == parent2.rank) { parent1.rank = parent1.rank + 1 } //parent1.rank = (parent1.rank == parent2.rank) ? parent1.rank + 1 : parent1.rank; parent2.parent = parent1 } else { parent1.parent = parent2 }
In the if statement, we check if parent1.rank is less than or equal to parent2.rank.
if (parent1.rank <= parent2.rank)
And in this case,
parent1.rank and parent2.rank has the same rank i.e. 0 (From the above diagram).
And in the next line,
if (parent1.rank == parent2.rank) { parent1.rank = parent1.rank + 1 }
We increment the parent1.rank only if parent1.rank is equal to parent2.rank.
And in this case parent1.rank is equal to parent2.rank,
So, we increment parent1.rank by 1.
parent1.rank = parent1.rank + 1
And parent1.rank becomes,
parent1.rank = 1
Then, we initialise parent2.parent with parent1.
parent2.parent = parent1
And we can see that the connection between a and b is established,
And continuing this way, we get the Minimum Spanning Tree,