ランダムなエッジを持つグラフを生成する

Question

ランクとパスの圧縮で共用体を使用して、非結合セットを使用するac/C++プログラムを作成しようとしています。グラフアルゴリズムがそのグラフにKruskalのアルゴリズムを適用しました。number_of_vertices-1 pairs（0,1） 、（1,2）...（n-2、n-1）をグラフのエッジとして出力する。私は残りの3 * number_Of_Vertices + 1ランダムなエッジを（頂点1、頂点2）のペアとして生成する必要があります（同じエッジは2回生成されません）。私は余分なメモリを使用せずにこれを行う必要があります。余分なメモリで、私は余分なリスト、ベクトルを意味...あなたはguyzはこれを行うにはどのようなアイデアを持っていますか？

これは私が今までやったことですが、それは確かに衝突があります

edge** createRandomEdges(nodeG **nodeArray, int n) { 
    edge **edgeArray = (edge**)malloc(sizeof(edge*)*n * 4); 

    for (int i = 0; i < n; i++) 
     edgeArray[i] = createEdge(nodeArray[0], nodeArray[i + 1], rand() % 100+1); 
    for (int i = n; i < 4 * n; i++) { 
     int nodeAindex = rand() % n; 
     int nodeBindex = rand() % n; 

     while (nodeAindex == nodeBindex) { 
      nodeAindex = rand() % n; 
      nodeBindex = rand() % n; 
     } 

     int weight = rand() % 100 + 1; 
     edgeArray[i] = createEdge(nodeArray[nodeAindex], nodeArray[nodeBindex], weight); 
    } 

    return edgeArray; 
} 

Answer 1

ですから、Nエッジを持っているし、メモリ消費を最適化し、それらのKをマークしたいです。この場合、Reservoir samplingをO（K）のメモリの複雑さで使用できます。

、ループを歩くと、ランダムに均一

ReservoirSample(S[1..n], R[1..k]) 
    // fill the reservoir array 
    for i = 1 to k 
     R[i] := S[i] 

    // replace elements with gradually decreasing probability 
    for i = k+1 to n 
    j := random(1, i) // important: inclusive range 
    if j <= k 
     R[j] := S[i]