Golang 实现Kruskal算法

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

步骤

第1步 - 首先，我们需要导入fmt和sort包。然后创建名为Edge、graph和subset的结构体，并为其分配属性。
第2步 - 然后以非递减顺序对图的所有边进行排序。
第3步 - 创建不相交集数据结构，其中每个集合只包含一个顶点。
第4步 - 对于排序后的图中的每条边。如果边连接了两个不相交的集合，则将其添加到最小生成树中并合并这两个集合。最后返回最小生成树。
第5步 - 现在，启动main()函数。在main()函数中，初始化一个图并将边赋给它。进一步，通过将边作为参数传递给kruskals()函数来调用它。
第6步 - 将函数得到的结果存储在一个变量中，并将它们打印到屏幕上。

示例1

在此示例中，我们将编写一个Go语言程序，使用并查集算法实现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("The given input is:", graph)
   fmt.Println()
   mst := kruskals(graph)
   fmt.Println("Minimum Spanning Tree:")
   for _, edge := range mst {
      fmt.Printf("(%d, %d) with weight %d\n", edge.Src, edge.Dest, edge.Weight)
   }
}

输出

The given input is: {[{0 1 10} {0 2 6} {0 3 5} {1 3 15} {2 3 4}] 4}

Minimum Spanning Tree:
(2, 3) with weight 4
(0, 3) with weight 5
(0, 1) with weight 10

示例2

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

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 // for safety
   *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)

         // Update the parent node of the subset containing the src vertex
         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("The given input is:", graph)
   mst := kruskals(graph)
   fmt.Println()
   fmt.Println("Minimum Spanning Tree:")
   for _, edge := range mst {
      fmt.Printf("(%d, %d) with weight %d\n", edge.Src, edge.Dest, edge.Weight)
   }
}

输出

The given input is: {[{0 1 10} {0 2 6} {0 3 5} {1 3 15} {2 3 4}] 4}

Minimum Spanning Tree:
(2, 3) with weight 4
(0, 3) with weight 5
(0, 1) with weight 10