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

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

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

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

アルゴリズム

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

C++

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

Q&A

解決済

1回答

1789閲覧

接続行列(無向グラフ)をランダムに生成したい

退会済みユーザー

退会済みユーザー

総合スコア0

グラフ理論

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

アルゴリズム

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

C++

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

0グッド

0クリップ

投稿2021/11/05 15:05

前提・実現したいこと

頂点の数を入力し無向グラフをランダムに生成し、そのグラフを接続行列で出力したいです。

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

元々ランダムに生成された無向グラフを隣接行列と隣接リストに出力するプログラムを、 接続行列を出力する(列:辺数、行:頂点数で、各列の和が2になる)よう書き換えたのですが、以下の実行結果のように出力されてしまいます。 頂点数 = 5 グラフの辺数 = 7 0 1 1 1 1 0 0 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0

該当のソースコード

#include <iostream> #include <vector> #include <algorithm> #include <list> #include <random> using namespace std; bool graph[1010][1010]; class con_matrix { private: vector < vector<int>> matrix; public: con_matrix(int vn, int en) { set_vertex_num(vn, en); } void set_vertex_num(int vn, int en) { matrix.resize(vn); //行列行数を設定 for (auto& line : matrix) line.resize(en); //行列列数を設定 } int get_vertex_num() const { return matrix.size(); } int get_edge_num() const { return matrix.at(0).size(); } void set_random(unsigned int seed = 0) // seed:乱数シード(値を変えると乱数列が変化) { for (auto& row : matrix) { for (auto& v : row) v = 0; //要素をクリア } int vn = matrix.size(); //頂点数 int en = matrix.at(0).size(); //辺数 srand(seed); for (int cnt = 0; cnt < vn; ) { int r1 = rand() % vn; int r = 0; for (int a = 0; a < 2; ) { int r2 = rand() % vn; if (r != r2 && !matrix[r1][r2]) { r = r2; matrix[r1][r2] = 1; a++; } } cnt++; } } void disp_connection() const { for (auto& row : matrix){ for (auto v : row) cout << v << " "; //要素を表示 cout << endl; //行列列数を設定 } } int connection(int i, int j) const { return matrix[i][j]; } void make_con_list(vector<vector<int>>& al) const { int vn = matrix.size(); //頂点数 al.resize(vn); for (int i = 0; i < vn; i++) { al[i].resize(0); for (int j = 0; j < vn; j++) { if (connection(i, j)) al[i].push_back(j); } } } }; void disp_adj_list(const vector<vector<int>>& al) { for (auto& list : al) { for (auto v : list) { cout << v << " "; //行列列数を設定 } cout << endl; //行列列数を設定 } } int main() { const int n = 5; //頂点数 double r = 0.7; //辺数の比率 const int e = ((n * (n - 1) / 2) * r); int cover = 0; // 被覆数 con_matrix am(n, e); //接続行列 am.set_random(1); //ランダムにグラフの隣接行列を作る。引数は辺の存在確率, 乱数シード cout << "頂点数 = " << n << endl; cout << "グラフの辺数 = " << e << endl; am.disp_connection(); cout << endl; vector<vector<int>> ajl; //隣接リスト // am.make_con_list(ajl); disp_adj_list(ajl); return 0; }

試したこと

以下のプログラムにある、int r1 = rand() % vn や cnt < vn を辺数である en に書き換えたりすると実行不可となり、出力すらできなくなります。

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

visual studio 2019のC++言語で入力しています。

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

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

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

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

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

guest

回答1

0

ベストアンサー

隣接行列でのやり方だと重複判定が大変なので、全く別のやり方を検討しましょう。
以下のコードでは、すべての辺を生成したうえで、必要な数だけランダムで抽出しています。

c++

1 void set_random(unsigned int seed = 0) // seed:乱数シード(値を変えると乱数列が変化) 2 { 3 for (auto& row : matrix) 4 { 5 for (auto& v : row) 6 v = 0; //要素をクリア 7 } 8 9 int vn = matrix.size(); //頂点数 10 int en = matrix.at(0).size(); //辺数 11 srand(seed); 12 vector<pair<int, int>> es; 13 for (int i = 0; i < vn - 1; ++i) 14 for (int j = i + 1; j < vn; ++j) 15 es.emplace_back(i, j); 16 for (int i = 0; i < en; ++i) 17 { 18 swap(es[i], es[i + rand() % (es.size() - i)]); 19 matrix[es[i].first][i] = 1; 20 matrix[es[i].second][i] = 1; 21 } 22 }

投稿2021/11/06 04:25

actorbug

総合スコア2212

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

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

退会済みユーザー

退会済みユーザー

2021/11/06 05:05

頂点数や辺の比率の値を変えても、無事実行できました! ありがとうございます!
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

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

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

質問する

関連した質問