package kl;
import java.io.*;

//类 “点”是定义点的结构；
class 点
{
int value;//用于存放点值
int used;//用于记录这个点是否交换过，值为1时表示交换过，
}

//类 “change”里面的方法exchange()是用来交换两个点的；方法print()是用来输出集团情况的。
class change
{
static void exchange(点 A[],int i2,int j2)
{
int temp1,temp2;

temp1=A[i2].value;
temp2=A[i2].used;

A[i2].value=A[j2].value;
A[i2].used=A[j2].used;

A[j2].value=temp1;
A[j2].used=temp2;
}

static void print(PrintWriter out, 点 A[], int max, int m)throws IOException//把数据写到文件中
{
 int i;
 out.println("第一个集团的成员是:");
 for(i=0; i<max; i++)
 {
  if(i<m)
  {
   out.print(" "+A[i].value);
  }

  if(i==m){
   out.println(" ");
   out.println(" 第二个集团的成员是:");
  }
  

  if(i>=m)
   out.print(" "+A[i].value);
 }
}
}

public class Example {
 //main函数
   public static void main(String args[])throws IOException
   {
    int max,m;
    BufferedReader in=new BufferedReader(new FileReader("input.txt"));
    PrintWriter out=new PrintWriter(new FileWriter("output.txt"));
    System.out.println("下一步是接收集团所有点的个数max。\n");
    max=(int)Double.parseDouble(in.readLine());//最后转化为整型数据
    m=(int)Double.parseDouble(in.readLine());//最后转化为整型数据

点[] A=new 点[max];
    int[][]B=new int[max][max];
  
    String line1,line2;
    int t1,t2;

     System.out.println("m="+m+"\n下面是逐次输入有边连接的两个点，每次输入两个点，从文件中读取。\n");
     in.readLine();//此处用来读取中文字符“下面是逐次输入有边连接的两个点，每次输入两个点，从文件中读取”############☆★☆★☆★☆★☆★
  line1=in.readLine();//line1和line2是用来接收每两行数据
  line2=in.readLine();
  System.out.println(line1+"  "+line2);
  
  while(line1!=null&&line2!=null){
   t1=(int)Double.parseDouble(line1);//把line1和line2的字符串转化为整型数据。
   t2=(int)Double.parseDouble(line2);
   B[t1-1][t2-1]=1;
   B[t2-1][t1-1]=1;
   System.out.println(t1+"  "+t2);
   System.out.println("数组B["+(t1-1)+"]["+(t2-1)+"]="+B[t1-1][t2-1]);
   line1=in.readLine();//继续接收  next两行数据
   line2=in.readLine();
  }
  in.close();
  
  System.out.println("读取数据已经完成\n");
  
   int i,j,i1,j1;
   int count1=0,count2=0;  //count1和count2是用于交换点的过程中存放集团的边数。
   int signal=0;//signal是用来判断算法循环是否要跳出的标志，值为0时表示要跳出。

   for(i=0; i<max; i++)
    {
     点 g=new 点();//给A[]数组里边的每个元素初始化
     A[i]=g;
     A[i].value=i+1;
     A[i].used=0;
    
    }
  
   System.out.println("A[]初始化完成\n");
    out.println("交换前的集团情况是:");
    change.print(out,A,max,m);//打印集团情况
   
    for(i=0; i<m; i++)
    for(j=m; j<max; j++)
     if(B[i][j]==1)
       count2++;//扫描连接两个集团的边数

    count1=count2;//保存上一次扫描的边数在count1里

 //下面是交换两个点处理增益的过程，求最大增益，就是要求连接两个集团的边数最小。
  for(int time=0; ; time++)//循环做kernighthen-lin算法，循环体里有跳出循环的条件signal,值为0时跳出循环。
  {
    //###下面是执行一次kernighthen-lin算法#####
    for(i=0; i<m; i++)
    for(j=m; j<max; j++)
     if(A[j].used!=1)//看这个点是否已经交换过
    {
      count2=0;
      change.exchange(A,i,j);//先交换i点和j点，下面再检测交换这两个点后的增益
for(i1=0; i1<m; i1++)
    for(j1=m; j1<max; j1++)
     {
      if(B[ A[i1].value-1 ][ A[j1].value-1 ]==1)
      count2++;  //交换两个点i和j之后，扫描连接两个集团的边数
     }

    if(count2<count1) //与上一次的两集团之间的边数count1作比较，看这两点i和j交换是否得到最大增益。
     {
      count1=count2;
      A[i].used=1;
      A[j].used=1;
      signal=1;//有点交换，则把signal值置1
     }
     else
      change.exchange(A,i,j);//增益不是最大，则要把这两点交换恢复原来的他们所在的位置
    }
    //#####一次kernighthen-lin算法结束。######
 
    //判断signal是否为0，为0说明这一次kernighthen-lin算法循环没有点交换，增益已经达到最大，跳出算法循环。
     if(signal==0)
        break;
      else       //如果signal不为0，则要把signal置0，进入下次kernighthen-lin算法循环
      signal=0;
     
   //把A[].used项重新赋值为0，下次kernighthen-lin算法循环要重新扫描交换
    for(int tem=0; tem<max; tem++)
      A[tem].used=0;
   }

  out.println("");
  out.println("");
   out.println("交换后的集团情况是:");
    change.print(out,A,max,m);//打印集团情况
    out.close();
  }

}

