使用 Union-Find 实现 Karger 最小割算法的问题
Issues in Implementing Karger's Min Cut Algorithm using Union-Find
我已经使用 Union-Find 数据结构实现了 Karger 算法,使用 Path-Compression Heuristics 和 Union by Rank 但是我 运行 遇到了几个问题
我基本上所做的是,我 运行 算法 NNlog(N) 时间来很好地估计答案。但是,我只是没有得到 MinCut 的答案。我每次选择一个随机边缘,它有 2 个成员源 's' 和目标 'd'。如果它们的 parent 不相等,我将它们合并并减少顶点数,'vcnt' 最初等于原始顶点数。这个过程一直持续到剩下的顶点数为 2。最后,我找到每条边的源和目标的 parent,如果它们不相等,我增加 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);
}
}
测试数据:(源顶点-> 连接的顶点)
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
Link: http://ideone.com/QP62FN
谢谢
该算法表明每条边被选择用于合并的可能性相同。
但是您的代码从不选择索引 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);
现在应该可以了。
我已经使用 Union-Find 数据结构实现了 Karger 算法,使用 Path-Compression Heuristics 和 Union by Rank 但是我 运行 遇到了几个问题
我基本上所做的是,我 运行 算法 NNlog(N) 时间来很好地估计答案。但是,我只是没有得到 MinCut 的答案。我每次选择一个随机边缘,它有 2 个成员源 's' 和目标 'd'。如果它们的 parent 不相等,我将它们合并并减少顶点数,'vcnt' 最初等于原始顶点数。这个过程一直持续到剩下的顶点数为 2。最后,我找到每条边的源和目标的 parent,如果它们不相等,我增加 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);
}
}
测试数据:(源顶点-> 连接的顶点)
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
Link: http://ideone.com/QP62FN
谢谢
该算法表明每条边被选择用于合并的可能性相同。
但是您的代码从不选择索引 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);
现在应该可以了。