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

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

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

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

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

Q&A

解決済

有向グラフの強連結判定を正しく行うことができない

退会済みユーザー

退会済みユーザー

総合スコア0

C

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

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

1回答

0グッド

0クリップ

1202閲覧

投稿2021/11/28 13:19

編集2021/11/28 13:31

前提・実現したいこと

隣接行列が描かれたdatファイルを読み込んで、それをdot形式で描いた有向グラフが強連結であるか否かを判定するプログラムを作成しているのですが、強連結であるはずのグラフも「強連結ではありません」と出てしまいます。きちんと強連結のグラフに対して強連結と表示させるようにしたいです。find_path()の部分を作成したのですがどこか問題があるのでしょうか。

強連結である有向グラフ
イメージ説明

イメージ説明

発生している問題・エラーメッセージ

強連結であるはずのグラフも「強連結ではありません」と表示されてしまう。

該当のソースコード

#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define N 100 #define boolean int #define true 1 #define false 0 typedef boolean adjmatrix[N][N]; typedef int vindex; typedef struct edgecell{ vindex destination; struct edgecell *next; } edgecell; typedef edgecell * vertices[N]; typedef struct{ int vertex_num; int edge_num; vertices vtop; }graph; int read_adjacency_matrix(char *datafile, adjmatrix mat){ FILE *fp; int vertex_num; vindex src, dest; fp = fopen( datafile, "r" ); fscanf( fp, "%d\n", &vertex_num ); if( vertex_num > N ){ fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N); exit(1); } for (src = 0; src < vertex_num; src++){ for(dest = 0; dest < vertex_num; dest++){ fscanf( fp, "%d\n", &mat[src][dest] ); } } fclose( fp ); return vertex_num; } void add_edge(graph *g, vindex src, vindex dest){ edgecell *edge = (edgecell *)malloc(sizeof(edgecell)); edge->destination = dest; edge->next = g->vtop[src]; g->vtop[src] = edge; } void translate_into_graph(adjmatrix mat, graph *g){ vindex i,j; for(i = 0; i < g->vertex_num; i++){ g->vtop[i] = NULL; } for(i = 0; i < g->vertex_num; i++){ for(j = 0; j < g->vertex_num; j++){ if (mat[i][j] == 1) add_edge(g, i, j); } } } void find_path(adjmatrix mat, graph *g){ vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0; vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num]; A[src][dest] = 0; B[src][dest2] = mat[src][dest]; C[dest2][dest] = mat[src][dest]; for(x = 0; x < g->vertex_num; x++){ for(src = 0; src < g->vertex_num; src++){ for(dest = 0; dest < g->vertex_num; dest++){ for(dest2 = 0; dest2 < g->vertex_num; dest2++){ A[src][dest] += B[src][dest2] * C[dest2][dest]; B[src][dest2] = A[src][dest]; } } } } for(y = 0; y < g->vertex_num; y++){ if(A[y][y] == 1){ z++; } } if(z == g->vertex_num){ printf("強連結です\n"); } else{ printf("強連結ではありません\n"); } } void print_graph(graph *g){ vindex v; printf("digraph G {\n"); printf(" size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n"); for(v = 0; v < g->vertex_num; v++){ edgecell *edge; for(edge = g->vtop[v]; edge != NULL; edge = edge->next){ printf(" %d -> %d;\n", v+1, edge->destination+1); } } printf("}\n"); } void free_graph(graph *g){ vindex v; for (v = 0; v < g->vertex_num; v++){ edgecell *edge, *next_edge; for(edge = g->vtop[v]; edge != NULL; edge = next_edge){ next_edge = edge->next; free( edge ); } } } int main( int argc, char *argv[] ){ char *datafile; adjmatrix a; graph g; if ( argc <= 1 ){ fprintf( stderr, "##### ファイルを指定してください\n"); return 1; } datafile = argv[1]; g.vertex_num = read_adjacency_matrix( datafile, a ); translate_into_graph( a, &g ); find_path( a, &g ); free_graph( &g ); return 0; }

