ランダムグラフの生成

Question

グラフの頂点の数として整数Nを入力しましたか？

• 1から10の範囲の各エッジにランダムウェイトを割り当てます。すべての可能なエッジはありません。 が存在します。上記の例のように、Xによって不在のエッジを表します。
• MとLがそれぞれ行列であり、生成する（同じ）ランダムグラフのリスト表現 を表すペア（M、L）を返します。
• エッジウェイトの混乱を避けるため、非数字の文字を頂点名として使用します。

#include <iostream> 
#include <stdlib.h> 
using namespace std; 
void gen_random_graph(int n) 
{ 
    int adj_matrix[n][n]; 
    for(int u = 0; u < n; u++) 
    { 
     for (int v = 0; v < n; v++) 
     { 
      if(adj_matrix[u][v]==adj_matrix[v][u]) 
      { 
       adj_matrix[u][v] = rand() % 10 + 1; 
       cout << adj_matrix[u][v] << endl; 
      } 
     } 
    } 

} 

int main() 
{ 
    int N; 
    cout << "enter number of vertices" << endl; 
    cin >> N; 
    gen_random_graph(N); 

    return 0; 
} 

これは、これまでの私のコードです。それは体重を生成していますか？私はペアを返さなければならないということはどういう意味ですか？

Answer 1

グラフは、すでに設定したように、N×N隣接行列として表すことができます。matrix[i][j]の値は、頂点iから頂点jを接続するエッジの重みに対応します。ゼロは、iとjの間の接続が存在しないことに対応します。 matrix[i][j] == matrix[j][i]の場合、無向グラフが表示されます。さらに、ランダムなグラフは、頂点間のエッジとしてランダムな値を持ちます。すべてのエッジが存在するか、存在しません。いずれの場合も

（つまり、重みが0または1のどちらかである）は、次のものができます。

この画像は、インターネットから盗まれ、私はそれを信用できません。隣接行列が対称であるため、最初のグラフが無向であることを簡単に確認できます。同様に、第2のグラフは、行列が非対称であるため指示される。