数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在Go语言中实现克鲁斯卡尔算法
在本文中，我们将了解如何开发一个Go语言程序，借助并查集算法和优先队列方法来实现克鲁斯卡尔算法。克鲁斯卡尔算法用于查找图的最小生成树。
算法
步骤 1 − 首先，我们需要导入fmt和sort包。然后创建名为Edge、graph和subset的结构体，并为其分配属性。
步骤 2 − 然后按边的权重非递减顺序对图的所有边进行排序。
步骤 3 − 创建一个不相交集数据结构，其中每个集合只包含一个顶点。
步骤 4 − 对于排序后的图中的每条边。如果该边连接两个不相交集，则我们需要将其添加到最小生成树中并合并这两个集合。最后返回最小生成树。
步骤 5 − 现在，开始main()函数。在main()函数内部初始化一个图并为其分配边。进一步通过将边作为参数传递给它来调用kruskals()函数。
步骤 6 − 将函数获得的结果存储在一个变量中，并在屏幕上打印出来。
示例 1
在这个示例中，我们将编写一个Go语言程序，使用并查集算法来实现克鲁斯卡尔算法。
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语言程序，使用优先队列算法来实现克鲁斯卡尔算法。
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
结论
我们已经成功编译并执行了一个Go语言程序来实现克鲁斯卡尔算法以及示例。
更新于: 2023年4月5日
325 次浏览
广告