無作為グラフを生成する

Question

私はadj_matrix [u] [v] == adj_matrix [v] [u]を適用しようとすると助けが必要です。正しいパス？

エッジがない行列を0ではなくXに設定する方法はありますか？

int gen_random_graph(int n) 
{ 
    srand(time(0)); 
    int adj_matrix[n][n]; 
    for(int u = 0; u < n; u++) 
    { 
     for (int v = u; v < n; v++) //generating a N x N matrix based on the # of vertex input 
     { 
      bool edgeOrNot = rand() % 2; //decide whether it has an edge or not 
      adj_matrix[u][v] = adj_matrix[v][u] = edgeOrNot; 
      cout << u << " " << v << " " << adj_matrix[u][v] << endl; 
      if(adj_matrix[u][v] == true) 
      { 
       adj_matrix[v][u] = true; 
       if(u == v)       //We can't have i = j in an undirected graph 
       { 
        adj_matrix[u][v] = -1; 
       } 
       cout << u << " " << v << " " << adj_matrix[u][v] << endl; 
      } 
      else 
      { 
       adj_matrix[v][u] = -1; 
       cout << u << " " << v << " " << adj_matrix[u][v] << "else" << endl; 
      } 
     } 

    } 

    for(int i = 0; i < n; i++) 
    { 
     for(int j = i; j < n; j++)   //create the N x N with edges and sets the weight between the edge randomly 
     { 
      if(adj_matrix[i][j] == true) 
      { 
        int weight1 = rand()%10 + 1; 
        adj_matrix[i][j] = adj_matrix[j][i] = weight1; 
        cout << " (" << i << "," << j << ") " << "weight: " << adj_matrix[i][j] << endl; 
      } 
     } 
    } 
} 
int main() 
{ 
    int N; 
    cout << "Enter number of vertices" << endl; 
    cin >> N; 
    gen_random_graph(N); 

    return 0; 
} 

Answer 1

代わりに 'X'を使用することをお勧めします-1値。サンプルがあります：

void gen_random_graph(int n) { 
    srand(time(0)); 
    int adj_matrix[n][n]; 

    for(int u = 0; u < n; u++) { 
     for (int v = u; v < n; v++) { //you don't need to calculate weight twice so loop starts from u 
      if(v == u) { 
       adj_matrix[u][v] = -1; 
      } 
      else { 
       int weight = rand() % 10 - 1; 
       adj_matrix[u][v] = adj_matrix[v][u] = weight; 
      } 
     } 
    } 
} 

エッジの値を確認できます。 -1の場合は存在しません。

Answer 2

他にもアルゴリズムがよくわかりません。 boolを保存するのにint adj_matrixを使用することの1つですが、'X'、charを保存することは避けるべきことです。私がしようとするのと同じ重みを保存するために

：コンパイラ

const int weight = rand() % 10 + 1; 
adj_matrix[u][v] = weight; 
adj_matrix[v][u] = weight; 

は、ステートメントごとに1回、2回rand()を起動しようとするかもしれません。上記では、rand()を1回だけ呼び出します。

一般的に私はstd::vector<int>とstd::vector<std::vector<int>>のようなSTLコンテナを使用しますが、後者はメモリフットプリントの観点から理想的ではありません。

'X'の代わりにstd::numeric_limits<int>::minまたはmaxを使用します（rand() % 10 + 1と等しくない場合があります）。