回答編集履歴
4
サンプルコードを書き換え
answer
CHANGED
|
@@ -73,13 +73,17 @@
|
|
|
73
73
|
}
|
|
74
74
|
```
|
|
75
75
|
----
|
|
76
|
-
すいませんが、アルゴリズム的に正しいのか間違っているのかが確認出来ませんので、単純に各節に対して戻ってこれるかを再帰で探す形のサンプルプログラムを作りました。
|
|
77
|
-
|
|
76
|
+
ご質問本文のコードに単純に節毎にパスを探すコードを加えて、マクロ定義でオリジナルに戻せるように書き替えてみました。
|
|
78
|
-
現状で☆型の例で動作し、 #define SAMPLE2 のコメントを外すともう一方の例で動作します。
|
|
79
77
|
```c
|
|
80
78
|
#include <stdio.h>
|
|
81
79
|
#include <stdlib.h>
|
|
80
|
+
#include <malloc.h>
|
|
81
|
+
|
|
82
|
+
#define TERATAIL371379
|
|
83
|
+
|
|
84
|
+
#ifdef TERATAIL371379
|
|
82
85
|
#include <memory.h>
|
|
86
|
+
#endif
|
|
83
87
|
|
|
84
88
|
#define N 100
|
|
85
89
|
|
|
@@ -88,8 +92,64 @@
|
|
|
88
92
|
#define false 0
|
|
89
93
|
typedef boolean adjmatrix[N][N];
|
|
90
94
|
|
|
91
|
-
|
|
95
|
+
typedef int vindex;
|
|
92
96
|
|
|
97
|
+
typedef struct edgecell{
|
|
98
|
+
vindex destination;
|
|
99
|
+
struct edgecell *next;
|
|
100
|
+
}
|
|
101
|
+
edgecell;
|
|
102
|
+
|
|
103
|
+
typedef edgecell * vertices[N];
|
|
104
|
+
|
|
105
|
+
typedef struct{
|
|
106
|
+
int vertex_num;
|
|
107
|
+
int edge_num;
|
|
108
|
+
vertices vtop;
|
|
109
|
+
}graph;
|
|
110
|
+
|
|
111
|
+
int read_adjacency_matrix(char *datafile, adjmatrix mat){
|
|
112
|
+
FILE *fp;
|
|
113
|
+
int vertex_num;
|
|
114
|
+
vindex src, dest;
|
|
115
|
+
|
|
116
|
+
fp = fopen( datafile, "r" );
|
|
117
|
+
fscanf( fp, "%d\n", &vertex_num );
|
|
118
|
+
if( vertex_num > N ){
|
|
119
|
+
fprintf(stderr, "##### このプログラムが扱えるのは頂点数が%dまでのグラフです\n", N);
|
|
120
|
+
exit(1);
|
|
121
|
+
}
|
|
122
|
+
for (src = 0; src < vertex_num; src++){
|
|
123
|
+
for(dest = 0; dest < vertex_num; dest++){
|
|
124
|
+
fscanf( fp, "%d\n", &mat[src][dest] );
|
|
125
|
+
}
|
|
126
|
+
}
|
|
127
|
+
fclose( fp );
|
|
128
|
+
return vertex_num;
|
|
129
|
+
}
|
|
130
|
+
|
|
131
|
+
void add_edge(graph *g, vindex src, vindex dest){
|
|
132
|
+
edgecell *edge = (edgecell *)malloc(sizeof(edgecell));
|
|
133
|
+
edge->destination = dest;
|
|
134
|
+
edge->next = g->vtop[src];
|
|
135
|
+
g->vtop[src] = edge;
|
|
136
|
+
}
|
|
137
|
+
|
|
138
|
+
void translate_into_graph(adjmatrix mat, graph *g){
|
|
139
|
+
vindex i,j;
|
|
140
|
+
for(i = 0; i < g->vertex_num; i++){
|
|
141
|
+
g->vtop[i] = NULL;
|
|
142
|
+
}
|
|
143
|
+
|
|
144
|
+
for(i = 0; i < g->vertex_num; i++){
|
|
145
|
+
for(j = 0; j < g->vertex_num; j++){
|
|
146
|
+
if (mat[i][j] == 1)
|
|
147
|
+
add_edge(g, i, j);
|
|
148
|
+
}
|
|
149
|
+
}
|
|
150
|
+
}
|
|
151
|
+
|
|
152
|
+
#ifdef TERATAIL371379
|
|
93
153
|
//i から goal への経路を探す. 有ったら true
|
|
94
154
|
boolean find_path_sub(adjmatrix mat, int vertex_num, int goal, int i, boolean *treated) {
|
|
95
155
|
if(mat[i][goal]) return true;
|
|
@@ -124,37 +184,87 @@
|
|
|
124
184
|
printf("強連結ではありません\n");
|
|
125
185
|
}
|
|
126
186
|
}
|
|
187
|
+
#else
|
|
188
|
+
void find_path(adjmatrix mat, graph *g){
|
|
189
|
+
vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
|
|
190
|
+
vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
|
|
191
|
+
A[src][dest] = 0;
|
|
192
|
+
B[src][dest2] = mat[src][dest];
|
|
193
|
+
C[dest2][dest] = mat[src][dest];
|
|
127
194
|
|
|
195
|
+
for(x = 0; x < g->vertex_num; x++){
|
|
196
|
+
for(src = 0; src < g->vertex_num; src++){
|
|
197
|
+
for(dest = 0; dest < g->vertex_num; dest++){
|
|
198
|
+
for(dest2 = 0; dest2 < g->vertex_num; dest2++){
|
|
199
|
+
A[src][dest] += B[src][dest2] * C[dest2][dest];
|
|
200
|
+
B[src][dest2] = A[src][dest];
|
|
201
|
+
}
|
|
202
|
+
}
|
|
203
|
+
}
|
|
204
|
+
}
|
|
205
|
+
|
|
206
|
+
for(y = 0; y < g->vertex_num; y++){
|
|
207
|
+
if(A[y][y] == 1){
|
|
208
|
+
z++;
|
|
209
|
+
}
|
|
210
|
+
}
|
|
211
|
+
|
|
212
|
+
if(z == g->vertex_num){
|
|
213
|
+
printf("強連結です\n");
|
|
214
|
+
}
|
|
215
|
+
|
|
216
|
+
else{
|
|
217
|
+
printf("強連結ではありません\n");
|
|
218
|
+
}
|
|
219
|
+
}
|
|
220
|
+
#endif
|
|
221
|
+
|
|
222
|
+
void print_graph(graph *g){
|
|
223
|
+
vindex v;
|
|
224
|
+
printf("digraph G {\n");
|
|
225
|
+
printf(" size=\"14,10\"; node[fontsize=10,height=0.01,width=0.01]; edge[len=3.0];\n");
|
|
226
|
+
for(v = 0; v < g->vertex_num; v++){
|
|
227
|
+
edgecell *edge;
|
|
228
|
+
for(edge = g->vtop[v]; edge != NULL; edge = edge->next){
|
|
229
|
+
printf(" %d -> %d;\n", v+1, edge->destination+1);
|
|
230
|
+
}
|
|
231
|
+
}
|
|
232
|
+
printf("}\n");
|
|
233
|
+
}
|
|
234
|
+
|
|
235
|
+
void free_graph(graph *g){
|
|
236
|
+
vindex v;
|
|
237
|
+
for (v = 0; v < g->vertex_num; v++){
|
|
238
|
+
edgecell *edge, *next_edge;
|
|
239
|
+
for(edge = g->vtop[v]; edge != NULL; edge = next_edge){
|
|
240
|
+
next_edge = edge->next;
|
|
241
|
+
free( edge );
|
|
242
|
+
}
|
|
243
|
+
}
|
|
244
|
+
}
|
|
245
|
+
|
|
128
246
|
int main( int argc, char *argv[] ){
|
|
247
|
+
char *datafile;
|
|
129
|
-
adjmatrix
|
|
248
|
+
adjmatrix a;
|
|
249
|
+
graph g;
|
|
250
|
+
|
|
251
|
+
if ( argc <= 1 ){
|
|
252
|
+
fprintf( stderr, "##### ファイルを指定してください\n");
|
|
253
|
+
return 1;
|
|
254
|
+
}
|
|
255
|
+
datafile = argv[1];
|
|
256
|
+
//datafile = "371379sample1.dat"; //テスト用 ☆型
|
|
257
|
+
|
|
258
|
+
g.vertex_num = read_adjacency_matrix( datafile, a );
|
|
259
|
+
translate_into_graph( a, &g );
|
|
260
|
+
|
|
130
|
-
#
|
|
261
|
+
#ifdef TERATAIL371379
|
|
131
|
-
|
|
262
|
+
find_path( a, g.vertex_num );
|
|
132
|
-
{0,0,0,0,1,0,0,0,0,0},
|
|
133
|
-
{0,0,0,0,1,1,0,0,0,0},
|
|
134
|
-
{0,0,0,0,0,0,1,0,0,0},
|
|
135
|
-
{0,0,0,0,0,0,1,1,0,0},
|
|
136
|
-
{0,0,0,0,0,0,0,0,1,0},
|
|
137
|
-
{0,0,0,0,0,0,0,0,1,1},
|
|
138
|
-
{1,0,0,0,0,0,0,0,0,0},
|
|
139
|
-
{1,1,0,0,0,0,0,0,0,0},
|
|
140
|
-
{0,0,1,0,0,0,0,0,0,0},
|
|
141
263
|
#else
|
|
142
|
-
|
|
264
|
+
find_path( a, &g );
|
|
143
|
-
{0,0,0,0,1,1,0,0,0,0},
|
|
144
|
-
{0,0,0,0,1,0,0,0,0,0},
|
|
145
|
-
{0,0,0,0,0,0,0,1,0,0},
|
|
146
|
-
{0,0,0,0,0,0,1,0,0,0},
|
|
147
|
-
{0,0,0,0,0,0,0,1,0,1},
|
|
148
|
-
{0,0,0,0,0,0,0,0,1,0},
|
|
149
|
-
{1,1,0,0,0,0,0,0,0,0},
|
|
150
|
-
{1,0,0,0,0,0,0,0,0,0},
|
|
151
|
-
{0,1,0,1,0,0,0,0,0,0},
|
|
152
265
|
#endif
|
|
153
|
-
};
|
|
154
|
-
int vertex_num = 10;
|
|
155
266
|
|
|
156
|
-
|
|
267
|
+
free_graph( &g );
|
|
157
|
-
|
|
158
268
|
return 0;
|
|
159
269
|
}
|
|
160
270
|
```
|
3
脱字
answer
CHANGED
|
@@ -103,7 +103,7 @@
|
|
|
103
103
|
return false;
|
|
104
104
|
}
|
|
105
105
|
|
|
106
|
-
//mat のうち、 vertex_num × vertex_num の範囲の隣接行列が強連結を表示
|
|
106
|
+
//mat のうち、 vertex_num × vertex_num の範囲の隣接行列がグラフとして強連結かを表示
|
|
107
107
|
void find_path(adjmatrix mat, int vertex_num) {
|
|
108
108
|
int found = true;
|
|
109
109
|
boolean treated[vertex_num];
|
2
再帰で探すサンプルコードを追加
answer
CHANGED
|
@@ -71,4 +71,90 @@
|
|
|
71
71
|
printf("強連結ではありません\n");
|
|
72
72
|
}
|
|
73
73
|
}
|
|
74
|
+
```
|
|
75
|
+
----
|
|
76
|
+
すいませんが、アルゴリズム的に正しいのか間違っているのかが確認出来ませんので、単純に各節に対して戻ってこれるかを再帰で探す形のサンプルプログラムを作りました。
|
|
77
|
+
ファイル読み込みやプロットの部分は find_path には関係ありませんので、データを直書きしてあります。
|
|
78
|
+
現状で☆型の例で動作し、 #define SAMPLE2 のコメントを外すともう一方の例で動作します。
|
|
79
|
+
```c
|
|
80
|
+
#include <stdio.h>
|
|
81
|
+
#include <stdlib.h>
|
|
82
|
+
#include <memory.h>
|
|
83
|
+
|
|
84
|
+
#define N 100
|
|
85
|
+
|
|
86
|
+
#define boolean int
|
|
87
|
+
#define true 1
|
|
88
|
+
#define false 0
|
|
89
|
+
typedef boolean adjmatrix[N][N];
|
|
90
|
+
|
|
91
|
+
//#define SAMPLE2
|
|
92
|
+
|
|
93
|
+
//i から goal への経路を探す. 有ったら true
|
|
94
|
+
boolean find_path_sub(adjmatrix mat, int vertex_num, int goal, int i, boolean *treated) {
|
|
95
|
+
if(mat[i][goal]) return true;
|
|
96
|
+
|
|
97
|
+
treated[i] = true;
|
|
98
|
+
for(int j=0; j<vertex_num; j++) {
|
|
99
|
+
if(mat[i][j] && !treated[j]) {
|
|
100
|
+
if(find_path_sub(mat,vertex_num,goal,j,treated)) return true;
|
|
101
|
+
}
|
|
102
|
+
}
|
|
103
|
+
return false;
|
|
104
|
+
}
|
|
105
|
+
|
|
106
|
+
//mat のうち、 vertex_num × vertex_num の範囲の隣接行列が強連結を表示
|
|
107
|
+
void find_path(adjmatrix mat, int vertex_num) {
|
|
108
|
+
int found = true;
|
|
109
|
+
boolean treated[vertex_num];
|
|
110
|
+
|
|
111
|
+
for(int i=0; i<vertex_num && found; i++) {
|
|
112
|
+
found = false;
|
|
113
|
+
memset(treated, false, sizeof(treated));
|
|
114
|
+
for(int j=0; j<vertex_num && !found; j++) {
|
|
115
|
+
if(mat[i][j]) {
|
|
116
|
+
found = find_path_sub(mat,vertex_num,i,j,treated);
|
|
117
|
+
}
|
|
118
|
+
}
|
|
119
|
+
}
|
|
120
|
+
|
|
121
|
+
if(found) {
|
|
122
|
+
printf("強連結です\n");
|
|
123
|
+
} else {
|
|
124
|
+
printf("強連結ではありません\n");
|
|
125
|
+
}
|
|
126
|
+
}
|
|
127
|
+
|
|
128
|
+
int main( int argc, char *argv[] ){
|
|
129
|
+
adjmatrix adjmatrix = {
|
|
130
|
+
#ifndef SAMPLE2
|
|
131
|
+
{0,0,1,1,0,0,0,0,0,0},
|
|
132
|
+
{0,0,0,0,1,0,0,0,0,0},
|
|
133
|
+
{0,0,0,0,1,1,0,0,0,0},
|
|
134
|
+
{0,0,0,0,0,0,1,0,0,0},
|
|
135
|
+
{0,0,0,0,0,0,1,1,0,0},
|
|
136
|
+
{0,0,0,0,0,0,0,0,1,0},
|
|
137
|
+
{0,0,0,0,0,0,0,0,1,1},
|
|
138
|
+
{1,0,0,0,0,0,0,0,0,0},
|
|
139
|
+
{1,1,0,0,0,0,0,0,0,0},
|
|
140
|
+
{0,0,1,0,0,0,0,0,0,0},
|
|
141
|
+
#else
|
|
142
|
+
{0,0,1,1,0,0,0,0,0,0},
|
|
143
|
+
{0,0,0,0,1,1,0,0,0,0},
|
|
144
|
+
{0,0,0,0,1,0,0,0,0,0},
|
|
145
|
+
{0,0,0,0,0,0,0,1,0,0},
|
|
146
|
+
{0,0,0,0,0,0,1,0,0,0},
|
|
147
|
+
{0,0,0,0,0,0,0,1,0,1},
|
|
148
|
+
{0,0,0,0,0,0,0,0,1,0},
|
|
149
|
+
{1,1,0,0,0,0,0,0,0,0},
|
|
150
|
+
{1,0,0,0,0,0,0,0,0,0},
|
|
151
|
+
{0,1,0,1,0,0,0,0,0,0},
|
|
152
|
+
#endif
|
|
153
|
+
};
|
|
154
|
+
int vertex_num = 10;
|
|
155
|
+
|
|
156
|
+
find_path(adjmatrix, vertex_num);
|
|
157
|
+
|
|
158
|
+
return 0;
|
|
159
|
+
}
|
|
74
160
|
```
|
1
デバッグ例コード追加
answer
CHANGED
|
@@ -2,4 +2,73 @@
|
|
|
2
2
|
|
|
3
3
|
https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q14138814419
|
|
4
4
|
|
|
5
|
-
見た所、 z++ する if 文の条件式が異なるようです。
|
|
5
|
+
見た所、 z++ する if 文の条件式が異なるようです。
|
|
6
|
+
|
|
7
|
+
----
|
|
8
|
+
|
|
9
|
+
各配列の表示関数(printMat,print10x10)を作って find_path の計算の前後で表示してみては如何でしょう。
|
|
10
|
+
想定した値が表示されるでしょうか。
|
|
11
|
+
|
|
12
|
+
```c
|
|
13
|
+
void printMat(int a[N][N]) {
|
|
14
|
+
printf("mat -----\n");
|
|
15
|
+
for(int i=0; i<10; i++) {
|
|
16
|
+
for(int j=0; j<10; j++) {
|
|
17
|
+
printf(",%d"+(j==0?1:0),a[i][j]);
|
|
18
|
+
}
|
|
19
|
+
printf("\n");
|
|
20
|
+
}
|
|
21
|
+
}
|
|
22
|
+
void print10x10(char *prompt, int a[10][10]) {
|
|
23
|
+
printf("%s -----\n",prompt);
|
|
24
|
+
for(int i=0; i<10; i++) {
|
|
25
|
+
for(int j=0; j<10; j++) {
|
|
26
|
+
printf(",%d"+(j==0?1:0),a[i][j]);
|
|
27
|
+
}
|
|
28
|
+
printf("\n");
|
|
29
|
+
}
|
|
30
|
+
}
|
|
31
|
+
void find_path(adjmatrix mat, graph *g){
|
|
32
|
+
vindex src = 0, dest = 0, dest2 = 0, x = 0, y = 0, z = 0;
|
|
33
|
+
vindex A[g->vertex_num][g->vertex_num], B[g->vertex_num][g->vertex_num], C[g->vertex_num][g->vertex_num];
|
|
34
|
+
A[src][dest] = 0;
|
|
35
|
+
B[src][dest2] = mat[src][dest];
|
|
36
|
+
C[dest2][dest] = mat[src][dest];
|
|
37
|
+
|
|
38
|
+
printf("g->vertex_num=%d\n",g->vertex_num);
|
|
39
|
+
|
|
40
|
+
printMat(mat);
|
|
41
|
+
print10x10("A",A);
|
|
42
|
+
print10x10("B",B);
|
|
43
|
+
print10x10("C",C);
|
|
44
|
+
|
|
45
|
+
for(x = 0; x < g->vertex_num; x++){
|
|
46
|
+
for(src = 0; src < g->vertex_num; src++){
|
|
47
|
+
for(dest = 0; dest < g->vertex_num; dest++){
|
|
48
|
+
for(dest2 = 0; dest2 < g->vertex_num; dest2++){
|
|
49
|
+
A[src][dest] += B[src][dest2] * C[dest2][dest];
|
|
50
|
+
B[src][dest2] = A[src][dest];
|
|
51
|
+
}
|
|
52
|
+
}
|
|
53
|
+
}
|
|
54
|
+
}
|
|
55
|
+
|
|
56
|
+
print10x10("after A",A);
|
|
57
|
+
|
|
58
|
+
for(y = 0; y < g->vertex_num; y++){
|
|
59
|
+
if(A[y][y] >= 1){
|
|
60
|
+
z++;
|
|
61
|
+
}
|
|
62
|
+
}
|
|
63
|
+
|
|
64
|
+
printf("z=%d\n",z);
|
|
65
|
+
|
|
66
|
+
if(z == g->vertex_num){
|
|
67
|
+
printf("強連結です\n");
|
|
68
|
+
}
|
|
69
|
+
|
|
70
|
+
else{
|
|
71
|
+
printf("強連結ではありません\n");
|
|
72
|
+
}
|
|
73
|
+
}
|
|
74
|
+
```
|