グラフの点連結度を求めたいのですが実行するとエラーが表示されてしまうのですが、その原因が分からないので質問させていただきました。
実行結果
N = 8, M = 16 01110111 10101100 11010100 10101000 01010100 11101011 10000101 10000110 v0: 6 v1: 4 v2: 4 v3: 3 v4: 3 v5: 6 v6: 3 v7: 3 average degree: 4.000000 delta = 3 *****x=1***** ( 0 ) Connected *** Error in `./a.out': double free or corruption (out): 0x0000000000602460 *** ======= Backtrace: ========= /lib64/libc.so.6(+0x740a5)[0x7f899edf00a5] ・ ・ ・
該当のソースコード
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 int w; 11 yet[v] = 0; 12 for ( w=0; w<N; w++ ) 13 if ( adjacent[v][w] == 1 && yet[w] == 1 ) 14 visit( w, yet, N, adjacent ); 15} 16int connect_check( int N, int **adjacent ) 17{ 18 int i, 19 *YetToVisit, 20 count = 0; 21 YetToVisit = ( int * )malloc( sizeof( int ) * N ) 22; 23 for ( i=0; i<N; i++ ) 24 YetToVisit[i] = 1; 25 for ( i=0; i<N; i++ ) 26 if ( YetToVisit[i] == 1 ) { 27 count++; 28 visit( i, YetToVisit, N, adjacent ); 29 } 30 free( YetToVisit ); 31 return ( count ); 32} 33 34 35 36//累乗を計算 37int po(int x,int y){ 38 int result = 1; 39 int i; 40 for(i=0;i<y;i++){ 41 result = result * x; 42 } 43 return result; 44} 45 46 47int main(int argc, char *argv[]) { 48 int i,j; 49 int n1,n2; //点番号の一時保存 50 int N,M = 0; //点の数、辺の数 51 FILE *fp; //ファイルポインタ 52 char fn[MAX_LEN]; //グラフファイル名 53 int **adjacent; //隣接行列 54 double dsum = 0; //次数の合計 55 double dave = 0; //次数の平均 56 57 int x,k,m; 58 int val; //10進数表示 59 int delta = 100; //最小次数 60 int **Gdash; //(8-x)(8-x)の隣接行列 61 int v[8] = {}; //2進数表示 62 int count = 0; 63 int check = 0; 64 65 //実行時引数の数をチェック 66 if(argc != 2){ 67 fprintf(stderr, "Usage: %s graph_file\n", argv[0]); 68 exit(1); 69 } 70 71 //ファイル名をコピー 72 strcpy(fn, argv[1]); 73 74 //ファイルオープン 75 if((fp = fopen(fn, "r")) == NULL){ 76 fprintf(stderr, "%s cannot found./n", fn); 77 exit(1); 78 } 79 80 //1行目の読み込み 81 fscanf(fp, "%d", &N); 82 83 //隣接行列を動的に作成する N x N の2次元配列をmallocする 84 adjacent = (int **)malloc(sizeof(int *) * N); 85 for(i=0;i<N;i++){ 86 adjacent[i] = (int *)malloc(sizeof(int) * N); 87 for(j=0;j<N;j++){ 88 adjacent[i][j] = 0; 89 } 90 } 91 92 //2行目以降の読み込み 93 while(fscanf(fp, "%d %d", &n1,&n2) != EOF){ 94 M++; 95 adjacent[n1][n2] = 1; 96 adjacent[n2][n1] = 1; 97 } 98 99 fclose(fp); 100 101 //隣接行列行列を表示 102 printf("N = %d, M = %d\n", N,M); 103 for(i=0;i<N;i++){ 104 for(j=0;j<N;j++){ 105 printf("%d", adjacent[i][j]); 106 } 107 printf("\n"); 108 } 109 110 //各次数の計算 111 int d[N]; //次数を格納する 112 for(i=0;i<N;i++){ 113 d[i] = 0; 114 } 115 for(i=0;i<N;i++){ 116 for(j=0;j<N;j++){ 117 if(adjacent[i][j] == 1){ 118 d[i]++; 119 dsum++; 120 } 121 } 122 if(delta > d[i]){ 123 delta = d[i]; //最小次数の獲得 124 } 125 } 126 dave = dsum/N; //次数の平均の計算 127 128 //次数の表示 129 for(i=0;i<N;i++){ 130 printf("v%d: %d ", i,d[i]); 131 } 132 printf("\n"); 133 printf("average degree: %lf\n", dave); 134 135 printf("delta = %d\n",delta);//最小次数の表示 136 137 for(x=1;x<delta;x++){ 138 printf("*****x=%d*****\n",x); 139 for(val=1;val<256;val++){ 140 //Vx作成 141 for(i=0;i<8;i++){ 142 v[i] = val % po(2,i+1) / po(2,i); //2進数の配列に変換 143 } 144 145 //Vx内の要素数確認 146 count = 0; 147 for(i=0;i<8;i++){ 148 if(v[i] == 1) count++; 149 } 150 151 //(8-x)*(8-x)の配列をmalloc 152 Gdash = (int **)malloc(sizeof(int*)*(8-x)); 153 for(i=0;i<8;i++){ 154 Gdash[i] = (int *)malloc(sizeof(int)*(8-x)); 155 for(j=0;j<8;j++){ 156 Gdash[i][j] = 0; 157 } 158 } 159 //Gdash作成 160 k = m = 0; 161 if(x == count){ 162 for(i=0;i<8;i++){ 163 m = 0; 164 for(j=0;j<8;j++){ 165 if(v[i] == 0 && v[j] == 0){ //v[i]が消す必要のない場合 166 if(adjacent[i][j] == 1){ //Gdashに1を代入 167 Gdash[k][m] = 1; 168 } 169 m++; 170 } 171 } 172 if(v[i] == 0){ //v[i]が消す必要のない場合 173 k++; 174 } 175 } 176 177 //Vxが分離集合の場合 178 if(connect_check(8-x,Gdash) != 1){ 179 printf("("); 180 for(i=0;i<8;i++){ 181 if(v[i] == 1) printf(" %d",i); 182 } 183 printf(" ) Separated!!\n"); 184 check++; 185 break; 186 }else{//分離集合ではなかった場合 187 printf("("); 188 for(i=0;i<8;i++){ 189 if(v[i] == 1) printf(" %d",i); 190 } 191 printf(" ) Connected\n"); 192 } 193 } 194 //メモリの開放 195 for(i=0;i<8-x;i++){ 196 free(Gdash[i]); 197 } 198 free(Gdash); 199 } 200 201 if(check == 1) break; 202 } 203 204 if(x != delta){ 205 printf("\n"); 206 printf("k(G) = %d\n", x); 207 printf("Separating set = ("); 208 for(i=0;i<8;i++){ 209 if(v[i] == 1) printf(" %d",i); 210 } 211 printf(" )\n"); 212 }else{ 213 printf("\n"); 214 printf("k(G) = %d (=mindegree)\n", x); 215 } 216 217 //メモリの開放 218 for(i=0;i<N;i++){ 219 free(adjacent[i]); 220 } 221 free(adjacent); 222 223 return 0; 224}
回答1件
あなたの回答
tips
プレビュー