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?			int?queue_num?=?queue.queArray[i]-1;//得到當前節點，下標是從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;//最后把這個葉子節點插入到隊列最后
			}
		}

	}
	//注意，用廣度優先搜索算法后隊列里的最后幾個元素肯定是葉節點
//	--------------------------------------------------------------
//	方法二：
	//以某個源點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