Ошибка при получении минимального связующего дерева из графика?

Question

Я пытаюсь получить минимальное связующее дерево неориентированного взвешенного графика, который должен вернуть вес минимального связующего дерева или -1, если минимальное связующее дерево не найдено с помощью пакета CITS2200, ниже приведена ссылка на CITS2200.jar:

CITS2200.jar

мне было интересно, если кто-нибудь мог понять, почему мой метод getMinSpanningTree в следующем коде не проходит тест, любая помощь будет оценена. Привет, Бен. с»)

getShortestPath (G, v) метод работает отлично, однако, ниже сообщение об ошибке я получаю, когда я проверить свой код на тест-класс:

Answer 1

Я думаю, что проблема с этим линия:.

sum += g.getWeight(u,v); 

вы добавляете вес к вашей общей стоимости, когда вы рассмотреть добавление ребра к остову Это будет переоценивать истинную стоимость остовного дерева

Вместо этого. ты шуешь d только добавьте вес, когда вы находитесь , определенный край добавляется к остовному дереву (т. немедленно после int u = minKey(key, mstSet);)

например. что-то вроде:

int u = minKey(key, mstSet); 
if (parent[u] != -1) 
    sum += g.getWeight(parent[u],u); 

Answer 2

1. В строке: for (int count = 0; count < g.getNumberOfVertices()-1; count++) - удалить минус 1: for (int count = 0; count < g.getNumberOfVertices(); count++)

2. Как упоминалось Питер, ваша проблема в суммировании. Вам не нужно суммировать во время процесса поиска mst. Вы должны суммировать вес найденного MST в конце:

Удалить sum += g.getWeight(u,v); из цикла.

Добавить после цикла:

int sum = 0; 
     for (int v = 0; v < mstSet.length; v++) 
     { 
      if (mstSet[v] && parent[v] >= 0) 
      { 
       System.out.println("In MST: (" + (parent[v]+1) + ", " + (v+1) + ")"); 
       sum += g.getWeight(parent[v], v); 
      } 
     } 

     return sum;