補足情報(FW/ツールのバージョンなど)

C言語、Cygwin64

以下のような質問にはグッドを送りましょう

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

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

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

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

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

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

2021/11/29 03:39

こちらの質問が他のユーザーから「過去の低評価」という指摘を受けました。

jimbe

2021/11/28 14:01

ご提示の例のデータはどのようなファイルになっているのでしょうか。 そして、そのファイルを処理する場合、 find_path 内においてそのデータが各変数内でどのように変化していき、どの行の段階でどの変数がどのような値になっているはずが、実際にはどのような値になっているのでしょうか。
退会済みユーザー

退会済みユーザー

2021/11/28 14:56

datファイルの内容は、上の例は 10 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 下の例は 10 0 0 1 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 となっています。 最終的にどちらの例とも z = 10となるはずが、上の例は3、下の例は5となっています。
jimbe

2021/11/28 15:41

アルゴリズムは全く分からないのですが、2次元配列 C が値を入れずに使用していますが、式は合っているのでしょうか。
退会済みユーザー

退会済みユーザー

2021/11/28 16:21

具体的にどういうことでしょうか?
jimbe

2021/11/28 18:06

計算毎に各配列の値を表示するようにして確認しては如何でしょうか。

回答1

1

ベストアンサー

チエブクロに同じコードの質問が載っています。

https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14138814419

見た所、 z++ する if 文の条件式が異なるようです。


各配列の表示関数(printMat,print10x10)を作って find_path の計算の前後で表示してみては如何でしょう。
想定した値が表示されるでしょうか。

c

1void printMat(int a[N][N]) { 2 printf("mat -----\n"); 3 for(int i=0; i<10; i++) { 4 for(int j=0; j<10; j++) { 5 printf(",%d"+(j==0?1:0),a[i][j]); 6 } 7 printf("\n"); 8 } 9} 10void print10x10(char *prompt, int a[10][10]) { 11 printf("%s -----\n",prompt); 12 for(int i=0; i<10; i++) { 13 for(int j=0; j<10; j++) { 14 printf(",%d"+(j==0?1:0),a[i][j]); 15 } 16 printf("\n"); 17 } 18} 19void find_path(adjmatrix mat, graph *g){ 20 vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0; 21 vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num]; 22 A[src][dest] = 0; 23 B[src][dest2] = mat[src][dest]; 24 C[dest2][dest] = mat[src][dest]; 25 26 printf("g->vertex_num=%d\n",g->vertex_num); 27 28 printMat(mat); 29 print10x10("A",A); 30 print10x10("B",B); 31 print10x10("C",C); 32 33 for(x = 0; x < g->vertex_num; x++){ 34 for(src = 0; src < g->vertex_num; src++){ 35 for(dest = 0; dest < g->vertex_num; dest++){ 36 for(dest2 = 0; dest2 < g->vertex_num; dest2++){ 37 A[src][dest] += B[src][dest2] * C[dest2][dest]; 38 B[src][dest2] = A[src][dest]; 39 } 40 } 41 } 42 } 43 44 print10x10("after A",A); 45 46 for(y = 0; y < g->vertex_num; y++){ 47 if(A[y][y] >= 1){ 48 z++; 49 } 50 } 51 52 printf("z=%d\n",z); 53 54 if(z == g->vertex_num){ 55 printf("強連結です\n"); 56 } 57 58 else{ 59 printf("強連結ではありません\n"); 60 } 61}

ご質問本文のコードに単純に節毎にパスを探すコードを加えて、マクロ定義でオリジナルに戻せるように書き替えてみました。

c

