teratail
回答率
85.30%
質問するログイン新規登録
トップに関する質問グラフを呼び出し、値を挿入する方法

編集履歴

質問編集履歴

5

エラー内容を訂正しました。

2021/11/10 00:14

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -131,8 +131,7 @@
131
131
 
132
132
  ### 試したこと、エラー内容
133
133
  エラーは出ず、実行はできているのですが、min_cの出力がされないです。
134
- また、以下の警告文が出てきます。
135
- ・'a'への書き込み中にバッファーオーバーランが発生しました:書き込み可能なサイズは'en*4'バイトですが、'en'バイトを書き込む可能性があります。
136
134
 
135
+
137
136
  ### 環境
138
137
  Visual Studio 2019 C++です

4

プログラムの訂正、エラー内容を訂正しました。

2021/11/10 00:14

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -22,7 +22,6 @@
22
22
  #include <algorithm>
23
23
  #include <list>
24
24
  #include <random>
25
- #include <numeric>
26
25
 
27
26
  using namespace std;
28
27
 
@@ -75,62 +74,65 @@
75
74
  }
76
75
  };
77
76
 
77
+
78
78
  //最小の被覆数を探索する関数(接続行列)
79
79
  void is_covering(con_matrix &con)
80
80
  {
81
81
  int vn = con.get_vertex_num(); // 頂点数
82
82
  int en = con.get_edge_num(); // 辺数
83
- int min_c[10] = {}; // 実験回数
83
+ int min_c[5] = {}; // 使用した頂点数
84
- int w = 0; // 値を挿入したカウント
84
+ int w = 0; // カウント
85
85
  int* a = new int[en];
86
+ a[en] = {};
86
87
  vector < vector<int>> matrix;
87
88
  con.set_random(1);
88
89
 
89
- for (int min = 0; min < 10; min++) {
90
+ for (int min = 0; min < 5; min++) {
90
91
  while( w < en){
91
92
  w = 0;
92
93
  int i = rand() % vn;
93
94
  for (int j = 0; j < en; j++) {
94
95
  if (a[j] == 0 && matrix[i][j] == 1) {
95
- a[i] = matrix[i][j];
96
+ a[j] = 1;
96
97
  }
97
98
  }
98
- 　　　　　　　　　　　　　for (int o = 0; o < en; o++) {
99
+ for (int o = 0; o < en; o++) {
99
- w = +a[o];
100
+ w = +a[o];
101
+ min_c[min] = +1;
100
- 　　　　　　　　　　　　　}
102
+ }
101
- min_c[min] = +1;
102
103
  }
103
104
  }
104
- for (int b = 0; b < 10; b++) {
105
+ for (int b = 0; b < 5; b++) {
105
106
  cout << min_c[b] << ",";
106
107
  }
107
108
  }
108
109
 
110
+
109
111
  int main()
110
112
  {
111
113
  const int n = 7; //頂点数
112
114
  double r = 0.5; //辺数の比率
113
115
  const int e = ((n * (n - 1) / 2) * r);
116
+ vector<int> con;
114
117
  int cover = 0; // 被覆数
115
118
  con_matrix am(n, e);
116
119
  am.set_random(1); //ランダムにグラフの接続行列を作る。引数は乱数シード
117
120
 
121
+
122
+
118
123
  cout << "頂点数 = " << n << endl;
119
124
  cout << "グラフの辺数 = " << e << endl;
120
125
  am.disp_connection();
121
126
  cout << endl;
122
-
123
127
  is_covering(am);
124
-
125
128
  return 0;
126
129
  }
127
130
  ```
128
131
 
129
132
  ### 試したこと、エラー内容
133
+ エラーは出ず、実行はできているのですが、min_cの出力がされないです。
134
+ また、以下の警告文が出てきます。
130
- 関数is_coveringにクラスcon_matrixの関数を書き込み、matrix[i][j] = 1であれば配列a[en]の要素を１にし、全要素がうまるまで繰り返すようにし、この行為を10回繰り返すようにしたのですが、出力されないです。(実行はできています。)
135
+ ・'a'への書き込み中にバッファーオーバーランが発生しました:書き込み可能なサイズは'en*4'バイトですが、'en'バイトを書き込む可能性があります。
131
136
 
132
- また以下の警告文が出てきます。
133
- ・初期化されていないメモリ'a'を使用しています
134
-
135
137
  ### 環境
136
138
  Visual Studio 2019 C++です

3

プログラムの訂正、エラー内容、実施環境を追加しました。

2021/11/09 13:00

投稿

退会済みユーザー
title CHANGED
@@ -1,1 +1,1 @@
1
- 生成されたグラフを呼び出す方法
1
+ グラフを呼び出し、値を挿入する方法
body CHANGED
@@ -1,6 +1,19 @@
1
- ### 前提・実現したいこと
1
+ ### 実現したいこと
2
- 前回からの質問になります。
2
+ 前回(https://teratail.com/questions/367958)からの質問になります。
3
- グラフをランダムに作成し、出力された接続行列から、空の配列a[en]に１のみの列を挿入するようにしたいのですが、エラーで動かないです
3
+ ランダムに作成された接続行列から値を空の配列a[en]に値を挿入していき、
4
+ 配列a[en]の全要素が１になるまでに挿入した回数を出力したいです
5
+ 例）
6
+ ```
7
+ 頂点数(行) = 7
8
+ グラフの辺数(列) = 10
9
+ 0 0 0 0 0 0 1 1 1 1
10
+ 0 1 1 1 0 0 0 0 0 0
11
+ 0 0 0 0 1 0 0 0 1 0
12
+ 0 0 0 1 0 1 1 0 0 0 この行列から、a[en] = {1,1,1,1,1,1,1,1,1,1}となるまでに何回行の要素を組み合わせたか数えたい
13
+ 0 1 0 0 0 0 0 1 0 0
14
+ 1 0 1 0 0 0 0 0 0 0
15
+ 1 0 0 0 1 1 0 0 0 1
16
+ ```
4
17
 
5
18
  ### 該当するソースコード
6
19
  ```C++
@@ -9,6 +22,7 @@
9
22
  #include <algorithm>
10
23
  #include <list>
11
24
  #include <random>
25
+ #include <numeric>
12
26
 
13
27
  using namespace std;
14
28
 
@@ -62,18 +76,34 @@
62
76
  };
63
77
 
64
78
  //最小の被覆数を探索する関数(接続行列)
65
- int is_covering(const con_matrix& con)
79
+ void is_covering(con_matrix &con)
66
80
  {
67
- int vn = con.get_vertex_num();
81
+ int vn = con.get_vertex_num(); // 頂点数
68
- int en = con.get_edge_num();
82
+ int en = con.get_edge_num(); // 辺数
69
- con_matrix am(vn, en);
70
- am.set_vertex_num(vn,en);
71
- am.set_random(1);
72
-
73
- int min_c = 0;
83
+ int min_c[10] = {}; // 実験回数
84
+ int w = 0; // 値を挿入したカウント
74
85
  int* a = new int[en];
75
-
86
+ vector < vector<int>> matrix;
76
- return min_c;
87
+ con.set_random(1);
88
+
89
+ for (int min = 0; min < 10; min++) {
90
+ while( w < en){
91
+ w = 0;
92
+ int i = rand() % vn;
93
+ for (int j = 0; j < en; j++) {
94
+ if (a[j] == 0 && matrix[i][j] == 1) {
95
+ a[i] = matrix[i][j];
96
+ }
97
+ }
98
+ 　　　　　　　　　　　　　for (int o = 0; o < en; o++) {
99
+ w = +a[o];
100
+ 　　　　　　　　　　　　　}
101
+ min_c[min] = +1;
102
+ }
103
+ }
104
+ for (int b = 0; b < 10; b++) {
105
+ cout << min_c[b] << ",";
106
+ }
77
107
  }
78
108
 
79
109
  int main()
@@ -89,11 +119,18 @@
89
119
  cout << "グラフの辺数 = " << e << endl;
90
120
  am.disp_connection();
91
121
  cout << endl;
122
+
92
123
  is_covering(am);
93
124
 
94
125
  return 0;
95
126
  }
