Почему этот код создает неправильное минимальное остовное дерево по алгоритму Прима? - PullRequest
Новая
       36

Почему этот код создает неправильное минимальное остовное дерево по алгоритму Прима?

0 голосов
/ 23 июня 2019

У меня есть некоторый код на Голанге с алгоритмом Прима. Задача состоит в том, чтобы найти минимальное остовное дерево с минимальным количеством длин ребер. Но если число вершин больше 3, я получаю неправильный ответ.

Поэтому я попытался переписать алгоритм Прима, но ничего не изменилось. 

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
}

Мне нужно вывести минимальную сумму длины ребер в минимальном остовном дереве. Есть вход: 

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

Я получаю 1038 в качестве ответа, но правильный ответ - 951.

...