Randomly Connected Graph Generator

Question

Ich versuche, einen einfachen Graphen zu erzeugen, indem ich zufällig N Knoten annehme. Ich suche für einen effizienten Algorithmus zu tun, so etwas wie dieses:

• Eingang:
  • N Anzahl der Knoten
  • E Anzahl der Kanten von N-1 zu N(N-1)/2
• Ausgang : Einfach Verbundener Graph mit N Ecken und E Kanten

Answer 1

Erstellen Sie ein Array von N Knoten. Fisher-Yates shuffle das Array. Scannen Sie das Array und erstellen Sie eine Kante für jedes Knotenpaar, das im Array benachbart ist. Das Ergebnis ist ein zusammenhängender Graph mit N-1 Kanten.

Wenn die Anzahl der zusätzlichen Kanten klein ist, können Sie Kanten einfach zufügen, bis Sie genug haben. Erstellen Sie andernfalls ein Array der nicht verwendeten Kanten, Fisher-Yates mischt das Array und nimmt die ersten (E - (N-1)) Kanten aus dem Array.

Answer 2

Hier ist ein extrem einfacher Algorithmus, der zufällig jeden Knoten mit einer zufälligen Anzahl anderer Knoten verbindet.

void CreateRandomGraph(IList<Node> nodes, int maxConnections) 
{ 
    var rnd = new Random(); 

    foreach (Node node in nodes) 
    { 
     int numConnections = (int)(rnd.NextDouble() * maxConnections); 
     for (int i = 0; i < numConnections; i++) 
     { 
      //Find a random node to connect to 
      int idx = (int)(rnd.NextDouble() * nodes.Count); 
      node.ConnectTo(nodes[idx]); 
     } 
    } 
}