グラフから最小スパニングツリーを取得する際にエラーが発生しましたか？

Question

CITS2200というパッケージを使用して最小スパニングツリーが見つからない場合は、最小スパニングツリーの重みを返す、無向グラフの最小スパニングツリーを取得しようとしています。 CITS2200.jar：

CITS2200.jar

次のコードでは、私のgetMinSpanningTree方法は、試験に合格されていない理由を誰が見ることができれば、私は思っていたが、任意の助けいただければ幸いです。乾杯、ベン。 C」、）

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の重みを合計する必要があります。

ためのループからsum += g.getWeight(u,v);を削除します。

forループの後に追加：入力ピーターのため

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;