求一个Karger-Stein随机算法实现求无向图全局最小割的带注释的java实现代码！
最近正在学习karger-stein随机算法求无向图的全局最小割，想看看实现方法，网上搜的源码都是别的语言的看不太懂。希望有人能提供一份java版本实现karger-stein随机算法求全局最小割的代码，其他语言的看不太懂.。输入的无向图可以用邻接表形式存储并作为输入来处理，如果可以的话加一些注释这样我可能能看懂。感谢各位！
Kanger.java
package lesson_4;
import java.util.*;
import java.util.concurrent.ThreadLocalRandom;
public class Karger {
public static void main(String[] args) {
Karger karger = new Karger();
Map<Character, Set<Integer>> graph = karger.getRandomGraph(50, 100);
karger.printGraph(graph);
int n = graph.size();
int iterationCount = 5 * n * (n - 1);
int result = karger.runAlgorithm(graph, iterationCount);
System.out.println("Smallest cut – " + result);
}
public int runAlgorithm(Map<Character, Set<Integer>> graph, int count) {
int minCut = Integer.MAX_VALUE;
while (count > 0) {
Map<Character, Set<Integer>> copy = new HashMap<>(graph);
int cutsNumber = randomCut(copy);
if (cutsNumber < minCut)
minCut = cutsNumber;
count--;
}
return minCut;
}
// find the smallest cut (edges number)
protected int randomCut(Map<Character, Set<Integer>> graph) {
int cutsNumber = 0;
// create common set of edges
Set<Integer> totalSet = new HashSet<>();
for (Map.Entry<Character, Set<Integer>> entry: graph.entrySet())
totalSet.addAll(entry.getValue());
// algorithm is executed until there are 2 vertices left
while (graph.size() != 2) {
// берется рандомное ребро и запускается шаг алгоритма
int randomEdge = getRandomElement(totalSet);
kargetStep(graph, randomEdge, totalSet);
}
// calculation and section print
System.out.println("Cut: ");
for (Map.Entry<Character, Set<Integer>> entry: graph.entrySet()) {
for (Integer edge : entry.getValue())
System.out.print(edge + " ");
System.out.println();
cutsNumber = entry.getValue().size();
break;
}
return cutsNumber;
}
// execute a step of the algorithm with vertex contraction
protected void kargetStep(Map<Character, Set<Integer>> graph, int randomEdge, Set<Integer> totalSet) {
// find vertices of this edge
Map.Entry<Character, Set<Integer>> firstVertex = null;
Map.Entry<Character, Set<Integer>> secondVertex = null;
for (Map.Entry<Character, Set<Integer>> entry: graph.entrySet()) {
if (entry.getValue().contains(randomEdge)) {
if (firstVertex == null)
firstVertex = entry;
else
secondVertex = entry;
}
}
assert firstVertex != null;
assert secondVertex != null;
// Two vertices converge into one
Set<Integer> commonVertex = new HashSet<>(firstVertex.getValue());
commonVertex.addAll(secondVertex.getValue());
// Loops are removed
Set<Integer> vertexWithoutLoops = new HashSet<>();
for (Integer edge : commonVertex) {
boolean loop = firstVertex.getValue().contains(edge) && secondVertex.getValue().contains(edge);
if (!loop)
vertexWithoutLoops.add(edge);
else
totalSet.remove(edge);
}
// The first vertex is updated, the second one is deleted
graph.put(firstVertex.getKey(), vertexWithoutLoops);
graph.entrySet().remove(secondVertex);
}
// remove a random element from the set
protected <T> T getRandomElement(Set<T> set) {
int index = ThreadLocalRandom.current().nextInt(set.size());
int i = 0;
for (T e : set) {
if (i == index) {
set.remove(e);
return e;
}
i++;
}
return null;
}
// get static created graph
protected Map<Character, Set<Integer>> getStaticGraph() {
Map<Character, Set<Integer>> graph = new HashMap<>();
graph.put('A', Set.of(1, 2));
graph.put('B', Set.of(1, 3));
graph.put('C', Set.of(2, 4, 5));
graph.put('D', Set.of(3, 4, 6, 7));
graph.put('E', Set.of(5, 6, 8));
graph.put('F', Set.of(7, 8, 9));
graph.put('G', Set.of(9));
return graph;
}
// get randomly generated graph
protected Map<Character, Set<Integer>> getRandomGraph(int vertexCount, int edgeCount) {
Map<Character, Set<Integer>> graph = new HashMap<>();
ThreadLocalRandom random = ThreadLocalRandom.current();
// create graph without edges
char[] vertexes = new char[vertexCount];
char key = 'A';
for (int i = 0; i < vertexCount; i++) {
vertexes[i] = key;
graph.put(key, new HashSet<>());
key++;
}
for (int i = 0; i < edgeCount; i++) {
// obtain two random vertices
int firstIndex = Math.abs(random.nextInt(vertexCount));
int secondIndex = Math.abs(random.nextInt(vertexCount));
while (secondIndex == firstIndex)
secondIndex = Math.abs(random.nextInt(vertexCount));
char firstVertex = vertexes[firstIndex];
char secondVertex = vertexes[secondIndex];
// add common edge to the vertices
graph.get(firstVertex).add(i);
graph.get(secondVertex).add(i);
}
// remove vertices without edges from the graph
graph.entrySet().removeIf(entry -> entry.getValue().size() == 0);
return graph;
}
// print graph to console
protected void printGraph(Map<Character, Set<Integer>> graph) {
for (Map.Entry<Character, Set<Integer>> entry: graph.entrySet()) {
System.out.println(entry);
}
}
}
KargerStein.java
package lesson_4;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
public class KargerStein extends Karger {
public static void main(String[] args) {
KargerStein kargerStein = new KargerStein();
Map<Character, Set<Integer>> graph = kargerStein.getRandomGraph(50, 100);
int result = kargerStein.runSteinAlgorithm(graph);
System.out.println("Smallest cut – " + result);
}
// run the algorithm
public int runSteinAlgorithm(Map<Character, Set<Integer>> graph) {
int iterationCount = (int) Math.round(Math.sqrt(graph.size()));
// graph is shrinking
contractGraph(graph);
// run main algorithm
return runAlgorithm(graph, iterationCount);
}
// pull the graph several times
private void contractGraph(Map<Character, Set<Integer>> graph) {
int size = (int) Math.floor(Math.sqrt(graph.size()));
Set<Integer> totalSet = new HashSet<>();
for (Map.Entry<Character, Set<Integer>> entry: graph.entrySet())
totalSet.addAll(entry.getValue());
while (graph.size() != size) {
int randomEdge = getRandomElement(totalSet);
kargetStep(graph, randomEdge, totalSet);
}
}
}
在Karger的算法中，随机选择一个边，然后收缩所选的边缘，从而产生一个超级节点。该过程将继续，直到图中只剩下两个超级节点。这两个超级节点代表了原始图形中的切割GG.
由于Karger算法是“蒙特卡罗”算法，因此通过多次重复算法，可以找到图形的最小切口，并且概率很高。
//导入必要文件
//模块输入/输出。
import java.util.*;
class MinCut{
//声明变量
// V, E,parent和Rank
static int V,E;
static int parent[];
static int rank[];
//获取随机模块
//随机整数值。
static Random rand;
//构造函数
MinCut(int V, int E){
//初始化变量
this.V=V;
this.E=E;
parent=new int[V];
rank=new int[V];
rand = new Random();
//使用is和0来初始化父元素和rank元素。
for(int i=0;i<V;i++)
{
parent[i]=i;
rank[i]=0;
}
}
//函数查找最小切割。
static int minCutKarger(Edge edges[]){
int vertices=V;
//迭代到顶点大于2为止。
while(vertices>2)
{
//获取范围[0,E-1]的随机整数。
int i=rand.nextInt(E);
// 查找边为[i]的首元素
int set1=find(edges[i].u);
//查找边[i]的前导元素
int set2=find(edges[i].v);
//如果它们不属于同一个集合。
if(set1!=set2)
{
System.out.println("收缩顶点 "+edges[i].u+" 和 "+edges[i].v);
//将顶点u和v合并为一个
union(edges[i].u,edges[i].v);
//减少顶点数1。
vertices--;
}
}
System.out.println("需要去除边缘- ");
//将answer (minCut)初始化为0。
int ans=0;
for(int i=0;i<E;i++)
{
//查找边为[i]的首元素
int set1=find(edges[i].u);
//查找边为[i]的前导元素
int set2=find(edges[i].v);
// 如果它们不在同一个集合中。
if(set1!=set2)
{
System.out.println(edges[i].u+" <----> "+edges[i].v);
//增加ans
ans++;
}
}
return ans;
}
//查找函数
public static int find(int node){
//如果节点是它自己的父节点，那么它就是树的leader。
if(node==parent[node]) return node;
//否则，查找父路径并压缩路径。
return parent[node]=find(parent[node]);
}
//联合函数
static void union(int u,int v){
//U做这棵树的首节点。
u=find(u);
// v作为它的树的首节点
v=find(v);
// 判断u和v是否相等，因为如果它们相等，这意味着它们已经在同一棵树中，执行联合操作没有意义。
if(u!=v)
{
//检查是否较小的深度/高度。
if(rank[u]<rank[v])
{
int temp=u;
u=v;
v=temp;
}
//将低秩树附加到高秩树。
parent[v]=u;
//如果现在rank相等，则增加u的rank。
if(rank[u]==rank[v])
rank[u]++;
}
}
//边缘类
static class Edge{
//边e的端点u和v。
int u;
int v;
//初始化的构造函数。
Edge(int u,int v){
this.u=u;
this.v=v;
}
}
//驱动函数
public static void main(String args[]){
//预先定义V和E
int V=5,E=7;
//创建MinCut类的对象。
MinCut minCut=new MinCut(V,E);
//通过给出边的端点来创建一个边数组。
Edge edge[]=new Edge[E];
edge[0]=new Edge(0,3);
edge[1]=new Edge(3,2);
edge[2]=new Edge(2,1);
edge[3]=new Edge(1,0);
edge[4]=new Edge(0,2);
edge[5]=new Edge(2,4);
edge[6]=new Edge(4,1);
//找到最小切割的大小。
System.out.println("需要移除的边数 "+ MinCut.minCutKarger(edge));
}
}
可以参考下文
https://www.jianshu.com/p/7f843dbcab1b
import java.io.IOException;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Scanner;
public class KargerMinCut {
public static void main(String[] args) throws IOException {
KargerMinCut mc = new KargerMinCut();
int min = mc.mincut();
for (int i = 0; i < 1000; i++){
mc = new KargerMinCut();
int ans = mc.mincut();
if ( ans < min) {
min = ans;
}
}
System.out.println(min);
}
// 图的数据结构，存储每一条边
List<HashSet<Integer>> vergroups = new LinkedList<>();
HashSet<ArrayList<Integer>> Graph = new HashSet<>();
public int mincut() throws IOException {
Random r = new Random();
HashSet<Integer> vertices = new HashSet<>();
int vsize = 0;
Scanner in1 = new Scanner(Paths.get("")); // 文件路径
while (in1.hasNextLine()) {
vsize++;
String line = in1.nextLine();
Scanner readInt = new Scanner(line);
int v = readInt.nextInt();
while (readInt.hasNextInt()) {
Graph.add(new ArrayList<Integer>() {{ add(v); add(readInt.nextInt());}});
}
readInt.close();
}
in1.close();
for (int i=1; i<=vsize; i++) {
vertices.add(i);
}
while (true) {
if ((vergroups.size()==2 && vertices.size()==0) ||
((vergroups.size()==1) && vertices.size()==1)) {
break;
}
ArrayList[] a = new ArrayList[0];
ArrayList<Integer>[] g = Graph.toArray(a);
ArrayList<Integer> pair = g[r.nextInt(g.length)];
int v = pair.get(0);
int u = pair.get(1);
Iterator<HashSet<Integer>> i = vergroups.iterator();
HashSet<Integer> conV = new HashSet<Integer>();
HashSet<Integer> conU = new HashSet<Integer>();
if (!i.hasNext()) {
vergroups.add(new HashSet<Integer>(pair));
vertices.remove(u);
vertices.remove(v);
}
else
while (i.hasNext()) {
HashSet<Integer> h = i.next();
if (h.contains(v)) {
conV = h;
}
else if (h.contains(u)) {
conU = h;
}
}
if (conV.contains(v) && !conU.contains(u)) {
conV.add(u);
vertices.remove(u);
removeloop(conV, v, u);
}
else if (!conV.contains(v) && conU.contains(u)) {
conU.add(v);
vertices.remove(v);
removeloop(conU, u, v);
}
else if (!conV.contains(v) && !conU.contains(u) && !vergroups.contains(new HashSet<Integer>(pair))) {
vergroups.add(new HashSet<Integer>(pair));
vertices.remove(u);
vertices.remove(v);
}
else if (conV.contains(v) && conU.contains(u)) {
conV.addAll(conU);
vergroups.remove(conU);
removeloop(conV, conU, v, u);
}
deledge(v, u);
}
return Graph.size()/2;
}
public void deledge(int v, int u) {
List<Integer> t1 = new ArrayList<Integer>(2);
t1.add(v); t1.add(u);
List<Integer> t2 = new ArrayList<Integer>(2);
t2.add(u); t2.add(v);
Graph.remove(t1);
Graph.remove(t2);
}
public HashSet<Integer> preprocess(int v, int u) {
for (HashSet<Integer> h : vergroups) {
if (h.contains(v)) return h;
else if (h.contains(u)) return h;
}
return null;
}
public void removeloop(HashSet<Integer> h, int v, int u) {
for (Integer l : h) {
if (l != u && l != v) {
deledge(l, u);
System.out.println("l:" + l + " " + "u:" + u);
}
}
}
public void removeloop(HashSet<Integer> V, HashSet<Integer> U, int v, int u) {
for (Integer exu : U) {
if (exu != u)
for (Integer j : V) {
deledge(exu, j);
}
}
}
}
全局最小割 stoer-wagner与karger-stein算法_weixin_34402408的博客-CSDN博客 stoer-wagner算法进行n轮操作，每轮操作确定一对点s,t被割开情况下的最小割，然后将s,t合并。s,t为操作中最后剩下的两个点。操作类似prim求最大生成树，每次将与当前集合相邻的距离最大的点合并到集合中，最后剩下s,t两点。代码来自wikiconst int maxn = 550;const int inf = 1000000000;int n, r;... 
https://blog.csdn.net/weixin_34402408/article/details/94637985
你可以参考下如下链接https://blog.csdn.net/weixin_34402408/article/details/94637985
虽然是c语言的，但是你可以搜一些工具将代码转成java代码
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <map>
#define ULL unsigned long long
#define LDB long double
using namespace std;
ULL sed=233;
int top,deg[5010],b[5010][5010],totdeg,n,m,succ[5010],prev[5010],faqcnt=0;
map <int,int> mp;
struct data{
int x,y,k,num;
}sta[5000*5000+1];
ULL ran(){
sed*=1280313;sed+=12413;sed^=123893;
return(sed);
}
void restore(int tar){
while (top>tar){
data t=sta[top];top--;
int x=t.x,y=t.y,i=t.k,num=t.num;
if (t.k==-1){
deg[x]+=num;deg[y]+=num;
b[x][y]=b[y][x]=num;
totdeg+=2*num;
succ[prev[x]]=x;prev[succ[x]]=x;
}else{
deg[x]+=num;deg[y]-=num;
b[y][i]=(b[i][y]-=num);
b[x][i]=b[i][x]=num;
}
}
}
void contract(int x,int y){
sta[++top]=(data){x,y,-1,b[x][y]};
deg[x]-=b[x][y];deg[y]-=b[x][y];
totdeg-=2*b[x][y];
b[x][y]=b[y][x]=0;
prev[succ[x]]=prev[x];succ[prev[x]]=succ[x];
for (int i=0;i<=n;i=succ[i]) if (b[x][i]){
sta[++top]=(data){x,y,i,b[x][i]};
deg[x]-=b[x][i];deg[y]+=b[x][i];
b[y][i]=(b[i][y]+=b[x][i]);
b[x][i]=b[i][x]=0;
}
}
void del(){
int tar=ran()%totdeg+1,x,y;
for (x=0;tar>deg[x];tar-=deg[x],x=succ[x]);
for (y=0;tar>b[x][y];tar-=b[x][y],y=succ[y]);
contract(x,y);
}
int slowsolve(int po){
int ttop=top;
for (int i=1;i<=po-2;i++) del();
int ret=totdeg/2;
restore(ttop);
return(ret);
}
int fastsolve(int po){
int ttop=top,ret=1e9;mp[po]++;
if (po<=20){
int ret=1e9;
for (int i=1;i<=100;i++){
ret=min(ret,slowsolve(po));
restore(ttop);
}
return(ret);
}
int tar=ceil(1+po/sqrt(2));
for (int i=1;i<=po-tar;i++) del();
ret=min(ret,fastsolve(tar));
restore(ttop);
for (int i=1;i<=po-tar;i++) del();
ret=min(ret,fastsolve(tar));
restore(ttop);
return(ret);
}
int main(){
scanf("%d%d",&n,&m);
prev[n+1]=n;succ[0]=1;
for (int i=1;i<=n;i++) prev[i]=i-1,succ[i]=i+1;
for (int i=1;i<=m;i++){
int t1,t2;
scanf("%d%d",&t1,&t2);
deg[t1]++;deg[t2]++;b[t1][t2]++;b[t2][t1]++;
totdeg+=2;
}
int ans=1e9;
for (int i=1;i<=10;i++){
int t=fastsolve(n);
ans=min(ans,t);
printf("%d\n",t);
}
printf("%d\n",ans);
}