Karger的算法实现

Question

该代码在较小的图形上运行良好，但当图形变得病态时会失败，就像这个。

我尝试过的一些较小的图表：

    // Example 1, 5 vertices, correct answer is 2
    /*
    1-----2
    | \   | \
    |  \  |   5
    |    \| /
    3-----4
    */

    G.addEdges(edge, 1, 2);
    G.addEdges(edge, 1, 3);
    G.addEdges(edge, 1, 4);
    G.addEdges(edge, 2, 4);
    G.addEdges(edge, 2, 5);
    G.addEdges(edge, 3, 4);
    G.addEdges(edge, 4, 5);

    // Example 2, 8 vertices, correct answer is 2
    // G.addEdges(edge, 1, 2);
    // G.addEdges(edge, 1, 3);
    // G.addEdges(edge, 1, 4);
    // G.addEdges(edge, 1, 7);
    // G.addEdges(edge, 2, 3);
    // G.addEdges(edge, 2, 4);
    // G.addEdges(edge, 3, 4);
    // G.addEdges(edge, 4, 5);
    // G.addEdges(edge, 5, 6);
    // G.addEdges(edge, 5, 7);
    // G.addEdges(edge, 5, 8);
    // G.addEdges(edge, 6, 7);
    // G.addEdges(edge, 6, 8);
    // G.addEdges(edge, 7, 8);

    // Example 3, 4 vertices, correct answer is 1
    // G.addEdges(edge, 0, 1);
    // G.addEdges(edge, 0, 2);
    // G.addEdges(edge, 0, 3);
    // G.addEdges(edge, 1, 3);

所以我的问题：

1. 是否可以在不使用并集查找、并集排名或路径压缩的概念的情况下实现 Karger 算法？我并不是故意回避它们，但到目前为止，我一直在学习的课程中，这些概念都没有被讨论过，甚至还没有被提及。

2. 如果可以的话，我对这个算法的理解哪部分是错误的？

我对算法的理解：

1. 随机选择一条边。

2. 在这个合并部分，我维护源代码，并更改 目的地到源，并用相同的方式更改其他边 目的地也到这个随机选择的源。例如，在 (1, 37) 中，1 是源，37 是目的地。例如选择 (1, 37), 将 37 更改为 1 以及其他包含 37 的边，如 (5, 37) 更改为 (5, 1) 或 (37, 69) 到 (1, 69)。

3. 继续做同样的事情，直到剩下两个顶点。

4. 计算最小割数，避免自循环。

5. 将整个过程进行多次并存储每次的结果 迭代。

6. 最后，选择结果中的最小值。

int minCut(Graph &graph, int &iteration){
    vector<int> result;

    while (iteration)
    {
        int cutEdges{}, vertices{graph.getV()};
        vector<int> vSrc, vDest;

        for (auto i = 0; i < graph.E(); i++)
        {
            vSrc.push_back(graph.adjList[i].src);
            vDest.push_back(graph.adjList[i].dest);
        }

        while (vertices > 2)
        {
            int mod;

            while (1) // Random pick, avoid self loops
            {
                mod = rand() % graph.E();
                if (vSrc[mod] != vDest[mod]) break;
            } 

            for (auto i = 0; i < graph.E(); i++) // Merge two vertices
            {                
                if (vSrc[i] == vDest[mod]) vSrc[i] = vSrc[mod];
                if (vDest[i] == vDest[mod]) vDest[i] = vSrc[mod];
            }
            vertices--;
        }

        for (auto i = 0; i < graph.E(); i++) // Count minimum cuts, ignore self loops
        {
            if (vSrc[i] != vDest[i]) cutEdges++;
        }
        
        result.push_back(cutEdges);
        iteration--;
    }
     
    return *min_element(result.begin(), result.end());
}

有人能指出我忽略或错过了哪些部分，或者对算法的整个理解完全错误吗？

Answer 1

Karger 算法（https://en.wikipedia.org/wiki/Karger%27s_algorithm）只有在高概率下才能成功。也就是说，有时会失败。看来您遇到过其中一种失败。

我推荐 Tarjan 算法（https://en.wikipedia.org/wiki/Biconnected_component）来查找最小割。

Tarjan 的 C++ 实现 https://github.com/JamesBremner/PathFinder/blob/main/src/tarjan.cpp