GN算法Java版源码，个人鼎作

GN算法Java版源码，个人鼎作 我采用压缩矩阵三元组的形式存储数组的，极大地节省了空间，经过反复测试数据，程序达到了perfect！！ 也是我个人本科阶段毕业设计的其中一个算法！！

package GN算法;

//import java.io.IOException;
import java.util.Vector;

//类GN_use主要配合myGN.java用，GN算法的实现需要GN_use中的方法，GN_use中的方法全都采用static的，为的是及时释放内存。
//队列里放的元素都是点号，是从1开始的，所以映射到数组中时都要减一
public class GN_use {

//	--------------------------------------------------------------	
	//方法一：
	//广度优先搜索法，从出发点s找最短路径static void BFS（Queue queue Vector vec_A_copy int[] r_sign dian B[] int s int max int num）
	static void BFS（Queue queue Vector vec_A int[] r_sign dian B[] int s int max int num）{//
		//s是广度优先搜索的出发点max是一个集团点的个数num是一个集团的集团号码。注意s和下标的区别，s的下标为s-1.队列queue里的节点号都是从1开始的，不是从0开始，注意
		//int position=0;
		for（int k=0; k			queue.queArray[k]=-1;//每次都要清除队列queue里的内容，下次调用时要用
		}
		queue.front=0;//队列queue里相关的项也要初始化。
		queue.rear=-1;
		queue.nItems=0;

		int ijsignal=0;//通过signal的值来判断节点是不是叶节点，值为0时表示是叶节点
		B[s-1].w=1;//源点的权值为1。
		queue.insert（s）;       //源点进队列，注意每个节点只能进一次队列

		while（!（queue.isEmpty（）））{
			i=queue.remove（）;   //节点出队列，

			for（j=0; j
				if（j==s-1 || B[j].belong!=num || i-1==j ）    //遇到是源点s或者不属于这个集团的点则转入下一次循环
					continue;	

				//position = GN_use.position_find（i-1 j）;	
				if（GN_use.link_if（i-1 j r_sign vec_A）==true）{//A_copy[position]==1if（GN_use.link_if（i-1 j r_sign vec_A_copy）==true）
					if（B[j].d==0）{     //节点j+1没有指定距离值时的情况
						B[j].d=B[i-1].d+1;
						B[j].w=B[i-1].w;
						signal=1;//有点被处理过，要执行signal++，以告诉下面说明点i+1不是叶子节点。
						queue.insert（j+1）;//访问过的节点进队列，注意每个节点只能进一次队列
					}
					if（B[j].d!=0 && B[j].d==B[i-1].d+1）{  //节点j+1指定了距离值，但还有dj=di+1成立时的情况
						B[j].w+=B[i-1].w;
						signal=1;//有点被处理过，要执行signal++，以告诉下面说明点i+1不是叶子节点。
						//注意这里节点j+1不用再入队列，因为前面这个节点已经入过队列了
					}
					if（B[j].d!=0 && B[j].d						continue;
				}
			}

			if（signal==0）  //signal值为0说明点i是叶节点
				B[i-1].leaves=1;
			else
				signal=0;//把signal置0，下次循环出队列的点要用				
		}

		//下面是把所有的叶节点移动到队列的最后。
		for（i = 0; i < queue.nItems; i++）{
			int queue_num = queue.queArray[i]-1;//得到当前节点，下标是从1开始的，注意，故要减一
			if（B[queue_num].leaves == 1）{
				for（j = i; j < queue.nItems-1; j++）{
					queue.queArray[i] = queue.queArray[i+1];
				}
				queue.queArray[queue.nItems-1] = queue_num+1;//最后把这个叶子节点插入到队列最后
			}
		}

	}
	//注意，用广度优先搜索算法后队列里的最后几个元素肯定是叶节点
//	--------------------------------------------------------------
//	方法二：
	//以某个源点s出发求对各边的介数，紧接方法BFS（Queue queue int A_copy[][] dian B[] int s int max int num）之后
	//static void BC（Queue queueVector vec_A_copy Vector vec_A int[] r_sign dian B[]）
	static void BC（Queue queue Vector vec_A int[] r_sign dian B[]）{//
		//数组A1[][]用来存放权值，
		int rear=queue.rear;//把队列的队尾下标赋给rear。
		int temp=rear;
		int i=queue.queArray[temp];
		//寻找叶节点和非叶节点仅是判断
		while（B[i-1].leaves==1 && temp>=1）
			i=queue.queArray[--temp];
		//temp就是非叶节点和叶节点的分界，其中temp+1是第一个叶节点的下标。

		int jt1t2;//position=0position2=0;
		double h1h2;
		//下面是处理和叶节点相邻的节点的情况

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

    .CA....       232  2010-05-17 00:35  GN算法\.classpath

    .CA....       384  2010-05-17 00:35  GN算法\.project

    .CA....       448  2010-05-17 01:21  GN算法\bin\GN算法\dian.class

    .CA....      9638  2010-05-17 01:21  GN算法\bin\GN算法\GN_use.class

    .CA....      5437  2010-05-17 01:21  GN算法\bin\GN算法\myGN.class

    .CA....       404  2010-05-17 21:12  GN算法\bin\GN算法\point_belong.class

    .CA....      1127  2010-05-17 00:37  GN算法\bin\GN算法\Queue.class

    .CA....       433  2010-05-17 21:12  GN算法\bin\GN算法\s_remove_belong.class

    .CA....     11255  2010-05-17 21:12  GN算法\bin\GN算法\test_all.class

    .CA....       599  2010-05-17 21:12  GN算法\bin\GN算法\v_side.class

    .CA....       552  2010-05-16 20:33  GN算法\input.txt

    .CA....       317  2010-05-13 16:24  GN算法\input1.txt

    .CA....        46  2010-05-14 09:54  GN算法\input3.txt

    .CA....      1022  2010-05-17 21:12  GN算法\out.txt

    .CA....     17015  2010-05-17 01:21  GN算法\src\GN算法\GN_use.java

    .CA....     11818  2010-05-17 01:21  GN算法\src\GN算法\myGN.java

    .CA....      1605  2010-05-17 00:37  GN算法\src\GN算法\Queue.java

    .CA....     15114  2010-05-17 21:12  GN算法\src\GN算法\test_all.java

    .C.D...         0  2010-05-17 00:37  GN算法\bin\GN算法

    .C.D...         0  2010-05-17 00:37  GN算法\src\GN算法

    .C.D...         0  2010-05-17 00:36  GN算法\bin

    .C.D...         0  2010-05-17 00:36  GN算法\src

    .C.D...         0  2010-05-17 00:40  GN算法

----------- ---------  ---------- -----  ----

                77446                    23