96
127
  ```
97
128
 
98
- ### 試したこと
129
+ ### 試したこと、エラー内容
99
- クラス内の関数、set_randomなどにあるmatrix[][]を利用することで空の配列に挿入できると思ったのですが、エラーで動かないです。
130
+ 関数is_coveringにクラスcon_matrixの関数を書き込み、matrix[i][j] = 1であれば配列a[en]の要素を１にし、全要素がうまるまで繰り返すようにし、この行為を10回繰り返すようにしたのですが、出力されないです。(実行はできています。)
131
+
132
+ また以下の警告文が出てきます。
133
+ ・初期化されていないメモリ'a'を使用しています
134
+
135
+ ### 環境
136
+ Visual Studio 2019 C++です

2

試したことや実現したいことを変更しました。何かしらのヒントのみでもあれば幸いです。

2021/11/09 02:16

投稿

退会済みユーザー
title CHANGED
@@ -1,1 +1,1 @@
1
- 接続行列を使って、頂点被覆をC++で求めたい
1
+ 生成されたグラフを呼び出す方法
body CHANGED
@@ -1,29 +1,8 @@
1
1
  ### 前提・実現したいこと
2
2
  前回からの質問になります。
3
- グラフをランダムに作成し、出力された接続行列を読み込み、行の中が全て１になるように
3
+ グラフをランダムに作成し、出力された接続行列から、空の配列a[en]に１のみの列を挿入するようにしたいのですが、エラーで動かないです
4
- 組み合わせたいのですが、どうしたらいいかわからないです。
5
4
 
6
-
7
-
8
- ### 全体のプログラミング
9
- 自身が実装したいプログラムのリストと、
10
- 自分が作成しているプログラムの今現在の段階です。
11
-
12
- ```
13
- 頂点と辺の数を入力する
14
- ↓
15
- 接続行列を生成(行：頂点数、列；辺数)
16
- ↓
17
- 空の配列(辺数)を宣言し、接続行列を行を配列に挿入していき、
18
- 配列の中が全て「１」となるものを見つける　　　　　　　　　　　　　　　←今現在取り組んでいるもの
19
- ↓
20
- 使用した行（頂点）の数を数え、最小のものが出るまで繰り返す
21
- ↓
22
- 全ての探索をし終えた後、最小の行(頂点)の数を出力する
23
- ```
24
-
25
- ### 該当のソースコード
5
+ ### 該当するソースコード
26
-
27
6
  ```C++
