質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.78%

プリム法の出力結果が模範解答と異なるので困っています。

解決済

回答 2

投稿 編集

  • 評価
  • クリップ 1
  • VIEW 1,311

Teemro_431265

score 29

プリム法について勉強について勉強しているのですが入力が100×100隣接行列の時に結果が少しだけ異なってしまいます。
問題としては最小全域木で与えられた重み付きグラフに対する最小全域木の辺の重みの総和を計算するプログラムを作成すると言うものです。
Prims関数に関して何かおかしなところがあれば教えていただきたいです。
問題はこちらです。
問題
うまくいかない入力例はこちらです。
入力例

本来なら出力結果が
3864
となるはずなのですが
3991
となってしまいます。

#include<stdio.h>
#define max 1000
#define inf 100000

int vertex_num,admat[max][max];

int Prims(){
  int i,j,u,v,cost[max][max],min_distance;
  int visit[max],no_edges,min_cost,distance[max],from[max];

  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
      if(admat[i][j]==0){
          cost[i][j]=inf;
      }else{
          cost[i][j]=admat[i][j];
      }
    }
  }
  distance[0]=0;
  visit[0]=1;

  for(i=1;i<vertex_num;i++){
      distance[i]=cost[0][i];
      from[i]=0;
      visit[i]=0;
  }
  min_cost=0;
  no_edges=vertex_num-1;

  while(no_edges>0){
     min_distance=inf;
     for(i=1;i<vertex_num;i++){
         if(visit[i]==0 && distance[i]<min_distance){
             v=i;
             min_distance=distance[i];
         }
     }
     u=from[v];
     no_edges--;
     visit[v]=1;
     for(i=1;i<vertex_num;i++){
         if(visit[i]==0 && cost[i][v]<distance[i]){
             distance[i]=cost[i][v];
             from[i]=v;
         }
     }
     min_cost+=cost[u][v];
  }

  return min_cost;
}

int main(){
  //admatは隣接行列
  int i,j;

  scanf("%d",&vertex_num);
  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
      scanf("%d",&admat[i][j]);
    }
  }
  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
       if(admat[i][j]==-1){
           admat[i][j]=0;
       }
       //printf("%d ",admat[i][j]);
    }
  }

  printf("%d\n",Prims());
  return 0;
}
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 2

+3

回答ではないですが、

C言語のコードを組みたいのであれば、デバッグ環境を整えましょう
WindowsであればVisualStudio、そうでなければEclipseなど、
これらの統合環境では、C言語のコードの任意の行で実行を停止させ、変数の値を参照したり、1行づつステップ実行させて変数の値を追いかけるなどができるようになります
そうすれば、あてずっぽでコードを組む、ということをしなくて済みます 

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/27 15:20

    あてずっぽでコードは組んでません。

    キャンセル

  • 2019/01/27 15:34

    ソースデバッグできる環境をお持ちなら、どこで計算がおかしくなっていっているのか、というのを探っていきましょう。
    すでにそういうことはやってる、というのであれば、この回答は無視してください。

    #で、できればどこでおかしいのかというのを追記していただけるとありがたいです

    キャンセル

  • 2019/01/27 22:21

    これ、ちょっと追ってみたけど、単純にデバッグ環境があるからと言ってデバッグできるとは思えない。
    プリム法に関する知識が無いと厳しそう。コードそのものは、デバッガなんか無しでも追跡は容易。ただし、意味するところが、、。ちょっと調べてみたが、まだ理解できず。
    あ、Visual Studio 2017 の cl でコンパイルしたら、実行時にエラー無し終了。どうもstackサイズオーバーか? ローカルをグローバルに移して実行できました。

    キャンセル

checkベストアンサー

+1

  for(i=0;i<vertex_num;i++){
    for(j=0;j<vertex_num;j++){
       if(admat[i][j]==-1){
           admat[i][j]=0;
       }
       //printf("%d ",admat[i][j]);
    }
  }

が間違いでは?

参照ページの制約条件に

0≤aij≤2,000 (aij≠−1 のとき)

があります。
上記箇所を削除すると共に、

      if(admat[i][j]==0){
          cost[i][j]=inf;


      if(admat[i][j]==-1){
          cost[i][j]=inf;


とする。

手元の計算では、 3864 となりました。
(実際にうまくいかない入力例には、0が含まれています)

[追記]
結局、プリム法は理解できないまま。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2019/01/31 12:00

    回答ありがとうございます。
    まだ何が悪いのかはわかっていないので参考にさせていただきます。

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.78%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る