在边的权重取值范围为\(1 \sim |V|\)内，Prim算法的时间复杂度为\(O(V^2)\)。这是因为Prim算法每次选择与当前最小生成树连接的最短边时，需要遍历所有剩余节点来寻找最小边。
如果边的权重取值范围在1到常数\(W\)之间，Prim算法的时间复杂度可以优化到\(O((V+E)\log V)\)。这是因为我们可以使用最小堆（或者优先队列）来维护距离最小的边，并通过更新距离和添加新边时调整堆中元素的位置。这样每次选取最小距离的操作就可以在\(O(\log V)\)时间内完成。
以下是一个使用Go语言实现Prim算法的示例代码：
package main
import (
"container/heap"
"fmt"
)
type Edge struct {
to int // 边的目标节点
weight int // 边的权重
}
type PriorityQueue []Edge
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].weight < pq[j].weight }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(Edge))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
x := old[n-1]
*pq = old[0 : n-1]
return x
}
func prim(graph [][]Edge, start int) []Edge {
numNodes := len(graph)
// 初始化最小堆和访问数组
pq := make(PriorityQueue, 0)
heap.Init(&pq)
visited := make([]bool, numNodes)
// 将起始节点标记为已访问并将与其相邻的边加入最小堆
visited[start] = true
for _, edge := range graph[start] {
heap.Push(&pq, edge)
}
var minSpanningTree []Edge
for pq.Len() > 0 {
minEdge := heap.Pop(&pq).(Edge)
toNode := minEdge.to
if visited[toNode] {
continue // 如果目标节点已被访问，跳过该边
}
minSpanningTree = append(minSpanningTree, minEdge)
visited[toNode] = true
// 将与新加入的节点相邻的边加入最小堆
for _, edge := range graph[toNode] {
if !visited[edge.to] {
heap.Push(&pq, edge)
}
}
}
return minSpanningTree
}
func main() {
graph := [][]Edge{
{{1, 5}, {2, 3}, {3, 2}},
{{0, 5}, {2, 6}, {4, 7}},
{{0, 3}, {1, 6}, {4, 9}},
{{0, 2}, {4, 8}},
{{1, 7}, {2, 9}, {3, 8}},
}
startNode := 0
minSpanningTree := prim(graph, startNode)
fmt.Println("Minimum Spanning Tree:")
for _, edge := range minSpanningTree {
fmt.Printf("%d - %d (weight: %d)\n", startNode, edge.to, edge.weight)
}
}
这段代码演示了如何使用最小堆实现Prim算法，从给定的起始节点开始构建最小生成树。它输出了最小生成树的边及其权重。
内容由零声教学AI助手提供，问题来源于学员提问
