Golang 实现Prim算法

在这篇文章中，我们将学习如何使用二进制堆方法和优先队列方法在Golang中实现Prim算法。Prim算法用于查找加权无向图的最小生成树。

步骤

第1步 −首先，我们需要导入fmt和heap包。然后创建所需的结构体和函数并为它们定义属性。
第2步 −进一步初始化一个空的visited集合和一个二进制堆h，其中包含来自起始顶点s的最小边。
第3步 −然后创建main()函数。在函数内部，通过将所需的顶点传递给addEdge()函数来初始化图。
第4步 −将顶点传递给在图结构中创建的函数，并将得到的结果存储在一个单独的变量中。
第5步 −最后，使用fmt.Println()函数将结果打印到屏幕上。

示例1

在这个示例中，我们将编写一个Go语言程序来使用二进制堆方法实现Prim算法。

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)
}

输出

Minimum weight: 16

示例2

在这个示例中，我们将编写一个 Go 语言程序，通过使用邻接算法和优先队列来实现 Prim 算法。

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)
}