回溯算法最大团和m着色问题java源程序

《回溯算法最大团和m着色问题java源程序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、实验报告12课程数据结构与算法实验名称回溯法第页班级11计本学号105032011130姓名风律澈实验日期：2013年5月27日报告退发(订正、重做)一、实验目的掌握回溯法的原理和应用。二、实验环境1、微型计算机一台2、WINDOWS操作系统，JavaSDK，Eclipse开发环境三、实验内容必做题：1、编写程序，采用回溯法求解最大团问题。2、编写程序，采用回溯法实现m着色问题。四、实验步骤和结果(附上代码和程序运行结果截图)1最大团publicclassMaxclique{/***@paramargs*/static

2、grapha;staticintn;//顶点数目staticintnowanswer[];//当前解staticintnowpointn;//当前顶点数量staticintnowmostpointn;//当前最多顶点子图staticintnowbestanswer[];//当前可能最优解publicstaticvoidmain(String[]args){//TODOAuto-generatedmethodstubintx[][]={{1,1,0,1,1},{1,1,1,0,1},{0,1,1,0,1},{1,0,0,

3、1,1},{1,1,1,1,1}};//初始化变量n=5;a=newgraph(x,n);nowanswer=newint[n];nowpointn=0;nowmostpointn=0;nowbestanswer=newint[n];nowbestanswer=a.getpoint(1).getreach();nowanswer[0]=1;//进入算法backtrack(0);//输出解System.out.println(nowmostpointn);for(inti=0;i

4、){System.out.print(nowanswer[i]+"");}}privatestaticvoidbacktrack(inti){//TODOAuto-generatedmethodstubif(i>n-1){for(intj=0;j

5、ack(i+1);nowpointn--;}elseif(nowpointn+n-i>nowmostpointn){nowanswer[i]=0;backtrack(i+1);}}}——————————————————————————————————publicclassgraph{privatepointp[];publicgraph(intx[][],intn){p=newpoint[x.length];for(inti=0;i

6、npointnumber(){returnp.length;}publicintcheck(inti,int[]x){//TODOAuto-generatedmethodstubintok=1;for(intj=0;j

7、blicclasspoint{privateintreach[];publicpoint(intx[]){this.reach=x;};publicintreachornot(intj){returnreach[j];}publicint[]getreach(){returnreach;}}———————————————————————————————————————2，m着色问题publicclassColoring{/***@paramargs*/staticintn,m;staticint[][]a;static

8、int[]x;staticlongsum;publicstaticlongmColoring(intmm){m=mm;sum=0;backtrack(1);returnsum;}privatestaticvoidbacktrack(intt){//TODOAuto-generatedmethodstubif(t>n){sum++;