무작위로 연결된 그래프 생성기

Question

N 노드를 임의로 연결하여 간단한 그래프를 생성하려고합니다.

• 입력 : 노드의
  • N 수 가장자리의
  • E 수 N-1의 출력
• N(N-1)/2에 나는, 그래서 이런 일을 할 효율적인 알고리즘을 찾고 있어요 : N vertex와 E edges를 가진 Simple Connected 그래프

Answer 1

N 노드의 배열을 만듭니다. Fisher-Yates shuffle 배열입니다. 어레이를 스캔하고 어레이에 인접한 노드 쌍마다 에지를 작성하십시오. 결과는 N-1 가장자리의 연결된 그래프입니다.

추가 가장자리 수가 적 으면 충분한 크기가 될 때까지 임의로 가장자리를 추가 할 수 있습니다. 그렇지 않으면 사용되지 않는 모서리의 배열을 만들고 Fisher-Yates는 배열을 임의로 뒤집어 배열에서 첫 번째 (E - (N-1)) 모서리를 가져옵니다.

Answer 2

다음은 임의의 수의 다른 노드와 각 노드를 무작위로 연결하는 매우 간단한 알고리즘입니다.

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]); 
     } 
    } 
}