我尝试实现 karger Minimum Cut 算法（Karger wiki page）
到目前为止，我已经在小例子（大小为 10 的输入）上尝试了我的算法，它似乎有效。但是当我尝试有更大的输入时，假设是 200。它只会崩溃。
为了存储最小切割数据，我创建了一个二维数组：GraphCut[SIZE_ARRAY][SIZE_ARRAY_2] SIZE_ARRAY = 200 在这种情况下，但我找不到 SIZE_ARRAY_2 的合适长度。
问题是，SIZE_ARRAY_2 必须很大，因为我修改了初始数组以合并不同的顶点。
如果我声明 SIZE_ARRAY_2 = 200，大小将不够，但如果我设置 SIZE_ARRAY_2 = 1000，程序就会崩溃。
问题是，我必须执行算法 100000 次。
以下是部分代码：
#define ARRAY_SIZE 200
#define ARRAY_SIZE_2 200
int main()
{
int minCut,minMinCut;
for (int k = 0; k < ARRAY_SIZE * ARRAY_SIZE * 4;k++) {
minCut = kargerMinCut(k);
if (k == 0)
minMinCut = minCut;
else if (minMinCut > minCut)
minMinCut = minCut;
}
printf("\n minMinCut = %d\n", minMinCut);
return 0;
}
int kargerMinCut(int k) {
// 1st dimension: each different node
// 2nd dimension: vertices
long graphCut[ARRAY_SIZE + 1][ARRAY_SIZE_2] = {0};
populateIntegerArray(graphCut); // import data from a file
int nodeToMain[ARRAY_SIZE + 1];
int sizeOfMainNode, indexToMerge,initialRand,i,j,m,nodeToMerge,nodeRemaining = ARRAY_SIZE;
for (m = 0;m<ARRAY_SIZE + 1;m++) // initialization of nodeToMain
nodeToMain[m] = m;
while (nodeRemaining > 2) {
i = 0;
j = 0;
srand(time(NULL) + nodeRemaining);// initialise rand
initialRand = nodeToMain[rand()%(ARRAY_SIZE) + 1]; // pick a random initial node, but not a merged one
sizeOfMainNode = sizeOfArray(graphCut[initialRand]); // size of the initial node
srand(time(NULL) + k); // initialise rand
indexToMerge = rand()%sizeOfMainNode;// pick another random node in the linked nodes (its index to be precise)
nodeToMerge = nodeToMain[graphCut[initialRand][indexToMerge]];
for (m = 0;m<ARRAY_SIZE + 1;m++) // update the nodeToMain array, initialRand is now the main node for nodeToMerge
if (nodeToMain[m] == nodeToMerge)
nodeToMain[m] = initialRand;
// remove the nodeToMerge numbers from the graphCut[initialRand] (as they are going to be merged)
while(graphCut[initialRand][j] > 0 && j < sizeOfMainNode) {
if (initialRand == nodeToMain[graphCut[initialRand][j]]) {
// if this is the last element, do nothing
while(nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]] == initialRand && j < sizeOfMainNode - 1) {
graphCut[initialRand][sizeOfMainNode - 1] = 0;
sizeOfMainNode--;
}
graphCut[initialRand][j] = nodeToMain[graphCut[initialRand][sizeOfMainNode - 1]];
graphCut[initialRand][sizeOfMainNode - 1] = 0;
sizeOfMainNode--;
}
j++;
}
i = 0;
while (graphCut[nodeToMerge][i] > 0 && sizeOfMainNode < ARRAY_SIZE_2 && i < ARRAY_SIZE_2) { // add each vextex of the nodeTomerge to the merged nodes
if (nodeToMain[graphCut[nodeToMerge][i]] != initialRand) {
graphCut[initialRand][sizeOfMainNode] = nodeToMain[graphCut[nodeToMerge][i]];
sizeOfMainNode++;
}
i++;
}
nodeRemaining--;
}
return sizeOfArray(graphCut[nodeToMain[1]]);
}
我确信代码不是很干净，甚至可能很糟糕（C 初学者）。所以我欢迎任何其他建议。
我用调试器得到的错误似乎真的很随机。错误是：
不可能除以 0
它在第 62 行的 time64.c 中停止
tim = (__time64_t)((nt_time.ft_scalar - EPOCH_BIAS) / 10000000i64);