「ライブラリ」の編集履歴（バックアップ）一覧はこちら

ライブラリ - (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 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;
     }
 }