1#include <stdio.h> 2#include <stdlib.h> 3#include <malloc.h> 4 5#define TERATAIL371379 6 7#ifdef TERATAIL371379 8#include <memory.h> 9#endif 10 11#define N 100 12 13#define boolean int 14#define true 1 15#define false 0 16typedef boolean adjmatrix[N][N]; 17 18typedef int vindex; 19 20typedef struct edgecell{ 21 vindex destination; 22 struct edgecell *next; 23} 24 edgecell; 25 26typedef edgecell * vertices[N]; 27 28typedef struct{ 29 int vertex_num; 30 int edge_num; 31 vertices vtop; 32}graph; 33 34int read_adjacency_matrix(char *datafile, adjmatrix mat){ 35 FILE *fp; 36 int vertex_num; 37 vindex src, dest; 38 39 fp = fopen( datafile, "r" ); 40 fscanf( fp, "%d\n", &vertex_num ); 41 if( vertex_num > N ){ 42 fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N); 43 exit(1); 44 } 45 for (src = 0; src < vertex_num; src++){ 46 for(dest = 0; dest < vertex_num; dest++){ 47 fscanf( fp, "%d\n", &mat[src][dest] ); 48 } 49 } 50 fclose( fp ); 51 return vertex_num; 52} 53 54void add_edge(graph *g, vindex src, vindex dest){ 55 edgecell *edge = (edgecell *)malloc(sizeof(edgecell)); 56 edge->destination = dest; 57 edge->next = g->vtop[src]; 58 g->vtop[src] = edge; 59} 60 61void translate_into_graph(adjmatrix mat, graph *g){ 62 vindex i,j; 63 for(i = 0; i < g->vertex_num; i++){ 64 g->vtop[i] = NULL; 65 } 66 67 for(i = 0; i < g->vertex_num; i++){ 68 for(j = 0; j < g->vertex_num; j++){ 69 if (mat[i][j] == 1) 70 add_edge(g, i, j); 71 } 72 } 73} 74 75#ifdef TERATAIL371379 76//i から goal への経路を探す. 有ったら true 77boolean find_path_sub(adjmatrix mat, int vertex_num, int goal, int i, boolean *treated) { 78 if(mat[i][goal]) return true; 79 80 treated[i] = true; 81 for(int j=0; j<vertex_num; j++) { 82 if(mat[i][j] && !treated[j]) { 83 if(find_path_sub(mat,vertex_num,goal,j,treated)) return true; 84 } 85 } 86 return false; 87} 88 89//mat のうち、 vertex_num × vertex_num の範囲の隣接行列がグラフとして強連結かを表示 90void find_path(adjmatrix mat, int vertex_num) { 91 int found = true; 92 boolean treated[vertex_num]; 93 94 for(int i=0; i<vertex_num && found; i++) { 95 found = false; 96 memset(treated, false, sizeof(treated)); 97 for(int j=0; j<vertex_num && !found; j++) { 98 if(mat[i][j]) { 99 found = find_path_sub(mat,vertex_num,i,j,treated); 100 } 101 } 102 } 103 104 if(found) { 105 printf("強連結です\n"); 106 } else { 107 printf("強連結ではありません\n"); 108 } 109} 110#else 111void find_path(adjmatrix mat, graph *g){ 112 vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0; 113 vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num]; 114 A[src][dest] = 0; 115 B[src][dest2] = mat[src][dest]; 116 C[dest2][dest] = mat[src][dest]; 117 118 for(x = 0; x < g->vertex_num; x++){ 119 for(src = 0; src < g->vertex_num; src++){ 120 for(dest = 0; dest < g->vertex_num; dest++){ 121 for(dest2 = 0; dest2 < g->vertex_num; dest2++){ 122 A[src][dest] += B[src][dest2] * C[dest2][dest]; 123 B[src][dest2] = A[src][dest]; 124 } 125 } 126 } 127 } 128 129 for(y = 0; y < g->vertex_num; y++){ 130 if(A[y][y] == 1){ 131 z++; 132 } 133 } 134 135 if(z == g->vertex_num){ 136 printf("強連結です\n"); 137 } 138 139 else{ 140 printf("強連結ではありません\n"); 141 } 142} 143#endif 144 145void print_graph(graph *g){ 146 vindex v; 147 printf("digraph G {\n"); 148 printf(" size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n"); 149 for(v = 0; v < g->vertex_num; v++){ 150 edgecell *edge; 151 for(edge = g->vtop[v]; edge != NULL; edge = edge->next){ 152 printf(" %d -> %d;\n", v+1, edge->destination+1); 153 } 154 } 155 printf("}\n"); 156} 157 158void free_graph(graph *g){ 159 vindex v; 160 for (v = 0; v < g->vertex_num; v++){ 161 edgecell *edge, *next_edge; 162 for(edge = g->vtop[v]; edge != NULL; edge = next_edge){ 163 next_edge = edge->next; 164 free( edge ); 165 } 166 } 167} 168 169int main( int argc, char *argv[] ){ 170 char *datafile; 171 adjmatrix a; 172 graph g; 173 174 if ( argc <= 1 ){ 175 fprintf( stderr, "##### ファイルを指定してください\n"); 176 return 1; 177 } 178 datafile = argv[1]; 179 //datafile = "371379sample1.dat"; //テスト用 ☆型 180 181 g.vertex_num = read_adjacency_matrix( datafile, a ); 182 translate_into_graph( a, &g ); 183 184#ifdef TERATAIL371379 185 find_path( a, g.vertex_num ); 186#else 187 find_path( a, &g ); 188#endif 189 190 free_graph( &g ); 191 return 0; 192}

