package?GN算法;

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

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

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

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

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

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

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

		//下面是把所有的葉節(jié)點(diǎn)移動到隊(duì)列的最后。
		for（i?=?0;?i?			int?queue_num?=?queue.queArray[i]-1;//得到當(dāng)前節(jié)點(diǎn)，下標(biāo)是從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é)點(diǎn)插入到隊(duì)列最后
			}
		}

	}
	//注意，用廣度優(yōu)先搜索算法后隊(duì)列里的最后幾個元素肯定是葉節(jié)點(diǎn)
//	--------------------------------------------------------------
//	方法二：
	//以某個源點(diǎn)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;//把隊(duì)列的隊(duì)尾下標(biāo)賦給rear。
		int?temp=rear;
		int?i=queue.queArray[temp];
		//尋找葉節(jié)點(diǎn)和非葉節(jié)點(diǎn)僅是判斷
		while（B[i-1].leaves==1?&&?temp>=1）
			i=queue.queArray[--temp];
		//temp就是非葉節(jié)點(diǎn)和葉節(jié)點(diǎn)的分界，其中temp+1是第一個葉節(jié)點(diǎn)的下標(biāo)。

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

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

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