資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告