0

我正在尝试在 Java 中实现 min-cut Karger 算法。为此，我创建了一个 Graph 类，它存储一个 SortedMap，一个整数索引作为键，一个顶点对象作为值，以及一个边缘对象的 ArrayList。Edges 存储其事件顶点的索引。然后我合并一些随机边的顶点，直到顶点数达到 2。我重复这个步骤安全的次数。奇怪的是，在我的输出中，我得到了 2 倍的交叉边数。我的意思是，如果正确答案是 10，在执行 n 次算法后（对于 n 足够大），这些执行结果的最小值是 20，这让我相信实现几乎是正确的。这是代码的相关部分：

    void mergeVertex(int iV, int iW) {

    for (int i = 0; i < edges.size(); i++) {
        Edge e = edges.get(i);
        if (e.contains(iW)) {
            if (e.contains(iV)) {
                edges.remove(i);
                i--;
            } else {
                e.replace(iW, iV);
            }
        }
    }

    vertices.remove(iW);
}

public int kargerContraction(){

    Graph copy = new Graph(this);
    Random r = new Random();
    while(copy.getVertices().size() > 2){
        int i = r.nextInt(copy.getEdges().size());
        Edge e = copy.getEdges().get(i);
        copy.mergeVertex(e.getVertices()[0], e.getVertices()[1]);
    }

    return copy.getEdges().size()/2;
}
4

1 回答 1

1

其实问题比我想象的要简单得多。在读取包含图形数据的 .txt 时，我对每条边进行了两次计数，因此从逻辑上讲，返回的 minCut 是正确 minCut 的 2 倍。

于 2015-08-11T17:32:02.913 回答