package?GN算法;

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

//類GN_use主要配合myGN.java用，GN算法的實現(xiàn)需要GN_use中的方法，GN_use中的方法全都采用static的，為的是及時釋放內(nèi)存。
//隊列里放的元素都是點號，是從1開始的，所以映射到數(shù)組中時都要減一
public?class?GN_use?{

//	--------------------------------------------------------------	
	//方法一：
	//廣度優(yōu)先搜索法，從出發(fā)點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是廣度優(yōu)先搜索的出發(fā)點max是一個集團點的個數(shù)num是一個集團的集團號碼。注意s和下標的區(qū)別，s的下標為s-1.隊列queue里的節(jié)點號都是從1開始的，不是從0開始，注意
		//int?position=0;
		for（int?k=0;?k			queue.queArray[k]=-1;//每次都要清除隊列queue里的內(nèi)容，下次調(diào)用時要用
		}
		queue.front=0;//隊列queue里相關(guān)的項也要初始化。
		queue.rear=-1;
		queue.nItems=0;

		int?ijsignal=0;//通過signal的值來判斷節(jié)點是不是葉節(jié)點，值為0時表示是葉節(jié)點
		B[s-1].w=1;//源點的權(quán)值為1。
		queue.insert（s）;???????//源點進隊列，注意每個節(jié)點只能進一次隊列

		while（!（queue.isEmpty（）））{
			i=queue.remove（）;???//節(jié)點出隊列，

			for（j=0;?j
				if（j==s-1?||?B[j].belong!=num?||?i-1==j?）????//遇到是源點s或者不屬于這個集團的點則轉(zhuǎn)入下一次循環(huán)
					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）{?????//節(jié)點j+1沒有指定距離值時的情況
						B[j].d=B[i-1].d+1;
						B[j].w=B[i-1].w;
						signal=1;//有點被處理過，要執(zhí)行signal++，以告訴下面說明點i+1不是葉子節(jié)點。
						queue.insert（j+1）;//訪問過的節(jié)點進隊列，注意每個節(jié)點只能進一次隊列
					}
					if（B[j].d!=0?&&?B[j].d==B[i-1].d+1）{??//節(jié)點j+1指定了距離值，但還有dj=di+1成立時的情況
						B[j].w+=B[i-1].w;
						signal=1;//有點被處理過，要執(zhí)行signal++，以告訴下面說明點i+1不是葉子節(jié)點。
						//注意這里節(jié)點j+1不用再入隊列，因為前面這個節(jié)點已經(jīng)入過隊列了
					}
					if（B[j].d!=0?&&?B[j].d						continue;
				}
			}

			if（signal==0）??//signal值為0說明點i是葉節(jié)點
				B[i-1].leaves=1;
			else
				signal=0;//把signal置0，下次循環(huán)出隊列的點要用				
		}

		//下面是把所有的葉節(jié)點移動到隊列的最后。
		for（i?=?0;?i?			int?queue_num?=?queue.queArray[i]-1;//得到當前節(jié)點，下標是從1開始的，注意，故要減一
			if（B[queue_num].leaves?==?1）{
				for（j?=?i;?j?					queue.queArray[i]?=?queue.queArray[i+1];
				}
				queue.queArray[queue.nItems-1]?=?queue_num+1;//最后把這個葉子節(jié)點插入到隊列最后
			}
		}

	}
	//注意，用廣度優(yōu)先搜索算法后隊列里的最后幾個元素肯定是葉節(jié)點
//	--------------------------------------------------------------
//	方法二：
	//以某個源點s出發(fā)求對各邊的介數(shù)，緊接方法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[]）{//
		//數(shù)組A1[][]用來存放權(quán)值，
		int?rear=queue.rear;//把隊列的隊尾下標賦給rear。
		int?temp=rear;
		int?i=queue.queArray[temp];
		//尋找葉節(jié)點和非葉節(jié)點僅是判斷
		while（B[i-1].leaves==1?&&?temp>=1）
			i=queue.queArray[--temp];
		//temp就是非葉節(jié)點和葉節(jié)點的分界，其中temp+1是第一個葉節(jié)點的下標。

		int?jt1t2;//position=0position2=0;
		double?h1h2;
		//下面是處理和葉節(jié)點相鄰的節(jié)點的情況

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

????.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