генерации случайных граф неориентированный

Question

мне нужна помощь всякий раз, когда я пытаюсь сделать adj_matrix [и] [v] == adj_matrix [v] [и] для того же веса, он не применяется, и может кто-нибудь сказать мне, если я нахожусь на правильный путь?

и есть способ, чтобы установить матрицу без краев к Й вместо 0?

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

Я не уверен в вашем алгоритме, среди прочего. Это одна вещь, чтобы использовать int adj_matrix для хранения bool с, но хранение 'X', char то, что я хотел бы избежать.

Для хранения же веса я хотел бы попробовать:

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

Компилятор может попытаться вызвать rand() дважды, один раз для каждого оператора. В приведенном выше примере вы вызываете rand() только один раз.

В общем, я бы использовал контейнеры STL, такие как std::vector<int> и std::vector<std::vector<int>>, хотя последний не идеален с точки зрения памяти.

Вместо 'X' Я бы использовал std::numeric_limits<int>::min или max, что не может быть равно rand() % 10 + 1.