随机边缘生成图

-2

我正在尝试使用排列和路径压缩使用联合使用不相交集的ac/C++程序图算法然后在该图上应用Kruskal算法。我已经生成了number_of_vertices-1对（0,1），（1,2）...（n-2，n-1）作为图中的边，以使图连通。我需要生成其余的3 * number_Of_Vertices + 1个随机边作为（vertex1，vertex2）对，而不会产生冲突（同样的边不会产生两次）。我必须这样做而不使用额外的内存。通过额外的记忆我的意思是一个额外的列表，矢量...你有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; 
}

来源

2017-05-17 Sebi Danila

规则的一些数字您是否正在寻找交流或一个C++解决方案？这两种语言都提供不同的解你的例子看起来像c，并且你有两种语言被标记。 –

我很喜欢任何语言解决方案，我只是想要算法。是的，我的代码是写在C –

如果你正在寻找讨论算法，你可能想问一个更合适的堆栈交换站点。也许https://cs.stackexchange.com/？ –

所以，你有N条边，想将它们标记为K个优化内存消耗。在这种情况下，您可以使用Reservoir sampling，其内存复杂度为O（K）。

请用大小为K的整数数组，与0..K-1号填充它，然后步行一个循环，随机替换使用提供均匀

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]

来源

2017-05-18 02:19:03 MBo

随机边缘生成图

回答

相关问题