在Golang中实现Kruskal算法

在本文中，我们将了解如何使用union-find算法和优先级队列方法开发golang程序来实现Kruskal算法。Kruskal算法用于查找图的最小生成树。

算法

• 第1步 – 首先，我们需要导入fmt和sort包。然后创建名为Edge、Graph和Subset的结构体，并为其分配属性。

• 第2步 – 然后，按它们的权重将图的所有边排序。

• 第3步 – 创建一个不相交的集合数据结构，其中每个集合仅包含一个顶点。

• 第4步 – 对于排序后的图中的每条边。如果该边连接了两个不相交的集合，则需要将其添加到最小生成树中并合并这两个集合。最后返回最小生成树。

• 第5步 – 现在，开始main()函数。在main()函数中初始化图并为其分配边。然后通过将边作为参数调用kruskals()函数。

• 第6步 – 将函数获得的结果存储在变量中并在屏幕上打印它们。

实例1

在此示例中，我们将编写一个Go语言程序，通过使用union-find算法来实现Kruskal算法。

package main

import (
   "fmt"
   "sort"
)

type Edge struct {
   Src, Dest, Weight int
}

type Graph struct {
   Edges    []Edge
   Vertices int
}

type Subset struct {
   Parent int
   Rank   int
}

func find(subsets []Subset, i int) int {
   if subsets[i].Parent != i {
      subsets[i].Parent = find(subsets, subsets[i].Parent)
   }
   return subsets[i].Parent
}

func union(subsets []Subset, x, y int) {
   rootX := find(subsets, x)
   rootY := find(subsets, y)
   if subsets[rootX].Rank < subsets[rootY].Rank {
      subsets[rootX].Parent = rootY
   } else if subsets[rootX].Rank > subsets[rootY].Rank {
      subsets[rootY].Parent = rootX
   } else {
      subsets[rootY].Parent = rootX
      subsets[rootX].Rank++
   }
}

func kruskals(graph Graph) []Edge {
   sortedEdges := make([]Edge, len(graph.Edges))
   copy(sortedEdges, graph.Edges)
   sort.Slice(sortedEdges, func(i, j int) bool {
      return sortedEdges[i].Weight < sortedEdges[j].Weight
   })
   subsets := make([]Subset, graph.Vertices)
   for i := range subsets {
      subsets[i].Parent = i
      subsets[i].Rank = 0
   }
   result := make([]Edge, 0, graph.Vertices-1)
   for _, edge := range sortedEdges {
      srcRoot := find(subsets, edge.Src)
      destRoot := find(subsets, edge.Dest)
      if srcRoot != destRoot {
         result = append(result, edge)
         union(subsets, srcRoot, destRoot)
      }
   }
   return result
}

func main() {
   graph := Graph{
      Edges: []Edge{
         {0, 1, 10},
         {0, 2, 6},
         {0, 3, 5},
         {1, 3, 15},
         {2, 3, 4},
      },
      Vertices: 4,
   }
   fmt.Println("给定输入为:", graph)
   fmt.Println()
   mst := kruskals(graph)
   fmt.Println("最小生成树:")
   for _, edge := range mst {
      fmt.Printf("(%d, %d) 权重为 %d\n", edge.Src, edge.Dest, edge.Weight)
   }
}

输出

给定输入为: {[{0 1 10} {0 2 6} {0 3 5} {1 3 15} {2 3 4}] 4}

最小生成树:
(2, 3) 权重为 4
(0, 3) 权重为 5
(0, 1) 权重为 10

示例2

在此示例中，我们将编写一个Go语言程序，通过使用优先队列算法实现Kruskal算法。

package main

import (
   "container/heap"
   "fmt"
)

type Edge struct {
   Src    int
   Dest   int
   Weight int
}

type Graph struct {
   Edges    []Edge
   Vertices int
}

type PriorityQueue []*Item

type Item struct {
   value    Edge
   priority int
   index    int
}

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
   return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
   pq[i], pq[j] = pq[j], pq[i]
   pq[i].index = i
   pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
   n := len(*pq)
   item := x.(*Item)
   item.index = n
   *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
   old := *pq
   n := len(old)
   item := old[n-1]
   item.index = -1 //为了安全起见
   *pq = old[0 : n-1]
   return item
}

func find(subsets []int, i int) int {
   if subsets[i] != i {
      subsets[i] = find(subsets, subsets[i])
   }
   return subsets[i]
}

func union(subsets []int, x int, y int) {
   xroot := find(subsets, x)
   yroot := find(subsets, y)
   subsets[yroot] = xroot
}

func kruskals(graph Graph) []Edge {
   pq := make(PriorityQueue, len(graph.Edges))
   for i, edge := range graph.Edges {
      pq[i] = &Item{
         value:    edge,
         priority: edge.Weight,
         index:    i,
      }
   }
   heap.Init(&pq)
   subsets := make([]int, graph.Vertices)
   for i := range subsets {
      subsets[i] = i
   }
   result := make([]Edge, 0, graph.Vertices-1)
   for pq.Len() > 0 {
      item := heap.Pop(&pq).(*Item)
      edge := item.value
      srcRoot := find(subsets, edge.Src)
      destRoot := find(subsets, edge.Dest)
      if srcRoot != destRoot {
         result = append(result, edge)

         // 更新包含源顶点的子集的父节点
         union(subsets, edge.Src, edge.Dest) 
      }
   }
   return result
}

func main() {
   graph := Graph{
      Edges: []Edge{
         {0, 1, 10},
         {0, 2, 6},
         {0, 3, 5},
         {1, 3, 15},
         {2, 3, 4},
      },
      Vertices: 4,
   }
   fmt.Println("给定的输入是:", graph)
   mst := kruskals(graph)
   fmt.Println()
   fmt.Println("最小生成树:")
   for _, edge := range mst {
      fmt.Printf("(%d, %d) 权重为 %d\n", edge.Src, edge.Dest, edge.Weight)
   }
}

输出

给定的输入是: {[{0 1 10} {0 2 6} {0 3 5} {1 3 15} {2 3 4}] 4}

最小生成树:
(2, 3) 权重为 4
(0, 3) 权重为 5
(0, 1) 权重为 10

结论

我们成功编译并执行了一个go语言程序来实现Kruskal算法，包括示例。