「ライブラリ」の編集履歴（バックアップ）一覧に戻る

ライブラリ - (2006/05/23 (火) 02:24:44) の編集履歴(バックアップ)

---

高速Kruskal with 高速MFSet

O(NlogN)のMFsetを用いたKruskalのアルゴリズム．

class KruskalSolver{
    int n;
    double[][] dist;
    double len;
    private PriorityQueue<Edge> q;
    KruskalSolver(int n,double dist[][]){
        this.n = n;
        this.dist = dist;
        this.q = new PriorityQueue<Edge>();
        this.len = 0.0;
        
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(dist[i][j]<Double.MAX_VALUE){
                    q.offer(new Edge(i, j, dist[i][j]));
                }
            }
        }
        
        //Kruskal's algorithm
        MFSet mfs = new MFSet(n);
        while(!q.isEmpty()){
            Edge e = q.poll();
            int i = e.p1;
            int j = e.p2;
            if(mfs.find(i)!=mfs.find(j)){
                mfs.merge(mfs.find(i),mfs.find(j));
                len += e.length;
            }
        }
    }
}

class Edge implements Comparable<Edge>{
    int p1;
    int p2;
    double length;
    Edge(int i,int j,double l){
        p1 = i;
        p2 = j;
        length = l;
    }
    public int compareTo(Edge e){
        if(length>e.length) return 1;
        else if(length==e.length) return 0;
        else return -1;
    }
}

class MFSet{
    int n;
    private int[] setsize;
    private int[] firstelem;
    private int[] set;
    private int[] next;
    MFSet(int n){
        this.n = n;
        setsize = new int[n];
        Arrays.fill(setsize, 1);
        firstelem = new int[n];
        for(int i=0;i<n;i++) firstelem[i] = i;
        set = new int[n];
        for(int i=0;i<n;i++) set[i] = i;
        next = new int[n];
        for(int i=0;i<n;i++) next[i] = -1;
    }
    int find(int x){
        return set[x];
    }
    void merge(int a, int b){
        if(setsize[a]<setsize[b]){
            merge(b, a);
            return;
        }
        int i = firstelem[b];
        while(next[i]>=0){
            set[i] = a;
            i = next[i];
        }
        set[i] = a;
        next[i] = firstelem[a];
        firstelem[a] = firstelem[b];
        setsize[a] = setsize[a] + setsize[b];
        setsize[b] = 0;
        firstelem[b] = -1;
    }
}

Kruskal

O(N^2)のMFSetを用いたKruskalのアルゴリズム．

class KruskalSolver{
    int n;
    double[][] dist;
    double len;
    private PriorityQueue<Edge> q;
    int[] set;
    KruskalSolver(int n,double dist[][]){
        this.n = n;
        this.dist = dist;
        this.len = 0.0;
        this.q = new PriorityQueue<Edge>();
        this.set = new int[n];
        for(int i=0;i<n;i++) set[i] = i;
        
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(dist[i][j]<Double.MAX_VALUE){
                    q.offer(new Edge(i, j, dist[i][j]));
                }
            }
        }
        
        //Kruskal's algorithm
        while(!q.isEmpty()){
            Edge e = q.poll();
            int i = e.p1;
            int j = e.p2;
            int si = set[i];
            int sj = set[j];
            if(si!=sj){
                len += e.length;
                for(int k=0;k<n;k++){
                    if(set[k]==sj) set[k] = si;
                }
            }
        }
    }
}

class Edge implements Comparable<Edge>{
    int p1;
    int p2;
    double length;
    Edge(int i,int j,double l){
        p1 = i;
        p2 = j;
        length = l;
    }
    public int compareTo(Edge e){
        if(length>e.length) return 1;
        else if(length==e.length) return 0;
        else return -1;
    }
}