数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
服装研究
法律研究使用Go语言实现Prim算法
在本文中，我们将学习如何使用二叉堆方法和优先队列方法在Go语言中实现Prim算法。Prim算法用于查找加权无向图的最小生成树。
算法
步骤1 − 首先，我们需要导入fmt和heap包。然后创建所需的结构体和函数，并为其定义属性。
步骤2 − 接下来，初始化一个空的已访问集合和一个二叉堆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)
}
输出
Minimum weight: 16
结论
我们已经成功地编译并执行了一个Go语言程序来实现Prim算法以及示例。这里我们实现了两个程序。在第一个程序中，我们使用二叉堆方法，而在第二个程序中，我们使用邻接矩阵和优先队列方法。此实现使用邻接矩阵来表示图。它还使用优先队列来维护与已访问集合距离最小的顶点。
更新于：2023年4月5日
293 次浏览
广告