最大团问题回溯法子集树
5星 · 超过95%的资源 需积分: 13 111 浏览量
2013-01-02
14:49:19
上传
评论 1
收藏 29KB DOC 举报 
/*
* 最大团问题-回溯法-子集树
* time：2012-1-2
* 下标从 1 开始
*/
package com.book.java;
public class Project40_MaxClique {
public static int n;
public static int edge[][]={{0,0,0,0,0,0},
{0,0,1,0,1,1},
{0,1,0,1,0,1},
{0,0,1,0,0,1},
{0,1,0,0,0,1},
{0,1,1,1,1,0}};//存放图的连接矩阵其中，没有边
相互连接用 0 表示，顶点相同用 0 表示
public static int x[]; //用来存放最大团的数组
public static int bestx[];//用来存放最大团的组成
public static int cur;//用来存放当前最大团中的个数
public static int bestcur;//用来存放最佳最大团中的个数
public static int remain;//用来在剪去右的时候使用
public static void main(String[] args) {
n=edge.length-1;
// n=3;
x=new int[n+1];
bestx=new int[n+1];
remain=n;
cur=0;
bestcur=0;
maxClique(1);
System.out.println("最大团的个数为:"+bestcur);
System.out.println("组成如下:");
for(int i=1;i<=n;i++)
{
System.out.print(bestx[i]+" ");
}
}
public static boolean decide(int num)//选择的点到前面所选点的点都有连接，
则返回 true，否则返回 false
{
for(int i=1;i<num;i++)
{
if(x[i]==1)//查看相应的点存在 x[i]数组中，如果存在则进行下一步的判断，
不存在，则跳过
{
if(edge[num][i]==0)//判断这个点和目标是否有连线，没有连线则表示不
能成为完全子图
{
return false;
}
}
}
return true;
}
资源评论
songzelu2015-05-12对我非常有用
