平均頂点間距離

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
みん
記事: 1
登録日時: 2年前

平均頂点間距離

#1

投稿記事 by みん » 2年前

[1] 平均頂点間距離を求めるコードを作成しています.
 [1.1] 枝リストの入っているデータファイルを読み込み,隣接行列を求めてから平均頂点間距離を求めるコードを作成しています.

 [1.2] 以下にコードを載せます.

コード:

//平均頂点間距離を求めるコード
/* 隣接行列の作成*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h> /* 文字列関数を扱えるようにする*/
#define maxN 1000 /* 扱う頂点数の最大値,ここでは1000 に設定*/

/*ワーシャルフロイド法*/
void warshall_floyd(int N, int Adj[N][N], double length[N][N]){
    int i,j,k;

    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            for(k=0;k<N;k++){
                length[j][k] = length[j][i] + length[i][k];
            }
        }
    }
}

int main(void)
{
    int N, M; /* 頂点数,辺数*/
    int Adj[maxN][maxN]; /* 隣接行列を表す変数*/

    /* 必要な変数を宣言*/
    int u,v;
    int i, j, k;

    double length[N][N];//頂点間距離
    double ave_length;//平均頂点間距離
    int branch;
    
    char fname[128]; /* 読み込むファイルの名前*/
    FILE *fp; /* 入力ファイル*/

    printf("input filename: "); /* ファイル名の入力を要求*/

    /* 入力ファイルの操作*/
    fgets(fname,sizeof(fname),stdin);
    fname[strlen(fname)-1]='\0';
    fflush(stdin);

    fp = fopen(fname, "r"); /* ファイルを読み込みモードで開く*/
    fscanf(fp, "%d %d", &N, &M); /* ファイルからN, Mを読み込む*/

    for (u=0; u<N+1; u++){ /* 隣接行列の初期化*/
	for (v=0; v<N+1; v++){
	    Adj[u][v] = 0;
	}
    }

    while(! feof(fp))
{
    /* 頂点u,vを読み込む */
    fscanf(fp, "%d %d", &u, &v);

    if( u > N )
    {
        N = u; //uがNより大きかった場合、uを代入
    }

    Adj[u][v] = 1;
    Adj[v][u] = 1;
}
    fclose(fp);
    printf("Adjacency matrix\n"); /* 隣接行列出力*/
    for (u=0; u<N; u++){

	printf("%2d |", u);
	for( v=0; v<N; v++){
	    printf("%2d ", Adj[u][v]);
	}
	printf("\n");
    }
    

//lengthの初期化
for(i=0; i<N; i++){
      for(j=0; j<N; j++){
          length[i][j] = 0;
      }
    }
    
//ワーシャルフロイド法で全点対最短経路を求める    
warshall_floyd(N, Adj, length);
    for(i=0;i<N;i++){
        for(j=0;j<N;j++){
            ave_length += length[i][j];
            
        }
    }
branch = N * (N+1);
printf("平均頂点間距離: %lf\n", ave_length/branch);

return 0;
}
 [1.3]上記のコードを実行すると Segmentation fault: 11 とセグメンテーション違反が出てきてしまいます.
どこの部分を変えればいいのか教えていただけると嬉しいです.

[2] 環境  
 [2.1] OS : MacOS
 [2.2] コンパイラ名 : gcc

アバター
みけCAT
記事: 6734
登録日時: 13年前
住所: 千葉県
連絡を取る:

Re: 平均頂点間距離

#2

投稿記事 by みけCAT » 2年前

・double length[N][N];//頂点間距離 において、未初期化のNの値が使われているため、未定義動作になります。
 この行は fscanf(fp, "%d %d", &N, &M); /* ファイルからN, Mを読み込む*/ の次に移動するべきです。
・fflush(stdin); は未定義動作になります。この後標準入力は使っていないようなので、削除するべきです。
・fopenの返り値がNULLかどうかをチェックしていないため、ファイルオープンに失敗すると危険です。
 fopenの直後にチェックを追加し、NULLだったら処理を終了するようにするといいでしょう。
・/* 隣接行列の初期化*/ のループにおいて、N要素しか無い配列の添字Nにアクセスしているため、
 範囲外アクセスで未定義動作になります。
 配列の要素数を十分確保するか、ループの条件を修正するべきです。
・変数 ave_length に対し初期化しないまま足し算をしています。これは未定義動作になります。
 足し算をする前にこの変数を初期化するべきです。
・関数warshall_floydの中身が、ワーシャル-フロイド法になっていないようです。
 足し算の結果が既存の値より有利な場合のみ、値を更新するようにした方がいいかもしれません。
 また、「辺がない場所を無限大に初期化」という処理も無く、不適切な可能性があります。
・大きい配列が普通のローカル変数として確保されているため、スタックオーバーフローになる可能性があります。
 以上の点を直してもエラーが解消しない場合、静的変数(static)か動的確保(malloc)に切り替えるといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

返信

“C言語何でも質問掲示板” へ戻る