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

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

新規登録して質問してみよう
ただいま回答率
85.53%
グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

Q&A

解決済

1回答

1143閲覧

バッファーオーバーランが出ているためか、出力されない

退会済みユーザー

退会済みユーザー

総合スコア0

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C++

C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

0グッド

0クリップ

投稿2021/11/10 00:22

編集2021/11/10 00:23

実現したいこと

前回(https://teratail.com/questions/368301)と同様になりますが、編集が重なり質問内容が別物になっているため、改めての質問になります。
ランダムに作成された接続行列から値を空の配列a[en]に値を挿入していき、
配列a[en]の全要素が1になるまでに挿入した回数を出力したいです。

例)

頂点数(行) = 7 グラフの辺数(列) = 10 0 0 0 0 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 0 この行列から、a[en] = {1,1,1,1,1,1,1,1,1,1}となるまでに何回行の要素を組み合わせたか数えたい 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1

該当するソースコード

C++

1#include <iostream> 2#include <vector> 3#include <algorithm> 4#include <list> 5#include <random> 6 7using namespace std; 8 9bool graph[1010][1010]; 10 11class con_matrix 12{ 13private: 14 vector < vector<int>> matrix; 15public: 16 con_matrix(int vn, int en) { set_vertex_num(vn, en); } 17 void set_vertex_num(int vn, int en) 18 { 19 matrix.resize(vn); //行列行数を設定 20 for (auto& line : matrix) 21 line.resize(en); //行列列数を設定 22 } 23 int get_vertex_num() const { return matrix.size(); } 24 int get_edge_num() const { return matrix.at(0).size(); } 25 26 void set_random(unsigned int seed = 0) // seed:乱数シード(値を変えると乱数列が変化) 27 { 28 for (auto& row : matrix) 29 { 30 for (auto& v : row) 31 v = 0; //要素をクリア 32 } 33 34 int vn = matrix.size(); //頂点数 35 int en = matrix.at(0).size(); //辺数 36 srand(seed); 37 vector<pair<int, int>> es; 38 for (int i = 0; i < vn - 1; ++i) 39 for (int j = i + 1; j < vn; ++j) 40 es.emplace_back(i, j); 41 for (int i = 0; i < en; ++i) 42 { 43 swap(es[i], es[i + rand() % (es.size() - i)]); 44 matrix[es[i].first][i] = 1; 45 matrix[es[i].second][i] = 1; 46 } 47 } 48 void disp_connection() const 49 { 50 for (auto& row : matrix) { 51 for (auto v : row) 52 cout << v << " "; //要素を表示 53 cout << endl; //行列列数を設定 54 } 55 } 56}; 57 58 59//最小の被覆数を探索する関数(接続行列) 60void is_covering(con_matrix &con) 61{ 62 int vn = con.get_vertex_num(); // 頂点数 63 int en = con.get_edge_num(); // 辺数 64 int min_c[5] = {}; // 使用した頂点数 65 int w = 0; // カウント 66 int* a = new int[en]; 67 a[en] = {}; 68 vector < vector<int>> matrix; 69 con.set_random(1); 70 71 for (int min = 0; min < 5; min++) { 72 while( w < en){ 73 w = 0; 74 int i = rand() % vn; 75 for (int j = 0; j < en; j++) { 76 if (a[j] == 0 && matrix[i][j] == 1) { 77 a[j] = 1; 78 } 79 } 80 for (int o = 0; o < en; o++) { 81 w = +a[o]; 82 min_c[min] = +1; 83 } 84 } 85 } 86 for (int b = 0; b < 5; b++) { 87 cout << min_c[b] << ","; 88 } 89} 90 91 92int main() 93{ 94 const int n = 7; //頂点数 95 double r = 0.5; //辺数の比率 96 const int e = ((n * (n - 1) / 2) * r); 97 vector<int> con; 98 int cover = 0; // 被覆数 99 con_matrix am(n, e); 100 am.set_random(1); //ランダムにグラフの接続行列を作る。引数は乱数シード 101 102 103 104 cout << "頂点数 = " << n << endl; 105 cout << "グラフの辺数 = " << e << endl; 106 am.disp_connection(); 107 cout << endl; 108 is_covering(am); 109 return 0; 110}

試したこと・エラー内容

エラーは出ず、実行はできているのですが、min_cの出力がされないです。
また、以下の警告文が出てきます。
・'a'への書き込み中にバッファーオーバーランが発生しました:書き込み可能なサイズは'en*4'バイトですが、'en'バイトを書き込む可能性があります。
対象となる67行目を丸ごと消してみたりしても実行はできるのですが、「初期化されていません」と警告文が出てき、やはりmin_cが出力されないです。

環境

Visual Studio 2019 C++です

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

C++

1//最小の被覆数を探索する関数(接続行列) 2void is_covering(con_matrix &con) 3{ 4 int vn = con.get_vertex_num(); 5 int en = con.get_edge_num(); 6 int min_c[5] = {}; 7 int w = 0; 8 int* a = new int[en]; // ****[1] 配列の要素数はenだから *** 9 a[en] = {}; // ****[1] a[en] は存在しない **** 10 vector < vector<int>> matrix; // ****[2] 行数/列数 共に0 だから**** 11 con.set_random(1); 12 13 for (int min = 0; min < 5; min++) { 14 while( w < en){ 15 w = 0; 16 int i = rand() % vn; 17 for (int j = 0; j < en; j++) { 18 if (a[j] == 0 && matrix[i][j] == 1) { // ****[2] matrix[i][j] は存在しない *** 19 a[j] = 1; 20 } 21 } 22 for (int o = 0; o < en; o++) { 23 w = +a[o]; 24 min_c[min] = +1; 25 } 26 } 27 } 28 for (int b = 0; b < 5; b++) { 29 cout << min_c[b] << ","; 30 } 31}

投稿2021/11/10 01:28

episteme

総合スコア16614

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.53%

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

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

質問する

関連した質問