c言語 フラーリーのアルゴリズムによるオイラー小道の表示、橋確認時のエラー

Question

全ての次数が偶数かどうかでオイラーグラフかを判定し、オイラーグラフの場合はフラーリーのアルゴリズムを用いてオイラー小道を表示したいのですが、橋ではないはずのところで橋だと判定されてしまい最後まで表示されません。
その原因と解決方法を知りたいです。

実行結果

*****
pos = 0
next-hop candidate: 1 3 4 5
0-1 is not a bridge.
*****
pos = 1
next-hop candidate: 2 4 5
1-2 is not a bridge.
*****
pos = 2
next-hop candidate: 3 6 7
2-3 is not a bridge.
*****
pos = 3
next-hop candidate: 0 6 7
3-0 is not a bridge.
*****
pos = 0
next-hop candidate: 4 5
0-4 is not a bridge.
*****
pos = 4
next-hop candidate: 1 5 7
4-1 is not a bridge.
*****
pos = 1
next-hop candidate: 5
candidate is 1-5 only.
*****
pos = 5
next-hop candidate: 0 4 6
5-0 is a bridge.  Another candidate...
5-4 is a bridge.  Another candidate...
5-6 is a bridge.  Another candidate...
5-0 is a bridge.  Another candidate...
5-0 is a bridge.  Another candidate...
5-0 is a bridge.  Another candidate...
5-0 is a bridge.  Another candidate...
5-0 is a bridge.  Another candidate...
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 selection (int **adjacent, int next[], int min, int pos, int candidate){

  int check = 0;

  adjacent[pos][next[min]] = 0; //接続の消去
  adjacent[next[min]][pos] = 0; //接続の消去

  check = connect_check(8,adjacent); //連結か確認

  if(candidate == 1){ //候補が1つしかない場合
    printf("candidate is %d-%d only.\n",pos,next[min]);
    return min;
  }else if(check != 1){ //橋の場合
    printf("%d-%d is a bridge.  Another candidate...\n",pos,next[min]);//橋であることを表示
    adjacent[pos][next[min]] = 1; //接続の回復
    adjacent[next[min]][pos] = 1; //接続の回復

    selection(adjacent, next, min+1, pos, candidate); //次の候補で繰り返す
  }else{ //橋ではない場合
    printf("%d-%d is not a bridge.\n",pos,next[min]);
    return min;
   }
}


//経路の計算
int fleury (int **adjacent, int pos){
  int j;
  int min = 0; //候補の可能性のある最小の位置
  int candidate = 0; //候補の数
  int N = 8; //行列サイズ
  int next[8] = {10,0,0,0,0,0,0,0}; //候補の配列
  printf("*****\n");
  printf("pos = %d\n",pos);
  printf("next-hop candidate:");
  for(j=0;j<N;j++){ //移動先の候補を表示
    if(adjacent[pos][j] == 1){
      next[candidate] = j; //nextに点番号を入れる
      printf(" %d",j);
      candidate++;
    }
  }

  printf("\n");
  


  min = selection(adjacent, next, min, pos, candidate); //移動できる最初の点番号獲得


  if(next[0] != 10 ){ //候補が0個でないなら
    fleury(adjacent,next[min]);
  }

}


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; //次数の合計
  int count = 0; //奇数の次数の数

  int pos = 0; //現在の点

  //実行時引数の数をチェック
  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);
  
  //各次数の計算 
  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(d[i] % 2 == 1){ //奇数の場合
	  count++;
	}
  }

  if(count == 0){
    fleury(adjacent,pos); //経路の表示
  }else{
    printf("This is not Euler graph.\n");
  }
  
  //メモリの開放
  for(i=0;i<N;i++){
    free(adjacent[i]);
    adjacent[i] = NULL;
  }
  free(adjacent);
   
  return 0;
}

###読み込むファイル

8
0 3
3 7
4 1
2 6
3 2
2 7
0 4
0 1
5 6
3 6
1 5
0 5
1 2
4 7
6 7
5 4

Answer 1

ある節点につながる辺がすべて削除された場合を考えてみてください。

connect_checkにて、YetToVisitにすべて1を入れているので、つながるすべての辺が削除された節点についても1が入ることになります。そうなると、その接点は他とつながっていないので、常に非連結と判断されてしまうのではないでしょうか。

Comments

[tamintya]

回答ありがとうございます。
ご指摘通りでしたので、つながる全ての辺が削除された節点には1を代入しないようにしたところ求めている結果になりました。
ありがとうございました。