dongyixun0634 2019-06-23 19:27
浏览 89

为什么此代码使用Prim的算法生成了错误的最小生成树?

I have some code on Golang with Prim's algorythm. The task is to find minimal spanning tree with a minimum amount of edge lengths. But if vertices number is greater then 3, I'm getting wrong answer.

So I tried to rewrite Prim's algorythm, but nothing changed.

func MST_Prim(vertices []*Vertex, vertNum int, edgeNum int) []*Edge {
    treeEdges := make([]*Edge, 0)

    for i := 0; i < vertNum; i++ {
        vertices[i].index = -1
    }

    queue := make(PriorityQueue, 0)
    v := vertices[0]
    for i := 0; i < vertNum; i++ {
        v.index = -2

        for _, edge := range vertices[v.id].edges {
            u := vertices[edge.v]

            if u.index == -1 {
                u.priority = edge.len
                u.value = v.id
                queue.Push(u)
            } else if u.index != -2 && edge.len < u.priority {
                u.value = v.id
                queue.update(u, v.value, edge.len)
            }
        }

        if queue.Len() == 0 {
            break
        }

        v = queue.Pop().(*Vertex)
        treeEdges = append(treeEdges, &Edge{v.id, v.value, v.priority})
    }

    return treeEdges
}

I need to print minimal sum of length of edges in minimal spanning tree. There is the input:

4
4
1 2 462
0 3 343
0 1 430
1 3 146

I'm getting 1038 as answer, but correct answer is 951.

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥15 关于#matlab#的问题:在模糊控制器中选出线路信息,在simulink中根据线路信息生成速度时间目标曲线(初速度为20m/s,15秒后减为0的速度时间图像)我想问线路信息是什么
    • ¥15 banner广告展示设置多少时间不怎么会消耗用户价值
    • ¥16 mybatis的代理对象无法通过@Autowired装填
    • ¥15 可见光定位matlab仿真
    • ¥15 arduino 四自由度机械臂
    • ¥15 wordpress 产品图片 GIF 没法显示
    • ¥15 求三国群英传pl国战时间的修改方法
    • ¥15 matlab代码代写,需写出详细代码,代价私
    • ¥15 ROS系统搭建请教(跨境电商用途)
    • ¥15 AIC3204的示例代码有吗,想用AIC3204测量血氧,找不到相关的代码。