卡格尔算法

Question

我正在尝试在 Java 中实现最小割 Karger 算法。为此，我创建了一个 Graph class 来存储一个 SortedMap，其中一个整数索引作为键，一个 Vertex 对象作为值，还有一个由 Edge 对象组成的 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;
}

Answer 1

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

卡格尔算法

Karger's Algorithm

java

algorithm

graph-theory

vertices

kargers-algorithm