グラフの点連結度を求めたいのですがセグメンテーション違反が発生してしまいその原因が分からないので質問させていただきました。
実行結果
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
該当のソースコード
c言語
1#include <stdio.h> 2#include <string.h> 3#include <stdlib.h> 4 5#define MAX_LEN 256 //ファイル名の最大値 6 7//連結か調べる 8void visit( int v, int *yet, int N, int **adjacent 9) 10{ 11 int w; 12 yet[v] = 0; 13 for ( w=0; w<N; w++ ) 14 if ( adjacent[v][w] == 1 && yet[w] == 1 ) 15 visit( w, yet, N, adjacent ); 16} 17int connect_check( int N, int **adjacent ) 18{ 19 int i, 20 *YetToVisit, 21 count = 0; 22 YetToVisit = ( int * )malloc( sizeof( int ) * N ) 23; 24 for ( i=0; i<N; i++ ) 25 YetToVisit[i] = 1; 26 for ( i=0; i<N; i++ ) 27 if ( YetToVisit[i] == 1 ) { 28 count++; 29 visit( i, YetToVisit, N, adjacent ); 30 } 31 free( YetToVisit ); 32 return ( count ); 33} 34 35 36 37//累乗を計算 38int po(int x,int y){ 39 int result = 1; 40 int i; 41 for(i=0;i<y;i++){ 42 result = result * x; 43 } 44 return result; 45} 46 47 48int main(int argc, char *argv[]) { 49 int i,j; 50 int n1,n2; //点番号の一時保存 51 int N,M = 0; //点の数、辺の数 52 FILE *fp; //ファイルポインタ 53 char fn[MAX_LEN]; //グラフファイル名 54 int **adjacent; //隣接行列 55 double dsum = 0; //次数の合計 56 double dave = 0; //次数の平均 57 58 int x,k,m; 59 int val; //10進数表示 60 int delta = 100; //最小次数 61 int **Gdash; //(8-x)(8-x)の隣接行列 62 int v[8] = {}; //2進数表示 63 64 //実行時引数の数をチェック 65 if(argc != 2){ 66 fprintf(stderr, "Usage: %s graph_file\n", argv[0]); 67 exit(1); 68 } 69 70 //ファイル名をコピー 71 strcpy(fn, argv[1]); 72 73 //ファイルオープン 74 if((fp = fopen(fn, "r")) == NULL){ 75 fprintf(stderr, "%s cannot found./n", fn); 76 exit(1); 77 } 78 79 //1行目の読み込み 80 fscanf(fp, "%d", &N); 81 82 //隣接行列を動的に作成する N x N の2次元配列をmallocする 83 adjacent = (int **)malloc(sizeof(int *) * N); 84 for(i=0;i<N;i++){ 85 adjacent[i] = (int *)malloc(sizeof(int) * N); 86 for(j=0;j<N;j++){ 87 adjacent[i][j] = 0; 88 } 89 } 90 91 //2行目以降の読み込み 92 while(fscanf(fp, "%d %d", &n1,&n2) != EOF){ 93 M++; 94 adjacent[n1][n2] = 1; 95 adjacent[n2][n1] = 1; 96 } 97 98 fclose(fp); 99 100 //隣接行列行列を表示 101 printf("N = %d, M = %d\n", N,M); 102 for(i=0;i<N;i++){ 103 for(j=0;j<N;j++){ 104 printf("%d", adjacent[i][j]); 105 } 106 printf("\n"); 107 } 108 109 //各次数の計算 110 int d[N]; //次数を格納する 111 for(i=0;i<N;i++){ 112 d[i] = 0; 113 } 114 for(i=0;i<N;i++){ 115 for(j=0;j<N;j++){ 116 if(adjacent[i][j] == 1){ 117 d[i]++; 118 dsum++; 119 } 120 } 121 if(delta > d[i]){ 122 delta = d[i]; //最小次数の獲得 123 } 124 } 125 dave = dsum/N; //次数の平均の計算 126 127 //次数の表示 128 for(i=0;i<N;i++){ 129 printf("v%d: %d ", i,d[i]); 130 } 131 printf("\n"); 132 printf("average degree: %lf\n", dave); 133 134 printf("delta = %d\n",delta);//最小次数の表示 135 136 for(x=1;x<delta;x++){ 137 printf("*****x=%d*****\n",x); 138 for(val=1;val<256;val++){ 139 //Vx作成 140 for(i=0;i<8;i++){ 141 v[i] = val % po(2,i+1) / po(2,i); //2進数の配列に変換 142 printf("v[%d] = %d\n",i,v[i]); 143 } 144 145 //(8-x)*(8-x)の配列をmalloc 146 Gdash = (int **)malloc(sizeof(int)*(8-x)); 147 for(i=0;i<8;i++){ 148 Gdash[i] = (int *)malloc(sizeof(int)*(8-x)); 149 for(j=0;j<8;j++){ 150 Gdash[i][j] = 0; 151 } 152 } 153 //Gdash作成 154 k = m = 0; 155 for(i=0;i<8;i++){ 156 m = 0; 157 for(j=0;j<8;j++){ 158 if(v[i] == 0 && v[j] == 0){ //v[i]が消す必要のない場合 159 if(adjacent[i][j] == 1){ //Gdashに1を代入 160 Gdash[k][m] = 1; 161 } 162 m++; 163 } 164 } 165 if(v[i] == 0 && v[j] == 0){ //v[i]が消す必要のない場合 166 k++; 167 } 168 } 169 170 171 //Vxが分離集合の場合 172 if(connect_check(8-x,Gdash) != 1){ 173 printf("Separated!\n"); 174 break; 175 } 176 177 //メモリの開放 178 for(i=0;i<8;i++){ 179 free(Gdash[i]); 180 Gdash[i] = NULL; 181 } 182 free(Gdash); 183 } 184 } 185 186 187 188 //メモリの開放 189 for(i=0;i<N;i++){ 190 free(adjacent[i]); 191 adjacent[i] = NULL; 192 } 193 free(adjacent); 194 195 return 0; 196}
入力ファイルの内容も提示してください。

回答2件
あなたの回答
tips
プレビュー