投稿2021/11/28 15:55

編集2021/11/30 02:38
jimbe

総合スコア10821

退会済みユーザー👍を押しています

良いと思った回答にはグッドを送りましょう。
グッドが多くついた回答ほどページの上位に表示されるので、他の人が素晴らしい回答を見つけやすくなります。

下記のような回答は推奨されていません。

  • 間違っている回答
  • 質問の回答になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

このような回答には修正を依頼しましょう。

回答へのコメント

退会済みユーザー

退会済みユーザー

2021/11/28 16:22

その部分は修正しましたが、やはり正しく動かないようです。
jimbe

2021/11/28 18:53 編集

回答にデバッグ用コードの例を追加しました。 各変数の値が計算前後で想定通りの値になっているか確認してみてください。
退会済みユーザー

退会済みユーザー

2021/11/29 01:11

after Aではマイナスの値が多く、z++される条件であるA[y][y] >= 1を満たしているものが少ないことが分かりました。また、A[y][y] だとA[0][0], A[1][1], ... などと配列の全てを調べることができないように感じるのですが、他の部分を調べるにはどうすれば良いでしょうか。
jimbe

2021/11/29 03:31

このアルゴリズムでマイナス値は出るものなのでしょうか。 そもそも、計算前でも A や B 、C にマイナスの値などが見られると思います(しかも実行する毎に違う値だったりします)が、それで良いのでしょうか? z をカウントしている for で、 y の価は (vertex_num が 10 なら ) 0~9 となります。従って、 A[y][y] であれば A[0][0],A[1][1],…,A[8][8],A[9][9] の全 9 箇所、イメージ的には二次元配列の左上から右下への斜めの範囲を判定している事になります。 これは、そうなるように debcold さんが書かれたのではないのでしょうか?
退会済みユーザー

退会済みユーザー

2021/11/29 03:43

すみません、自分でもなぜマイナス値が出るのか分かりません。 そうなるように書いたのですが、全部を調べようとして二重ループにすると逆に多過ぎになってしまいます。
jimbe

2021/11/29 04:34 編集

