Implement Prim's Algorithm in Golang

In this article we are going to learn how to use Binary Heap method and Priority queue method to implement prims Algorithm in golang. Prim's Algorithm is used to find the minimum spanning tree of a weighted undirected graph.

Algorithm

• Step 1 ? First, we need to import the fmt and heap package. Then create the required structs and functions and define properties to them.

• Step 2 ? Further Initialize an empty visited set and a binary heap h with the minimum edge from the starting vertex s.

• Step 3 ? Then create the main() function. Inside the function initialize graph by passing the required vertices to the addEdge() function.

• Step 4 ? Pass the vertices to the function created in graph struct and store the result obtained in a separate variable.

• Step 5 ? At last print the result on the screen by using fmt.Println() function.

Example 1

In this Example we will write a go language program to implement the prims Algorithm by using the binary heap method.

package main

import (
   "container/heap"
   "fmt"
)

type Edge struct {
   u, v, w int
}

type Graph struct {
   n     int
   edges []Edge
   adj   [][]Edge
}

func (g *Graph) addEdge(u, v, w int) {
   g.adj[u] = append(g.adj[u], Edge{u, v, w})
   g.adj[v] = append(g.adj[v], Edge{v, u, w})
   g.edges = append(g.edges, Edge{u, v, w})
}

func (g *Graph) prim() int {
   visited := make([]bool, g.n)
   h := &EdgeHeap{}
   heap.Push(h, Edge{-1, 0, 0})
   minWeight := 0
   for h.Len() > 0 {
      e := heap.Pop(h).(Edge)
      if visited[e.v] {
         continue
      }
      visited[e.v] = true
      minWeight += e.w
      for _, edge := range g.adj[e.v] {
         if !visited[edge.v] {
            heap.Push(h, edge)
         }
      }
   }
   return minWeight
}

type EdgeHeap []Edge

func (h EdgeHeap) Len() int           { return len(h) }
func (h EdgeHeap) Less(i, j int) bool { return h[i].w < h[j].w }
func (h EdgeHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *EdgeHeap) Push(x interface{}) {
   *h = append(*h, x.(Edge))
}

func (h *EdgeHeap) Pop() interface{} {
   old := *h
   n := len(old)
   x := old[n-1]
   *h = old[0 : n-1]
   return x
}

func main() {
   g := &Graph{
      n:   5,
      adj: make([][]Edge, 5),
   }
   g.addEdge(0, 1, 2)
   g.addEdge(0, 3, 6)
   g.addEdge(1, 2, 3)
   g.addEdge(1, 3, 8)
   g.addEdge(1, 4, 5)
   g.addEdge(2, 4, 7)
   g.addEdge(3, 4, 9)
   minWeight := g.prim()
   fmt.Println("Minimum weight:", minWeight)
}

Output

Minimum weight: 16

Example 2

In this Example we will write a go language program to implement the prims Algorithm by using an adjacency Algorithm and a priority queue.

package main

import (
   "container/heap"
   "fmt"
)

type Edge struct {
   v, w int
}

type Graph struct {
   n      int
   adjMat [][]int
}

func (g *Graph) addEdge(u, v, w int) {
   g.adjMat[u][v] = w
   g.adjMat[v][u] = w
}

func (g *Graph) prim() int {
   visited := make([]bool, g.n)
   dist := make([]int, g.n)
   parent := make([]int, g.n)
   for i := range dist {
      dist[i] = 1 << 31 // set dist to infinity
   }
   dist[0] = 0
   h := &VertexHeap{}
   heap.Push(h, Vertex{0, 0})
   minWeight := 0
   for h.Len() > 0 {
      u := heap.Pop(h).(Vertex).v
      if visited[u] {
         continue
      }
      visited[u] = true
      minWeight += dist[u]
      for v := 0; v < g.n; v++ {
         if g.adjMat[u][v] != 0 && !visited[v] && g.adjMat[u][v] < dist[v] {
            dist[v] = g.adjMat[u][v]
            parent[v] = u
            heap.Push(h, Vertex{v, dist[v]})
         }
      }
   }
   return minWeight
}

type Vertex struct {
   v, dist int
}

type VertexHeap []Vertex

func (h VertexHeap) Len() int           { return len(h) }
func (h VertexHeap) Less(i, j int) bool { return h[i].dist < h[j].dist }
func (h VertexHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *VertexHeap) Push(x interface{}) {
   *h = append(*h, x.(Vertex))
}

func (h *VertexHeap) Pop() interface{} {
   old := *h
   n := len(old)
   x := old[n-1]
   *h = old[0 : n-1]
   return x
}

func main() {
   g := &Graph{
      n:      5,
      adjMat: make([][]int, 5),
   }
   for i := range g.adjMat {
      g.adjMat[i] = make([]int, 5)
   }
   g.addEdge(0, 1, 2)
   g.addEdge(0, 3, 6)
   g.addEdge(1, 2, 3)
   g.addEdge(1, 3, 8)
   g.addEdge(1, 4, 5)
   g.addEdge(2, 4, 7)
   g.addEdge(3, 4, 9)

   minWeight := g.prim()
   fmt.Println("Minimum weight:", minWeight)
}

Output

Minimum weight: 16

Conclusion

We have successfully compiled and executed a go language program to implement prims Algorithm along with the Examples. Here we have implemented two programs. In the first program we are using binary queue method while in the second one we are using adjacency method along with priority queue approach. This implementation uses an adjacency matrix to represent the graph. It also uses a priority queue to maintain the vertices with the minimum distance to the visited set.