这个程序其实很简单，就是利用循环反复交换两个集团的成员，直至增益最大不再改变为止

最大收获是我学会了定义一个类，相当于C语言里的结构体，然后用这个类创建一个数组对象，怎么实现的问题

关键是在要给数组初始化，我弄了很久，查了很多资料，才弄出来

初始化对象数组方法如下

其中数组创建时为： 点[] A=new 点[max];

“class 点”是我自己定义的一个类。程序中有解说

for(i=0; i<max; i++)
    {
     点 g=new 点();//给A[]数组里边的每个元素初始化
     A[i]=g;
     A[i].value=i+1;
     A[i].used=0;
    
    }
如果没有给数组初始化，在编译的时候不会提示出错，但是在测试读数据时会提示有错

还有就是读文件的问题，java里边的读取文件比较繁琐，我看书看了一天，查了一大堆资料，网上搜了一大堆资料。最后终于实现了读文件和写文件，只能用readline()方法读去，先转化为double型数据，最后转化为 int型数据

说明，数据从文本里读取，每行读取一个整数，

先读取max，网络中的点个数，

再读m，第一个网络的点个数，

接着下一行就是文字注释“下面是逐次输入有边连接的两个点，每次输入两个点，从文件中读取”，单独用in.readLine();读取，（//此处用来读取中字符“下面是逐次输入有边连接的两个点，每次输入两个点，从文件中读取”############☆★☆★☆★☆★☆★）标记了在程序代码中
 

边v(a,b)是分两行读取，每两行整数表示读取一条边，如边v(12,37)，表示点12和点37有边连接，第一行输入“12”，下一行输入“37”即可。

我测试的数据是 Zachary空手道俱乐部成员关系网络，

编程环境是“eclipse”，在包所在的文件夹新建一个“input.txt”文件，文件里输入如下数据：

34
16
下面是逐次输入有边连接的两个点，每次输入两个点，从文件中读取
3
1
4
1
5
1
6
1
7
1
8
1
9
1
11
1
12
1
13
1
14
1
18
1
20
1
22
1
32
2
3
2
4
2
8
2
14
2
18
2
20
2
22
2
31
3
4
3
8
3
 

9
3
10
3
14
3
28
3
29
3
33
4
8
4
13
4
14
5
7
5
11
6
7
6
11
6
17
7
17
9
31
9
33
9
34
14
34
15
33
15
34
16
33
16
34
16
27
16
30
19
33
19
34
20
34
21
33
21
34
23
33
23
34
24
33
24
34
24
30
24
26
24
28
25
26
25
28
25
32
26
32
27
34
28
29
29
32
29
34
30
33
30
34
31
33
31
34
32
33
33
34
 

测试结果放在“output.txt”里，结果如下：

交换前的集团情况是:
第一个集团的成员是:
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
 第二个集团的成员是:
 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

交换后的集团情况是:
第一个集团的成员是:
 1 2 3 4 5 6 7 8 18 17 11 12 13 14 22 20
 第二个集团的成员是:
 10 19 16 15 21 9 23 24 25 26 27 28 29 30 31 32 33 34

和Zachary空手道俱乐部成员关系网络中情况相符，一个俱乐部最终分裂为两个集团

评论 (0) All

登陆 还没注册？