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