確認したいのは、A,B,C 各2次元配列の計算前の各要素値は、どんな状態であるという前提のアルゴリズムなのかということです。 例えば A は全て 0 で B や C は mat の 10x10 範囲の値のコピーである…とかです。 プログラムはそのような前提も含めて書く必要があり、(表示してみて)前提と異なっているならば、前提をまず達成するコードを書くことがプログラムを作る上での基本です。 > 自分でもなぜマイナス値が出るのか分かりません。 c におきましての基本は、変数の宣言は場所の確保だけであり、中身は "不定" です。ですので、 A, B, C 各配列も最初は何が入っているか分かりません。 A でいいますと、 A[src][dest]=0 により、 src=0,dest=0 で A[0][0] だけは 0 となりますが、 A の他の 99 個の要素の値は以前 "不定" なままです。 > 全部を調べようとして二重ループにすると逆に多過ぎになってしまいます 何が「多過ぎ」になるのでしょうか。 そもそも A の各要素の値が "想定" 通りかどうか、というか "想定" そのものがされているのかも分かりませんが、とにかく計算の前提もコードとして達成できていなければ、結果をどう求めようとしても "想定" 通りにはならないでしょう。 どこかに出かけようとして、そもそも進む方向が間違っているのにいくら道を "想定" 通りに曲がったところで、目的には着けません。
退会済みユーザー

退会済みユーザー

2021/11/29 04:28

A は全て0, B,C は0または1のみで構成された10×10行列にしたいです。 Aは全て0にすることができましたが、B, C のイコールである mat[src][dest]を0,1のみにするにはどうすれば良いでしょうか。 多過ぎなのは「z」です。
jimbe

2021/11/29 04:49 編集

> B, C のイコールである mat[src][dest]を0,1のみにする 表現の意味するところがイメージ出来ません。 デバッグ用として入れて頂いた print10x10 の表示に基づいた場合、「Aは全て0にすることができました」ということは A は A ----- 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 と表示されたのだと思います。 では、 B や C はどのように表示されたいのでしょうか。(☆型の例の場合で結構です。)
退会済みユーザー

退会済みユーザー

2021/11/29 05:07 編集

グラフの上の例であればBは 0,0,0,0,1,0,1,1,1,1 1,1,1,1,1,0,0,0,1,0 1,1,1,1,1,0,1,1,1,1 1,0,0,0,1,1,1,1,1,1 1,0,0,0,1,0,1,0,1,0 1,1,1,0,1,0,0,0,0,0 0,0,0,1,1,0,1,0,1,0 0,0,0,0,1,1,1,0,0,0 0,0,0,0,0,0,1,0,0,0 1,1,0,0,0,0,0,0,0,0 Cは 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 1,1,0,0,0,0,0,0,0,0 1,1,0,0,0,0,0,0,0,0 0,0,1,1,1,1,1,1,1,0 1,1,0,0,0,0,0,0,0,0 1,0,1,0,1,0,1,0,0,0 と表示されるようにしたいです。所々では0,1のみになっているのですが、大きすぎる値なども表示されているため、そこの部分を0,1のみにしたいです。
jimbe

2021/11/29 05:01

大分具体的になってきましたが、ご提示のデータは mat のデータとも大分異なりますね。 (B のほうが 11 列ありますけども ^^; ) 恐らく mat を元にしてそうなると思うのですが、どうやったら求まるのでしょうか。
退会済みユーザー

退会済みユーザー

2021/11/29 05:14

printfして得られたB,Cを見て0でない部分を1に変えたものを提示しました。 BとCを掛けて単位行列の形になれば強連結と判定するようにしたいです。
jimbe

2021/11/29 05:19

> printfして得られたB,Cを見て0でない部分を1に変えたものを提示しました いえ、それは意味がありません。現状 B, C として表示されているものは、メモリに残っている "ゴミ" です。 必要なのは「アルゴリズム上での B と C の初期値」です。
退会済みユーザー

退会済みユーザー

2021/11/29 06:04 編集

for文によりループを作るように書き換えるとBとCが0,1のみとなりました。 ここから最終的なAを単位行列にするにはどうすれば良いでしょうか。
jimbe

2021/11/29 06:47

こちらには B, C がどのような値になったのか全く分かりませんが…。 何度も言いますが、私はこのアルゴリズムは分かりません。ですので、ABC 各変数にアルゴリズムの想定通りの初期値が設定されたのなら、後は計算結果がどうなのかは判断できません。 debcold さんご自身が、この課題がこのアルゴリズムで出来ると判断され、そのアルゴリズムを c で書いているはずです。 それが「どうすれば」とはどういうことでしょう。
退会済みユーザー

