Generieren von Zufallsgraph

Question

Lassen Sie jemanden eine ganze Zahl N als die Anzahl der Scheitelpunkte im Diagramm eingeben.

• zuordnen zufällige Gewichte auf jeder Kante von 1 bis 10 nicht alle möglichen Kanten im Bereich sind zwar vorhanden! Wie im obigen Beispiel wird eine fehlende Kante durch ein X dargestellt.
• Geben Sie ein Paar (M, L) zurück, wobei M und L die Matrix- und Listendarstellung des (gleichen) zufälligen Graphen sind, den Sie erzeugen.
• Verwenden Sie nicht-stellige Zeichen als Vertexnamen, um Verwechslungen mit Kantengewichten zu vermeiden.

#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; 
} 

Das ist mein Code ist so weit. Generiert es die Gewichte? und was bedeutet es, dass ich ein Paar zurückgeben muss?

Answer 1

Ein Graph kann als N x N-Adjazenzmatrix dargestellt werden (wie Sie bereits eingerichtet haben), wobei der Wert in matrix[i][j] auf das Gewicht des Kantenscheitel i Verbindungs ​​entspricht j Scheitel. Eine Null entspricht einer Verbindung zwischen i und j. Wenn matrix[i][j] == matrix[j][i], dann haben Sie eine ungerichtete Grafik. Außerdem würde ein zufälliger Graph Zufallswerte als Kanten zwischen den Eckpunkten haben.

In dem Fall, dass entweder jede Kante existiert oder existiert nicht (dh Gewichte sind entweder 0 oder 1), haben Sie die folgenden könnten:

Dieses Bild aus dem Internet gestohlen wird, also nehme ich keine Anerkennung dafür. Beachten Sie, dass Sie leicht bestätigen können, dass der erste Graph ungerichtet ist, da die Adjazenzmatrix symmetrisch ist. In ähnlicher Weise ist der zweite Graph gerichtet, weil die Matrix NICHT symmetrisch ist.