알고리즘 자바 실현 - 분기 한계 법 - 최대 단 문제

최대 그룹 문제 의 자바 구현 (우선 대기 열 식 분기 한계 법)
구체 적 인 문제 설명 및 C / C + + 참조 사이트 구현
http://blog.csdn.net/liufeng_king/article/details/8951722

import java.util.Collections;
import java.util.LinkedList;

/**
 *           --     
 * @author lican
 *
 */
public class BBClique {
	public int [][]a;// G     
	public LinkedList heap;
	public BBClique(int[][] a){
		this.a=a;
		heap=new LinkedList();
	}
	/**
	 *                               
	 * @param up
	 * @param size
	 * @param lev
	 * @param par
	 * @param ch
	 */
	public void addLiveNode(int up,int size,int lev,BBnodes par,boolean ch){
		BBnodes enode=new BBnodes(par,ch);
		HeapNodes h=new HeapNodes(enode,up,size,lev);
		heap.add(h);
		Collections.sort(heap);
	}
	
	/**
	 *                     
	 * @param bestx          
	 * @return
	 */
	public int bbMaxClique(int[] bestx){
		int n=bestx.length-1;
		
		//   (    )
		BBnodes enode=null;
		int i=1;
		int cn=0;
		int bestn=0;
		
		//       
		while(i!=n+1){//    
			boolean ok=true;
			BBnodes bnode=enode;
			for(int j=i-1;j>0;j--){
				if(bnode.leftChild&&a[i][j]==0){
					ok=false;
					break;
				}
				bnode=bnode.parent;
			}
			if(ok){//          
				if(cn+1>bestn)
					bestn=cn+1;
				addLiveNode(cn+n-i+1,cn+1,i+1,enode,true);
			}
			if(cn+n-i>=bestn){//          
				addLiveNode(cn+n-i,cn,i+1,enode,false);
			}
			
			//        
			HeapNodes node=heap.poll();
			enode=node.liveNode;
			cn=node.cliqueSize;
			i=node.level;
		}
		
		//       
		for(int j=n;j>0;j--){
			bestx[j]=enode.leftChild?1:0;
			enode=enode.parent;
			System.out.print(bestx[j]+" ");
		}
		System.out.println();
		return bestn;
	}
	
	public static void main(String[] args) {
		int[][] a={{-1,-1,-1,-1,-1,-1},{-1,0,1,0,1,1},{-1,1,0,1,0,1},{-1,0,1,0,0,1},{-1,1,0,0,0,1},{-1,1,1,1,1,0}};//a    1  ，-1    
		int n=5;
		int[] bestx=new int[n+1];
		BBClique b=new BBClique(a);
		System.out.println(" G        ：");
		int best=b.bbMaxClique(bestx);				
		System.out.println(" G        ："+best);
	}
}


/**
 *           BBnodes
 * @author Lican
 *
 */
class BBnodes{
	BBnodes parent;//   
	boolean leftChild;//      
	public BBnodes(BBnodes par,boolean left){
		this.parent=par;
		this.leftChild=left;
	}
}
/**
 *              HeapNode
 * @author Lican
 *
 */
class HeapNodes implements Comparable{
	BBnodes liveNode;
	int upperSize;//          
	int cliqueSize;///       
	int level;//
	
	public HeapNodes(BBnodes node,int up,int size,int lev){
		liveNode=node;
		upperSize=up;
		cliqueSize=size;
		level=lev;
	}

	@Override
	public int compareTo(Object x) {//    
		int ux=((HeapNodes) x).upperSize;
		if(upperSize>ux) return -1;
		if(upperSize==ux) return 0;
		return 1;
	}
}

/*
    ：
 G        ：
1 0 0 1 1 
 G        ：3
 */