退会済みユーザー

2021/11/29 07:04

B ----- 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 1,1,1,1,1,1,1,1,1,1 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 0,0,0,0,0,0,0,0,0,0 C ----- 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 0,0,1,0,0,0,0,0,0,0 となりました。これでは掛けても単位行列にならないのでこれらを掛けると単位行列になるようにしたいです。 for(src = 0; src < g->vertex_num; src++){ for(dest = 0; dest < g->vertex_num; dest++){ A[src][dest] = 0; } } for(src = 0; src < g->vertex_num; src++){ for(dest2 = 0; dest2 < g->vertex_num; dest2++){ for(dest = 0; dest < g->vertex_num; dest++){ B[src][dest2] = mat[src][dest]; } } } for(dest2 = 0; dest2 < g->vertex_num; dest2++){ for(dest = 0; dest < g->vertex_num; dest++){ for(src = 0; src < g->vertex_num; src++){ C[dest2][dest] = mat[src][dest]; } } } コードを上のようにした結果BとCが上のようになったのですが、どこかまずい点はあるでしょうか。
jimbe

2021/11/29 13:13

どうもお使いのアルゴリズムが分かりませんので、単純に探す形のサンプルコードを回答に追加致しました。
退会済みユーザー

退会済みユーザー

2021/11/29 15:00 編集

ありがとうございます。これを読み込んだdatファイルに対して強連結判定をするようなプログラムにしたいのですが、どこを変更すれば良いでしょうか。 元のプログラムのread_adjacency_matrix()を使うことは分かっているのですが、それ以外には変更点はあるでしょうか。
jimbe

2021/11/29 15:35

ご提示のコードを修正するとしますと、 find_path 関数を交換(上書き)し、 find_path_sub 関数を追加、 main 関数で find_path( a, &g ); としている所を find_path( a, g.vertex_num ); とする感じでしょうか。
退会済みユーザー

退会済みユーザー

2021/11/29 22:46

すみません、その通りにしたのですが「強連結です」も「強連結ではありません」も表示されなくなってしまいました。
jimbe

2021/11/30 02:15

紛らわしい書き方をしてしまったかもしれません。 「ご提示のコード」というのは、 debcold さんのご質問本文の「該当のソースコード」のコードのことですが、間違っておられないでしょうか。
退会済みユーザー

退会済みユーザー

2021/11/30 02:27

はい、私が書いたコードにfind_path()の書き換え、find_path_sub()の追加、mainの書き換えを行った結果、「強連結です」も「強連結ではありません」も表示されません。
jimbe

2021/11/30 02:42

find_path は無限ループしていなければ必ずどちらかが表示されますから、プログラムは正常終了したのに表示されないとすれば、find_path の呼び出しがされていないと思われます。 また状況をご説明頂くのも時間も掛かりそうですしご質問と離れてしまいますので、回答に追加したコードをご質問本文のコードを編集したものに差し替えました。
退会済みユーザー

退会済みユーザー

2021/11/30 02:43

出来ました!本当にありがとうございました!
jimbe

2021/11/30 02:50

とりあえずは一安心ですが、 debcold さんのアルゴリズムの問題は全く分からないままです。 4 重ループで 3 つの行列(?)を使って判定する方法は、ネットのどこかに紹介されているでしょうか。ありましたら URL を教えて頂きたいのですが。
jimbe

2021/11/30 03:10

つまり、アルゴリズムとしても動作するのか分からないものを動かそうとしていたということですね。今後ご質問されることがあれば、そのような「元にした情報」等はご質問に予め書いておいて頂けると手間が省けるかと思います。 かなり遠回りしてしまいましたが、リンク先のアルゴリズムは忘れたほうが良さそうです。 おつかれさまでした。

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

ただいまの回答率
86.02%

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

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

質問する

関連した質問

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

C

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

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。