在Golang中实现Prim算法

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

算法

• Step 1 – 首先，我们需要导入fmt和heap包。然后创建所需的结构体和函数，并为其定义属性。

• Step 2 – 进一步初始化一个空visited集合和一个二叉堆h，其中包含来自起始顶点s的最小边。

• Step 3 – 然后创建main()函数。在函数内部，通过将所需的顶点传递给addEdge()函数来初始化图形。

• Step 4 – 将顶点传递给图形结构中创建的函数，并将获得的结果存储在单独的变量中。

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

输出

Minimum weight: 16

结论

我们已成功编译和执行了一个 go 语言程序来实现 Prims Algorithm 和 Examples。 这里我们实现了两个程序。 在第一个程序中，我们使用二进制队列方法，而在第二个程序中，我们使用邻接方法以及优先队列方法。 此实现使用邻接矩阵来表示图形。 它还使用优先队列来维护到已访问集的最小距离的顶点。