隨機邊緣生成圖

-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

隨機邊緣生成圖

回答

相關問題