28
7
  #include <iostream>
29
8
  #include <vector>
@@ -74,41 +53,27 @@
74
53
  }
75
54
  void disp_connection() const
76
55
  {
77
- for (auto& row : matrix){
56
+ for (auto& row : matrix) {
78
57
  for (auto v : row)
79
58
  cout << v << " "; //要素を表示
80
59
  cout << endl; //行列列数を設定
81
60
  }
82
61
  }
83
-
84
- int connection(int i, int j) const { return matrix[i][j]; }
85
- void make_con_list(vector<vector<int>>& al) const
86
- {
87
- int vn = matrix.size(); //頂点数
88
- al.resize(vn);
89
- for (int i = 0; i < vn; i++)
90
- {
91
- al[i].resize(0);
92
- for (int j = 0; j < vn; j++)
93
- {
94
- if (connection(i, j))
95
- al[i].push_back(j);
96
- }
97
- }
98
- }
99
-
100
62
  };
101
63
 
64
+ //最小の被覆数を探索する関数(接続行列)
102
- void disp_adj_list(const vector<vector<int>>& al)
65
+ int is_covering(const con_matrix& con)
103
- {
66
+ {
67
+ int vn = con.get_vertex_num();
68
+ int en = con.get_edge_num();
104
- for (auto& list : al)
69
+ con_matrix am(vn, en);
70
+ am.set_vertex_num(vn,en);
71
+ am.set_random(1);
72
+
105
- {
73
+ int min_c = 0;
106
- for (auto v : list)
74
+ int* a = new int[en];
107
- {
75
+
108
- cout << v << " "; //行列列数を設定
109
- }
110
- cout << endl; //行列列数を設定
76
+ return min_c;
111
- }
112
77
  }
113
78
 
114
79
  int main()
@@ -124,7 +89,11 @@
124
89
  cout << "グラフの辺数 = " << e << endl;
125
90
  am.disp_connection();
126
91
  cout << endl;
92
+ is_covering(am);
127
93
 
128
94
  return 0;
129
95
  }
130
- ```
96
+ ```
97
+
98
+ ### 試したこと
99
+ クラス内の関数、set_randomなどにあるmatrix[][]を利用することで空の配列に挿入できると思ったのですが、エラーで動かないです。

1

指摘していただいた部分を丸ごと消去いたしました。自分もこの状態からどのように書き込めばよいのかも分からないため、何かアドバイスをもらえると幸いだと思い質問させていただいてます。

2021/11/08 15:53

投稿

退会済みユーザー
title CHANGED
File without changes
body CHANGED
@@ -111,22 +111,6 @@
111
111
  }
112
112
  }
113
113
 
114
- //頂点被覆かチェックする関数(接続行列)
115
- int is_covering(const con_matrix& con, const int cover[])
116
- {
117
- int vn = con.get_vertex_num();
118
- int en = con.get_edge_num();
119
- int max_c = 0;
120
-
121
- for (int i = 0; i < vn; i++){
122
- for (int j = 0; j < en; j++){
123
- int c = cover[j];
124
- if (c == 1);
125
- }
126
- }
127
- return max_c;
128
- }
129
-
130
114
  int main()
131
115
  {
132
116
  const int n = 7; //頂点数
@@ -143,22 +127,4 @@
143
127
 
144
128
  return 0;
145
129
  }
146
- ```
147
- 以下の部分に書き足すことで実装できると思って書き込んでいます。
148
- ```
149
- //頂点被覆かチェックする関数(接続行列)
150
- int is_covering(const con_matrix& con, const int cover[])
151
- {
152
- int vn = con.get_vertex_num();
153
- int en = con.get_edge_num();
154
- int max_c = 0;
155
-
156
- for (int i = 0; i < vn; i++){
157
- for (int j = 0; j < en; j++){
158
- int c = cover[j];
159
- if (c == 1);
160
- }
161
- }
162
- return max_c;
163
- }
164
130
  ```