質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
87.20%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

解決済

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

tamintya
tamintya

総合スコア34

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

1回答

-1評価

0クリップ

231閲覧

投稿2022/06/18 07:27

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

実行結果

***** 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

該当のソースコード

C

#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

良い質問の評価を上げる

以下のような質問は評価を上げましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

気になる質問をクリップする

クリップした質問は、後からいつでもマイページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

  • プログラミングに関係のない質問
  • やってほしいことだけを記載した丸投げの質問
  • 問題・課題が含まれていない質問
  • 意図的に内容が抹消された質問
  • 過去に投稿した質問と同じ内容の質問
  • 広告と受け取られるような投稿

評価を下げると、トップページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

まだ回答がついていません

会員登録して回答してみよう

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
87.20%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問

同じタグがついた質問を見る

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。