3

我正在尝试实现 Karger 的最小切割算法，但我无法得到正确的答案。有人可以看看我的代码并帮助我找出我做错了什么吗？非常感谢您的帮助。

package a3;

import java.util.*;
import java.io.*;

public class Graph {

private ArrayList<Integer>[] adjList;
private int numOfVertices = 0;
private int numOfEdges = 0;


public Graph(String file) throws IOException {
    FileInputStream wordsFile = new FileInputStream(file);
    BufferedReader br = new BufferedReader(new InputStreamReader(wordsFile));
    adjList = (ArrayList<Integer>[]) new ArrayList[201];
    for (int i = 1; i < 201; i++) {
        adjList[i] = new ArrayList<Integer>();
    }
    while (true) {

        String s = br.readLine();

        if (s == null)
            break;
        String[] tokens = s.split("\t");
        int vertex = Integer.parseInt(tokens[0]);
        this.numOfVertices++;

        for (int i = 1; i < tokens.length; i++) {

            Integer edge = Integer.parseInt(tokens[i]);
            addEdge(vertex, edge);
            this.numOfEdges++;

        }

    }
}

public void addEdge(int v, int w) {
    adjList[v].add(w);
    //this.numOfEdges++;

}

public ArrayList<Integer> getNeighbors(Integer v) {
    return adjList[v];
}

public boolean hasEdge(Integer i, Integer j) {
    return adjList[i].contains(j);
}

public boolean removeEdge(Integer i, Integer j) {
    if (hasEdge(i, j)) {
        adjList[i].remove(j);
        adjList[j].remove(i);
        this.numOfEdges -= 2;
        return true;
    }
    return false;
}

public int getRandomVertex(){
    Random rand = new Random();
    return (rand.nextInt(this.getNumOfVertices()) + 1);
}

//Returns an array which consists of vertices connected by chosen edge
public int[] getRandomEdge(){
    int arr[] = new int[2];
    arr[0] = this.getRandomVertex();
    while (adjList[arr[0]].size() == 0) {
        arr[0] = this.getRandomVertex();            
    }

    Random rand = new Random();
    arr[1] = adjList[arr[0]].get(rand.nextInt(adjList[arr[0]].size()));
    return arr;
}

//Algorithm for min cut
public int minCut() {
    while (this.getNumOfVertices() > 2) {
        int[] edge = this.getRandomEdge();
        this.removeEdge(edge[0], edge[1]);
        //Adding edges of second vertex to first vertex
        for (Integer v: adjList[edge[1]]) {
            if (!adjList[edge[0]].contains(v)) {
                addEdge(edge[0], v);
            }               
        }

        //Removing edges of second vertex
        for (Iterator<Integer> it = adjList[edge[1]].iterator(); it.hasNext();) {
            Integer v = it.next();
            it.remove();
            this.numOfEdges--;
        }

        //Removing self-loops
        for (Iterator<Integer> it = adjList[edge[0]].iterator(); it.hasNext();) {
            Integer v = it.next();
            if (v == edge[0]) 
                it.remove();
                //this.numOfEdges--;
        }

        this.numOfVertices--;

    }
    return this.numOfEdges;
}

public int getNumOfVertices() {
    return this.numOfVertices;
}

public int getNumOfEdges() {
    return (this.numOfEdges) / 2;
}

public String toString() {

    String s = "";
    for (int v = 1; v < 201; v++) {
        s += v + ": ";
        for (int e : adjList[v]) {
            s += e + "-> ";
        }
        s += null + "\n";
        //s += "\n";
    }
    return s;
}

/**
 * @param args
 * @throws IOException
 */
public static void main(String[] args) throws IOException {
    // TODO Auto-generated method stub
    int min = 1000;
    //Graph test = new Graph("C:\\Users\\UE\\Desktop\\kargerMinCut.txt");
    for (int i = 0; i < 10; i++) {
        Graph test = new Graph("C:\\Users\\UE\\Desktop\\kargerMinCut.txt");
        int currMin = test.minCut();
        min = Math.min( min, currMin );            
    }

    System.out.println(min);
}

}
4

0 回答 0