c言語 セグメンテーション違反の原因を知りたいです

Question

グラフの点連結度を求めたいのですがセグメンテーション違反が発生してしまいその原因が分からないので質問させていただきました。

実行結果

N = 8, M = 16
01011100
10101100
01010011
10100011
11000101
11001010
00110101
00111010
v0: 4　v1: 4　v2: 4　v3: 4　v4: 4　v5: 4　v6: 4　v7: 4　
average degree: 4.000000
delta = 4
*****x=1*****
v[0] = 1
v[1] = 0
v[2] = 0
v[3] = 0
v[4] = 0
v[5] = 0
v[6] = 0
v[7] = 0
Segmentation fault

該当のソースコード

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LEN 256  //ファイル名の最大値

//連結か調べる
void visit( int v, int *yet, int N, int **adjacent 
) 
{ 
  int w; 
  yet[v] = 0; 
  for ( w=0; w<N; w++ ) 
    if ( adjacent[v][w] == 1 && yet[w] == 1 ) 
      visit( w, yet, N, adjacent ); 
} 
int connect_check( int N, int **adjacent ) 
{ 
  int    i, 
         *YetToVisit, 
         count = 0; 
  YetToVisit = ( int * )malloc( sizeof( int ) * N )
; 
  for ( i=0; i<N; i++ ) 
    YetToVisit[i] = 1; 
  for ( i=0; i<N; i++ ) 
    if ( YetToVisit[i] == 1 ) { 
      count++; 
      visit( i, YetToVisit, N, adjacent ); 
    } 
  free( YetToVisit ); 
  return ( count ); 
} 



//累乗を計算
int po(int x,int y){
  int result = 1;
  int i;
  for(i=0;i<y;i++){
    result = result * x;
  }
  return result;
}


int main(int argc, char *argv[]) {
  int i,j;
  int n1,n2; //点番号の一時保存
  int N,M = 0; //点の数、辺の数
  FILE *fp; //ファイルポインタ
  char fn[MAX_LEN]; //グラフファイル名
  int **adjacent; //隣接行列
  double dsum = 0; //次数の合計
  double dave = 0; //次数の平均

  int x,k,m;
  int val; //10進数表示
  int delta = 100; //最小次数
  int **Gdash; //(8-x)(8-x)の隣接行列
  int v[8] = {}; //2進数表示
  
  //実行時引数の数をチェック
  if(argc != 2){
  	fprintf(stderr, "Usage: %s graph_file\n", argv[0]);
  	exit(1);
  }
  
  //ファイル名をコピー	
  strcpy(fn, argv[1]); 
  
  //ファイルオープン
  if((fp = fopen(fn, "r")) == NULL){
  	fprintf(stderr, "%s cannot found./n", fn);
  	exit(1);
  }
  
  //1行目の読み込み
  fscanf(fp, "%d", &N);
  
  //隣接行列を動的に作成する N x N の2次元配列をmallocする
  adjacent = (int **)malloc(sizeof(int *) * N);
  for(i=0;i<N;i++){
  	adjacent[i] = (int *)malloc(sizeof(int) * N);
  	for(j=0;j<N;j++){
  	  adjacent[i][j] = 0;
  	}
  }
  
  //2行目以降の読み込み
  while(fscanf(fp, "%d %d", &n1,&n2) != EOF){
  	M++;
  	adjacent[n1][n2] = 1;
  	adjacent[n2][n1] = 1;
  	}
  
  fclose(fp);
  
  //隣接行列行列を表示
  printf("N = %d, M = %d\n", N,M);
  for(i=0;i<N;i++){
  	for(j=0;j<N;j++){
  	  printf("%d", adjacent[i][j]);
  	}
  	printf("\n");
  }  
  
  //各次数の計算 
  int d[N]; //次数を格納する
  for(i=0;i<N;i++){
    d[i] = 0;
  } 
  for(i=0;i<N;i++){
  	for(j=0;j<N;j++){
  	  if(adjacent[i][j] == 1){
  		d[i]++;
  		dsum++;
  	  } 
  	}
	if(delta > d[i]){
	  delta = d[i]; //最小次数の獲得
	}
  }
  dave = dsum/N; //次数の平均の計算
 
  //次数の表示
  for(i=0;i<N;i++){
    printf("v%d: %d　", i,d[i]);
  }
  printf("\n");
  printf("average degree: %lf\n", dave);

  printf("delta = %d\n",delta);//最小次数の表示

  for(x=1;x<delta;x++){
    printf("*****x=%d*****\n",x);
    for(val=1;val<256;val++){
      //Vx作成
      for(i=0;i<8;i++){
	v[i] = val % po(2,i+1) / po(2,i); //2進数の配列に変換
	printf("v[%d] = %d\n",i,v[i]);
	}

      //(8-x)*(8-x)の配列をmalloc
      Gdash = (int **)malloc(sizeof(int)*(8-x));
      for(i=0;i<8;i++){
	Gdash[i] = (int *)malloc(sizeof(int)*(8-x));
	for(j=0;j<8;j++){
	  Gdash[i][j] = 0;
	}
      }
      //Gdash作成
      k = m = 0;
      for(i=0;i<8;i++){
	m = 0; 
	for(j=0;j<8;j++){
	  if(v[i] == 0 && v[j] == 0){  //v[i]が消す必要のない場合 
	    if(adjacent[i][j] == 1){ //Gdashに1を代入
	      Gdash[k][m] = 1;
	    }
	    m++;
	  }
	}
	if(v[i] == 0 && v[j] == 0){  //v[i]が消す必要のない場合
	  k++;
	}
	}
      

      //Vxが分離集合の場合
      if(connect_check(8-x,Gdash) != 1){
	printf("Separated!\n");
	break;
	}

      //メモリの開放
      for(i=0;i<8;i++){
	free(Gdash[i]);
	Gdash[i] = NULL;
	}
	free(Gdash);
      }
  }


  
  //メモリの開放
  for(i=0;i<N;i++){
    free(adjacent[i]);
    adjacent[i] = NULL;
  }
  free(adjacent);
   
  return 0;
}

Comments

[tatsu99]

入力ファイルの内容も提示してください。

Answer 1

      //(8-x)*(8-x)の配列をmalloc
      Gdash = (int **)malloc(sizeof(int*)*(8-x));
      for(i=0;i<8;i++) {
        Gdash[i] = (int *)malloc(sizeof(int)*(8-x));
      }

Comments

[tamintya]

回答ありがとうございます。
無事解決することができました。

Answer 2

Gdash = (int **)malloc(sizeof(int)*(8-x));

ポインタなのにint分のサイズしか確保してないですよ。

Comments

[tamintya]

回答ありがとうございます。
見落としてしまっていました。