java - 使用 Union-Find 实现 Karger 最小割算法的问题

Question

我已经使用路径压缩启发式算法和按等级联合的联合查找数据结构实现了 Karger 算法，但我遇到了几个问题

我基本上所做的是，我运行算法 NNlog(N) 次以获得对答案的良好估计。但是，我只是没有得到 MinCut 的答案。我每次都选择一个随机边缘，它有 2 个成员，源 's' 和目标 'd'。如果它们的 parent 不相等，我合并它们并减少顶点数，'vcnt' 最初等于原始顶点数。这个过程一直持续到剩下的顶点数为 2。最后，我找到每条边的源和目标的父级，如果它们不相等，我增加 MinCut 计数。这将重复 NNLog(N) 次。

我已经尝试使用大量测试数据运行我的代码，但我似乎没有获得 Mincut 值，尤其是对于大数据。

谁能帮帮我？此外，欢迎提出性能改进建议。这是代码:

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class KragersMinCut
{
    static int n=200;//Number of Vertices
    static int[] u=new int[n];
    static int[]rank =new int[n];

    static class Edge //Edge which hols the source and destination
    {
        int s,d;//Source,Destination
        Edge(int s,int d)
        {
            this.s=s;
            this.d=d;
        }
    }

    private static void InitializeUnionFindData()
    {
        for(int i=0;i<n;i++)
        {
            u[i]=i;
            rank[i]=1;
        }
    }

    private static int FIND(int xx) //Finding Parent using Path-Compression Heuristics
    {
        if(u[xx]!=u[u[xx]])
        {
            u[xx]=FIND(u[xx]);
        }
        return u[xx];
    }

    private static boolean UNION(int x,int y) //Union by Order-by-Rank to create evenly balanced search trees
    {
    int px=FIND(x),py=FIND(y);
    if(rank[px]>rank[py])
    {
        int temp=px;
        px=py;
        py=temp;
    }
    else if(rank[px]==rank[py])
        rank[py]++;

    u[px]=py;
    return true;
    }


    public static void main(String[] args) throws IOException
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        ArrayList<Edge> EdgeList=new ArrayList<Edge>();
        for(int i=0;i<n;i++)
        {
            String x=br.readLine();
            ArrayList<Integer>al=new ArrayList<Integer>();
            for(int j=0;j<x.length();j++) //This loop is for parsing the input format
            {
                if(x.charAt(j)<48 || x.charAt(j)>57)
                    continue;

                int p=j;
                String input="";
                while(p!=x.length()&&(x.charAt(p)>=48 && x.charAt(p)<=57))
                {
                    input+=(x.charAt(p));
                    p++;
                }
                j=p;
                al.add(Integer.parseInt(input.trim())-1);
            }
            for(int j=1;j<al.size();j++)
            {
                EdgeList.add(new Edge(al.get(0),al.get(j)));//Source,Destination
            }
        }
        //Edge list ready
        int MinCut=Integer.MAX_VALUE;
        for(int q=0;q<(n*n)*Math.log(n);q++)//Running theta(n^2*ln(n)) times for a good estimate. Runs in about 20 secs
        {
            int vcnt=n;//Essentially n
            InitializeUnionFindData();
            while(vcnt>2)
            {
                Edge x=EdgeList.get((int)(Math.random()*(EdgeList.size()-1)+1));//Obtaining random valued element at index from EdgeList
                int s=x.s,d=x.d;
                int ps=FIND(s),pd=FIND(d);
                if(ps!=pd)//Contracting. Essentially making their parents equal
                {
                    UNION(s,d);
                    vcnt--;
                }
            }
            int CurrMinCutValue=0;
            for(Edge i:EdgeList)
            {
                int px=FIND(i.s),py=FIND(i.d);
                if(px!=py)//Since they belong to different Vertices
                {
                    CurrMinCutValue++;
                }
            }
            MinCut=Math.min(MinCut,CurrMinCutValue);//Finding Minimum cut of all random runs
        }
        System.out.println(MinCut);
    }
}    

TestData: (Source Vertex-> Connected Vertices)

1 2 3 4 7

2 1 3 4

3 1 2 4

4 1 2 3 5

5 4 6 7 8

6 5 7 8

7 1 5 6 8

8 5 6 7

答案:4 |预期答案:2

链接:http://ideone.com/QP62FN

谢谢

Answer 1

该算法表明每条边被选中进行合并的可能性均等。

但是您的代码永远不会选择索引 0 处的边缘。

所以修改行:

Edge x=EdgeList.get((int)(Math.random()*(EdgeList.size()-1)+1));

为此:

Edge x=EdgeList.get((int)(Math.random()*(EdgeList.size())));

还因为每条边都在边列表中列出了两次:

您应该打印以下内容

System.out.println(MinCut/2);

现在它应该可以工作了。