人群搜索演算法的實現源代碼

❶ 數據挖掘源代碼

基本Kmeans演算法實現 C++代碼

#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<math.h>
#include<stdlib.h>
#definek3//簇的數目
usingnamespacestd;
//存放元組的屬性信息
typedefvector<double>Tuple;//存儲每條數據記錄

intdataNum;//數據集中數據記錄數目
intdimNum;//每條記錄的維數

//計算兩個元組間的歐幾里距離
doublegetDistXY(constTuple&t1,constTuple&t2)
{
	doublesum=0;
	for(inti=1;i<=dimNum;++i)
	{
		sum+=(t1[i]-t2[i])*(t1[i]-t2[i]);
	}
	returnsqrt(sum);
}

//根據質心，決定當前元組屬於哪個簇
intclusterOfTuple(Tuplemeans[],constTuple&tuple){
	doubledist=getDistXY(means[0],tuple);
	doubletmp;
	intlabel=0;//標示屬於哪一個簇
	for(inti=1;i<k;i++){
		tmp=getDistXY(means[i],tuple);
		if(tmp<dist){dist=tmp;label=i;}
	}
	returnlabel;	
}
//獲得給定簇集的平方誤差
doublegetVar(vector<Tuple>clusters[],Tuplemeans[]){
	doublevar=0;
	for(inti=0;i<k;i++)
	{
		vector<Tuple>t=clusters[i];
		for(intj=0;j<t.size();j++)
		{
			var+=getDistXY(t[j],means[i]);
		}
	}
	//cout<<"sum:"<<sum<<endl;
	returnvar;

}
//獲得當前簇的均值（質心）
TuplegetMeans(constvector<Tuple>&cluster){
	
	intnum=cluster.size();
	Tuplet(dimNum+1,0);
	for(inti=0;i<num;i++)
	{
		for(intj=1;j<=dimNum;++j)
		{
			t[j]+=cluster[i][j];
		}
	}
	for(intj=1;j<=dimNum;++j)
		t[j]/=num;
	returnt;
	//cout<<"sum:"<<sum<<endl;
}

voidprint(constvector<Tuple>clusters[])
{
	for(intlable=0;lable<k;lable++)
	{
		cout<<"第"<<lable+1<<"個簇："<<endl;
		vector<Tuple>t=clusters[lable];
		for(inti=0;i<t.size();i++)
		{
			cout<<i+1<<".(";
			for(intj=0;j<=dimNum;++j)
			{
				cout<<t[i][j]<<",";
			}
			cout<<")
";
		}
	}
}

voidKMeans(vector<Tuple>&tuples){
	vector<Tuple>clusters[k];//k個簇
	Tuplemeans[k];//k個中心點
	inti=0;
	//一開始隨機選取k條記錄的值作為k個簇的質心（均值）
	srand((unsignedint)time(NULL));
	for(i=0;i<k;){
		intiToSelect=rand()%tuples.size();
		if(means[iToSelect].size()==0)
		{
			for(intj=0;j<=dimNum;++j)
			{
				means[i].push_back(tuples[iToSelect][j]);
			}
			++i;
		}
	}
	intlable=0;
	//根據默認的質心給簇賦值
	for(i=0;i!=tuples.size();++i){
		lable=clusterOfTuple(means,tuples[i]);
		clusters[lable].push_back(tuples[i]);
	}
	doubleoldVar=-1;
	doublenewVar=getVar(clusters,means);
	cout<<"初始的的整體誤差平方和為："<<newVar<<endl;
	intt=0;
	while(abs(newVar-oldVar)>=1)//當新舊函數值相差不到1即准則函數值不發生明顯變化時，演算法終止
	{
		cout<<"第"<<++t<<"次迭代開始："<<endl;
		for(i=0;i<k;i++)//更新每個簇的中心點
		{
			means[i]=getMeans(clusters[i]);
		}
		oldVar=newVar;
		newVar=getVar(clusters,means);//計算新的准則函數值
		for(i=0;i<k;i++)//清空每個簇
		{
			clusters[i].clear();
		}
		//根據新的質心獲得新的簇
		for(i=0;i!=tuples.size();++i){
			lable=clusterOfTuple(means,tuples[i]);
			clusters[lable].push_back(tuples[i]);
		}
		cout<<"此次迭代之後的整體誤差平方和為："<<newVar<<endl;
	}

	cout<<"Theresultis:
";
	print(clusters);
}
intmain(){

	charfname[256];
	cout<<"請輸入存放數據的文件名：";
	cin>>fname;
	cout<<endl<<"請依次輸入:維數樣本數目"<<endl;
	cout<<endl<<"維數dimNum:";
	cin>>dimNum;
	cout<<endl<<"樣本數目dataNum:";
	cin>>dataNum;
	ifstreaminfile(fname);
	if(!infile){
		cout<<"不能打開輸入的文件"<<fname<<endl;
		return0;
	}
	vector<Tuple>tuples;
	//從文件流中讀入數據
	for(inti=0;i<dataNum&&!infile.eof();++i)
	{
		stringstr;
		getline(infile,str);
		istringstreamistr(str);
		Tupletuple(dimNum+1,0);//第一個位置存放記錄編號，第2到dimNum+1個位置存放實際元素
		tuple[0]=i+1;
		for(intj=1;j<=dimNum;++j)
		{
			istr>>tuple[j];
		}
		tuples.push_back(tuple);
	}

	cout<<endl<<"開始聚類"<<endl;
	KMeans(tuples);
	return0;
}

❷ 《數據結構》演算法實現與分析高一凡中的源代碼要怎麼用

這個代碼可以直接用。用的時候必須把include中的文件也保存好。

❸ 禁忌搜索演算法源代碼

禁忌搜索法：使用一個禁忌表，記錄下不允許搜索的元素。在後面的搜索中，根據禁忌表來決定如何處理當前元素。用在約瑟夫環中，我們可以用一個數組記錄下已經出圈的人的編號，這樣再數數時，可以根據禁忌表來判斷此人是否還在圈內。

#define N 100
void yuesefu1(int data[],int result[],int sum,int k)
{
int i=0,j=0,count=0;
int n;
while(count<sum)
{
for(n=0;n<count;n++)/*根據禁忌表判斷此人是否還在圈內*/
if(result[n]==data[i])
break;
if(n>=count)/*若此人還在圈內*/
j++;
if(j==k)
{
result[count++]=data[i];/*把出圈的人的編號存入禁忌表*/
j=0;
}
i++;
if(i==sum)
i=0;
}
}

void main()
{
int data[N];
int result[N]={0};
int i,j,total,k;
printf("\nPlease input the number of every people.\n");
for(i=0;i<N;)
{
int input;
scanf("%d",&input);
if(input==0)
break;
for(j=0;j<i;j++)
if(data[j]==input)
break;
if(j>=i&&input>0)
{
data[i]=input;
i++;
}
else
printf("\nData error.Re-input:");
}
total=i;
printf("\nYou have input:\n");
for(i=0;i<total;i++)
{
if(i%10==0)
printf("\n");
printf("%4d",data[i]);
}
printf("\nPlease input a number to count:");
scanf("%d",&k);
yuesefu1(data,result,total,k);
printf("\nThe sequence is:\n");
for(i=0;i<total;i++)
printf("%d ",result[i]);

❹ 求查找演算法（折半查找法，順序查找法，分別在一個程序里）「動畫演示」程序源代碼，一共兩個源代碼

折半搜索（英語：half-interval search），也稱二分搜索（英語：binary search）、對數搜索（英語：logarithmic search），是一種在有序數組中查找某一特定元素的搜索演算法。

搜索過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜索過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。如果在某一步驟數組為空，則代表找不到。這種搜索演算法每一次比較都使搜索范圍縮小一半。

折半查找法是效率較高的一種查找方法。假設有已經按照從小到大的順序排列好的五個整數a0~a4，要查找的數是X，其基本思想是： 設查找數據的范圍下限為l=0，上限為h=4，求中點m=（l+h）/2，用X與中點元素am比較，若X等於am，即找到，停止查找；否則，若X大於am，替換下限l=m+1，到下半段繼續查找；若X小於am，換上限h=m-1，到上半段繼續查找；如此重復前面的過程直到找到或者l>h為止。如果l>h，說明沒有此數，列印找不到信息，程序結束。

函數實現如下：

bin_search(intA[],intn,intkey){
intlow,high,mid;
low=0;
high=n-1;
while(low<=high)
{
mid=(low+high)/2;
if(A[mid]==key)returnmid;
if(A[mid]<key){
low=mid+1;
}
if(A[mid]>key){
high=mid-1;
}
}
return-1;
}
C語言實現代碼
#include<stdio.h>intmain()
{
inta[11]={0,1,2,3,4,5,6,7,8,9,10},min=0,max=10,mid,n;//max為數列長度，a[0]作為第一個數組元素
printf("請輸入您要查找的數:
");
scanf("%d",&n);
while(min+1!=max)
{
mid=(min+max)/2;
if(n>a[mid])min=mid;
elseif(n<a[mid])max=mid;
else
{
printf("輸入的數在數列的第%d位
",mid);
exit(0);
}
}
if(n==a[max])
{
max+=1;
printf("
輸入的數在數列的第%d位
",max);
}
elseif(n==a[min])
{
min+=1;
printf("
輸入的數在數列的第%d位
",min);
}
elseif(n!=a[mid])
printf("
輸入的數不在數列中");
}
Dev-c++實現
#include<stdio.h>
#include<stdlib.h>
voidmain()
{
inta[15]={1,2,3,4,5,6,7,8,9,10,11,12,13,15};
intn,m,top,bot,mid;
top=m=1;//此處修改top=0;m=1;
bot=14;
printf("pleaseinputanumber:");
scanf("%d",&n);
while(top<=bot)
{
mid=(top+bot)/2;
if(n==a[mid])
{
printf("這是第%d個元素的值。
",mid+1);
m=0;
break;
}
elseif(n>a[mid])
top=mid+1;
elseif(n<a[mid])
bot=mid-1;
}
if(m)
printf("無此數。
");
system("PAUSE");
return0;
}

順序查找是按照序列原有順序對數組進行遍歷比較查詢的基本查找演算法。

對於任意一個序列以及一個給定的元素，將給定元素與序列中元素依次比較，直到找出與給定關鍵字相同的元素，或者將序列中的元素與其都比較完為止。

函數實現如下：

intsq_search(keytypekeyp[],intn,keytypekey)
{
inti;
for(i=0;i<n;i++)
if(key[i]==key)
returni;//查找成功
return-1;//查找失敗
}

上面只是演算法實現函數，對於動畫部分，自己用moveto，lineto描點劃線的方式實現吧。

❺ A*搜尋演算法的代碼實現(C語言實現)

用C語言實現A*最短路徑搜索演算法，作者 Tittup frog(跳跳蛙)。 #include<stdio.h>#include<math.h>#defineMaxLength100 //用於優先隊列（Open表）的數組#defineHeight15 //地圖高度#defineWidth20 //地圖寬度#defineReachable0 //可以到達的結點#defineBar1 //障礙物#definePass2 //需要走的步數#defineSource3 //起點#defineDestination4 //終點#defineSequential0 //順序遍歷#defineNoSolution2 //無解決方案#defineInfinity0xfffffff#defineEast(1<<0)#defineSouth_East(1<<1)#defineSouth(1<<2)#defineSouth_West(1<<3)#defineWest(1<<4)#defineNorth_West(1<<5)#defineNorth(1<<6)#defineNorth_East(1<<7)typedefstruct{ signedcharx,y;}Point;constPointdir[8]={ {0,1},//East {1,1},//South_East {1,0},//South {1,-1},//South_West {0,-1},//West {-1,-1},//North_West {-1,0},//North {-1,1}//North_East};unsignedcharwithin(intx,inty){ return(x>=0&&y>=0 &&x<Height&&y<Width);}typedefstruct{ intx,y; unsignedcharreachable,sur,value;}MapNode;typedefstructClose{ MapNode*cur; charvis; structClose*from; floatF,G; intH;}Close;typedefstruct//優先隊列（Open表）{ intlength; //當前隊列的長度 Close*Array[MaxLength]; //評價結點的指針}Open;staticMapNodegraph[Height][Width];staticintsrcX,srcY,dstX,dstY; //起始點、終點staticCloseclose[Height][Width];//優先隊列基本操作voidinitOpen(Open*q) //優先隊列初始化{ q->length=0; //隊內元素數初始為0}voidpush(Open*q,Closecls[Height][Width],intx,inty,floatg){ //向優先隊列（Open表）中添加元素 Close*t; inti,mintag; cls[x][y].G=g; //所添加節點的坐標 cls[x][y].F=cls[x][y].G+cls[x][y].H; q->Array[q->length++]=&(cls[x][y]); mintag=q->length-1; for(i=0;i<q->length-1;i++) { if(q->Array[i]->F<q->Array[mintag]->F) { mintag=i; } } t=q->Array[q->length-1]; q->Array[q->length-1]=q->Array[mintag]; q->Array[mintag]=t; //將評價函數值最小節點置於隊頭}Close*shift(Open*q){ returnq->Array[--q->length];}//地圖初始化操作voidinitClose(Closecls[Height][Width],intsx,intsy,intdx,intdy){ //地圖Close表初始化配置 inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { cls[i][j].cur=&graph[i][j]; //Close表所指節點 cls[i][j].vis=!graph[i][j].reachable; //是否被訪問 cls[i][j].from=NULL; //所來節點 cls[i][j].G=cls[i][j].F=0; cls[i][j].H=abs(dx-i)+abs(dy-j); //評價函數值 } } cls[sx][sy].F=cls[sx][sy].H; //起始點評價初始值 // cls[sy][sy].G=0; //移步花費代價值 cls[dx][dy].G=Infinity;}voidinitGraph(constintmap[Height][Width],intsx,intsy,intdx,intdy){ //地圖發生變化時重新構造地 inti,j; srcX=sx; //起點X坐標 srcY=sy; //起點Y坐標 dstX=dx; //終點X坐標 dstY=dy; //終點Y坐標 for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { graph[i][j].x=i;//地圖坐標X graph[i][j].y=j;//地圖坐標Y graph[i][j].value=map[i][j]; graph[i][j].reachable=(graph[i][j].value==Reachable); //節點可到達性 graph[i][j].sur=0;//鄰接節點個數 if(!graph[i][j].reachable) { continue; } if(j>0) { if(graph[i][j-1].reachable) //left節點可以到達 { graph[i][j].sur|=West; graph[i][j-1].sur|=East; } if(i>0) { if(graph[i-1][j-1].reachable &&graph[i-1][j].reachable &&graph[i][j-1].reachable) //up-left節點可以到達 { graph[i][j].sur|=North_West; graph[i-1][j-1].sur|=South_East; } } } if(i>0) { if(graph[i-1][j].reachable) //up節點可以到達 { graph[i][j].sur|=North; graph[i-1][j].sur|=South; } if(j<Width-1) { if(graph[i-1][j+1].reachable &&graph[i-1][j].reachable &&map[i][j+1]==Reachable)//up-right節點可以到達 { graph[i][j].sur|=North_East; graph[i-1][j+1].sur|=South_West; } } } } }}intbfs(){ inttimes=0; inti,curX,curY,surX,surY; unsignedcharf=0,r=1; Close*p; Close*q[MaxLength]={&close[srcX][srcY]}; initClose(close,srcX,srcY,dstX,dstY); close[srcX][srcY].vis=1; while(r!=f) { p=q[f]; f=(f+1)%MaxLength; curX=p->cur->x; curY=p->cur->y; for(i=0;i<8;i++) { if(!(p->cur->sur&(1<<i))) { continue; } surX=curX+dir[i].x; surY=curY+dir[i].y; if(!close[surX][surY].vis) { close[surX][surY].from=p; close[surX][surY].vis=1; close[surX][surY].G=p->G+1; q[r]=&close[surX][surY]; r=(r+1)%MaxLength; } } times++; } returntimes;}intastar(){ //A*演算法遍歷 //inttimes=0; inti,curX,curY,surX,surY; floatsurG; Openq;//Open表 Close*p; initOpen(&q); initClose(close,srcX,srcY,dstX,dstY); close[srcX][srcY].vis=1; push(&q,close,srcX,srcY,0); while(q.length) { //times++; p=shift(&q); curX=p->cur->x; curY=p->cur->y; if(!p->H) { returnSequential; } for(i=0;i<8;i++) { if(!(p->cur->sur&(1<<i))) { continue; } surX=curX+dir[i].x; surY=curY+dir[i].y; if(!close[surX][surY].vis) { close[surX][surY].vis=1; close[surX][surY].from=p; surG=p->G+sqrt((curX-surX)*(curX-surX)+(curY-surY)*(curY-surY)); push(&q,close,surX,surY,surG); } } } //printf("times:%d ",times); returnNoSolution;//無結果}constintmap[Height][Width]={ {0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1}, {0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1}, {0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1}, {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0}, {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1}, {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}};constcharSymbol[5][3]={"□","▓","▽","☆","◎"};voidprintMap(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%s",Symbol[graph[i][j].value]); } puts(""); } puts("");}Close*getShortest(){ //獲取最短路徑 intresult=astar(); Close*p,*t,*q=NULL; switch(result) { caseSequential: //順序最近 p=&(close[dstX][dstY]); while(p) //轉置路徑 { t=p->from; p->from=q; q=p; p=t; } close[srcX][srcY].from=q->from; return&(close[srcX][srcY]); caseNoSolution: returnNULL; } returnNULL;}staticClose*start;staticintshortestep;intprintShortest(){ Close*p; intstep=0; p=getShortest(); start=p; if(!p) { return0; } else { while(p->from) { graph[p->cur->x][p->cur->y].value=Pass; printf("（%d，%d）→ ",p->cur->x,p->cur->y); p=p->from; step++; } printf("（%d，%d） ",p->cur->x,p->cur->y); graph[srcX][srcY].value=Source; graph[dstX][dstY].value=Destination; returnstep; }}voidclearMap(){ //ClearMapMarksofSteps Close*p=start; while(p) { graph[p->cur->x][p->cur->y].value=Reachable; p=p->from; } graph[srcX][srcY].value=map[srcX][srcY]; graph[dstX][dstY].value=map[dstX][dstY];}voidprintDepth(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { if(map[i][j]) { printf("%s",Symbol[graph[i][j].value]); } else { printf("%2.0lf",close[i][j].G); } } puts(""); } puts("");}voidprintSur(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%02x",graph[i][j].sur); } puts(""); } puts("");}voidprintH(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%02d",close[i][j].H); } puts(""); } puts("");}intmain(intargc,constchar**argv){ initGraph(map,0,0,0,0); printMap(); while(scanf("%d%d%d%d",&srcX,&srcY,&dstX,&dstY)!=EOF) { if(within(srcX,srcY)&&within(dstX,dstY)) { if(shortestep=printShortest()) { printf("從（%d，%d）到（%d，%d）的最短步數是:%d ", srcX,srcY,dstX,dstY,shortestep); printMap(); clearMap(); bfs(); //printDepth(); puts((shortestep==close[dstX][dstY].G)?"正確":"錯誤"); clearMap(); } else { printf("從（%d，%d）不可到達（%d，%d） ", srcX,srcY,dstX,dstY); } } else { puts("輸入錯誤！"); } } return(0);}

❻ 尋找最短路徑的匯編語言實現源代碼是什麼(用Dijkstra 演算法)

Dijkstra演算法Dijkstra演算法是典型的最短路徑演算法，用於計算一個節點的最短路徑中的所有其他節點。其主要特點是出發點為中心向外層層擴展，直到擴展到結束日期。 Dijkstra最短路徑演算法能得出最佳的解決方案，但許多節點，它遍歷計算，這樣的效率是低的。最短路徑演算法的
Dijkstra演算法是非常有代表性的許多專業課程的基本內容進行了詳細的介紹，如數據結構，圖論，運籌學，等等。
Dijkstra演算法的一般性發言一般有兩種方式，永久和臨時的標簽，開啟，關閉表的方式之一，德魯表示，為了引進和下面的A *演算法和D *演算法一致，這里是開放的，關閉表。
貪婪的方法，演算法策略
大概過程如下：
創建兩個表，打開，關閉。
OPEN表保存沒有調查之前已產生的所有節點，CLOSED表中記錄已訪問過的節點。
1。的道路網路的出發點和等待在公開組的檢查沒有檢查點，此點。
2。打開表，以找出從起點最近的點，以確定所有的子節點，這一點，這點上關閉表。
3。遍歷訪問這個點的子節點。獲得這些子節點從子節點到OPEN表的放電的開始點的距離的值。
4。重復步驟2和步驟3，直到OPEN表為空，或找到目標點。
[編輯本段]演算法是
包括的文件
定義MAXNUM 765432100的
使用命名空間std;
ifstream的散熱片（Dijkstra演算法。在「）;
ofstream這樣的FOUT（」Dijkstra.out「）;
詮釋地圖[501] [501];
布爾is_arrived [501];
詮釋區[501] [501]，堆棧[501];
整數P，Q，K，路徑，源代碼，頂點，溫度，SetCard
詮釋FindMin（）
{
詮釋P，溫度= 0，MINM = MAXNUM;
（P = 1，P <=頂點，P + +）
（（區[P] MINM）&&（！is_arrived [P] ））
{
MINM區[P]。
溫度= P;
}
收益溫度;
}
：（ ）
{
的memset（is_arrived，0，大小（is_arrived））;
鰭>>源代碼>>頂點;
（P = 1，P <=頂點，P + +）
（Q = 1，Q =頂點，Q + +）
{
鰭>>地圖[P] [Q];
（圖[ P] [Q] == 0）地圖[P] [Q] = MAXNUM;
}
為（P = 1，P <=頂點，P + +）
{ />區[P] =地圖[來源] [P];
（區[P]！= MAXNUM）
[P] =源;
其他
[P] = P;
}
is_arrived [來源] = TRUE;
SetCard = 1;

{
溫度= FindMin（）;
（Temp! = 0）
{
SetCard SetCard +1;
is_arrived [溫度] = TRUE;
（P = 1，P <=頂點，P + +）
（（區[P]>區[溫度] +地圖[溫度] [P]）&&（！is_arrived [P]））
{
區[P] =區[溫度] +地圖[溫度] [P]
[P] =溫度;
}
}
其他
突破; BR />}
（SetCard! =頂點）;
（P = 1，P <=頂點，P + +）
（p! =源）
{
FOUT <<「======================== \ n」;
FOUT <<「來源：」<; <資料來源<<「\ n目標：」「P <<'\ n';
（區[P] == MAXNUM）
{
FOUT <<」距離：「< 「無限\ n」;
FOUT <<「路徑：沒辦法！」;
}
其他
{
FOUT「距離」：「<<區[P] <<'\ n';
K = 1;
路徑= P;
同時（從[路徑]！=路徑）
{
棧[K] =路徑;
路徑=從[路徑];
K = K +1;
}
FOUT <<「路徑：」<（Q = K-1，Q = 1，Q - ）
FOUT「 - >」<<棧[問];
}
FOUT <<「\ ?======================== \ n \ n「;}

fin.close（）;
fout.close（）;
返回0;
}
樣品輸入
2
7
00 20 50 30 00 00 00
20 00 25 00 00 70 00
50 25 00 40 25 50 00
30 00 40 0??0 55 00 00
00 00 25 55 00 10 00
00 70 50 00 10 00 00
00 00 00 00 00 00 00
樣本輸出
========================
來源：2
目標：1
距離：20
路徑：2 - > 1
==================== ====
========================
來源：
目標：3
距離：25
路徑：2 - > 3 ========================

===== ===================
來源：
目標：4
距離：50
路徑：2 - > 1 - > ======================== 4

============== =========
來源：
目標：5
距離：50
路徑：2 - > 3 - > 5
== ======================
========================
來源：
目標：6
距離：60
路徑：2 - > 3 - > 5 - > 6
========= ===============
========================
來源：2
目標：7
距離：無限
路徑：沒辦法！
========================
示常式序和相關子程序如下：
無效的Dijkstra（INT N，INT [ ]距離的int [] iPath標）
{
詮釋最短距離，U
INT I，J;
/ /從n個頂點的鄰接矩陣的副本可以擺脫行了，是復制前n行的距離[]
（i = 0;我VerNum，我+ +）
{
距離=圓弧[N];
訪問= 0;
} / / n個結點訪問，因為n個頂點的出發點是
訪問[N] = 1;
/ /找到的頂點其他頂點的路線，並且它不是頂點n的開頭，沒有先前旅遊。
/ /相當於u點，這一點是沒有的出發點N（i = 0; I <VerNum，我+ +）
{
U = 0

最短距離=否;
為（J = 0; <VerNum; + +）
（訪問[J] == 0 &&（距離[J]最短距離））
{
最短距離=距離[J];
ü= J;
}
/ /例如P1871圖G6距離=無，無，無，30,100]第一次看的是V2，U = 2
/ /找到結束，的MinDis意味著它無法連接，然後返回。這種情況是相似的V5。

（最短距離==否）返回;
/ /建立一個u個頂點將被用於頂點u，相當於弧[V，U +弧U，W] 。
訪問[U] = 1;
/ /找到一個U頂點到所有其他頂點最小的路徑實際上是在尋找弧] [U，J，J值在[0， VerNum]。
/ /如果是圓弧，U [I] +凱旋門[U，J] ARC [I，J]，ARC [I，J] =弧[I，U] +凱旋門[U J] <弧[I，J]
/ /的做法，因為距離[]是期望的結果，起始點確定的情況下，那就是：

/ /如果（距離[U] +圓弧[U，J）<=距離[J]：
/ /距離[J]距離[U] + [U，J弧];
/ /保存iPath標[] u點數量;
/ /同樣，設置訪問量：新發現的路由[J] = 0，經過尋找另一條道路，這條道路可能不利用。 V3
（J = 0; <VerNum; + +）
（訪問[J] == 0 &&弧U，J] <&& U！= J） /> {
（（距離[U] +圓弧[U，J）<=距離[J]）
{
距離[J]距離[U] +弧[ U，J];
訪問[J] = 0;
iPath標[J] = U;
}
}
}
} / /輔助功能
無效的Prim（），
{
INT I，M，N = 0;
為（i = 0;我VerNum;我+ +）
{
訪問= 0;
T =新的TreeNode（）;
T.Text = V;
}
訪問[N] + +;
listBox1.Items。添加（V [N]）;
（參觀（）> 0）
{
（（M = MinAdjNode（N））！= -1）
{ BR /> T [N]。 Nodes.Add（T [M]）;
N = M;
訪問[N] + +;
}
其他
{
?= MinNode（0）;
（N> 0）T [旻]。 Nodes.Add（T [敏]）;
訪問[N] + +;
}
listBox1.Items.Add（V [N]）;
} treeView1.Nodes.Add（T [0]）;
}
的無效TopoSort（）
{
INT I，N;
listBox1.Items.Clear（ ）;
棧S =新的堆棧（）;
為（i = 0;我VerNum，我+ +）
訪問= 0;
為（= VerNum- 1> = 0; I - ）
（入度（I）== 0）
{
S.Push（I）;
訪問+ +; ...... />}
而（S.Count！= 0）
{
N =（INT）S.Pop（）;
listBox1.Items.Add（V [N] ）;
CLEARLINK（N）;
為（i = VerNum-1> = 0; I - ）
（分== 0 &&入度（I）== 0）
{
S.Push（I）;
訪問+ +;
}
}
}
無效AOETrave（INT N，樹節點TR，W）
{
INT I，W0;
（出度（N）== 0）返回;
（i = 0; <VerNum; + +）
（（W0 =圓弧[N，I]）！= 0）
{
listBox1.Items.Add（V +「\ t」+（W + W0）的ToString（）+「\ t」+ i.ToString（）+「\ t」+ n.ToString（））;
TreeNode的T1 =新的TreeNode（）;
T1.Text = V + 「W =」+（W + W0）。的ToString（）+「]」;
TR.Nodes.Add（T1）;
AOETrave（I，T1，W + W0）;
}
}
無效AOE（）
{
INT I，W = 0，M = 1;
TreeNode的T1 =新的TreeNode（）;
為（i = 0; <VerNum;我+ +）
{
訪問= 0;
}
T1.Text = V [0];
listBox1.Items.Add（「父母符號顯示生成樹：「）;
listBox1.Items.Add（」V \ TW \工業貿易署\ TPID「）;
為（i = 0;我VerNum，我+ +）
{
（（W =弧[0，I]）！= 0）
{
listBox1.Items.Add（V +「\ t」+ w.ToString（）+「\ T「+ i.ToString（）+」\ T0「）;
TreeNode的T2 =新的TreeNode（）;
T2.Text = V +」W =「+ w.ToString（）+」 「;
AOETrave（I，T2，W）;
listBox1.Items.Add（」\ t \ t樹「+ m.ToString
T1.Nodes.Add（ T2），（））;
米+ +;
}
}
treeView1.Nodes.Clear（）;
treeView1.Nodes.Add（T1）;
}
IsZero（）
{
我;
為（i = 0;我VerNum，我+ +）
（LineIsZero （一）> = 0）返回;
返回-1;
}
詮釋LineIsZero（N）
{
我
（i = 0; <VerNum;我+ +）
（電弧[N，I] = 0）返回;
返回-1;}

：無效DepthTraverse（）
{
INT I，M;
（i = 0; <VerNum，我+ +）
{
訪問= 0; BR /> T =新的TreeNode（）;
T.Text = V
R = 0;
}
而（（M = IsZero（））> = 0）
{
（訪問[M] == 0）
{
listBox1.Items.Add（V [M]）;
R [M] = 1 ;}

訪問[M] + +;
DTrave（M）;
}
為（i = 0; {
（R == 1）
treeView1.Nodes.Add（T）;
}
}
無效DTrave（N） /> {
我;
（LineIsZero（N）<0）返回;
為（i = VerNum-1> = 0; I - ）
（弧[N] = 0）
{
弧[N，I] = 0;
弧[I，N] = 0;
（訪問= = 0）
{
listBox1.Items.Add（V）;
T [N]。 Nodes.Add（T）;
R = 0;
}
訪問+ +;
DTrave（I）;
}
} ：無效BreadthTraverse（）
{
INT I，M;
（i = 0; <VerNum，我+ +）
{
訪問= 0;
T =新的TreeNode（）;
T.Text = V;
R = 0;
}
而（（M = IsZero（））> = 0 ）
{
（訪問[M] == 0）
{
listBox1.Items。添加（V [M]）;
R [M] = 1;
}
訪問[M] + +;
BTrave（M）;
} BR />（i = 0;我VerNum，我+ +）
{
（R == 1）
treeView1.Nodes.Add（T）;
}
}
無效BTrave（N）
{
我
隊列Q =新的Queue（）;
Q.Enqueue（N）
而（Q.Count！= 0）
{
為（i = 0;我VerNum，我+ +）
{
（電弧N，I] = 0）
{
弧[N，I] = 0;
弧[N] = 0;
（訪問== 0）
{
listBox1.Items.Add（V）;
T [N]。 Nodes.Add（T）;
直徑= 0;
}
訪問+ +;
Q.Enqueue（I）;
}
} BR /> N =（int）的Q.Dequeue（）;
}
}
詮釋MinNode（VN）
{
INT I，J，N，米，最小=否;
N = -1，M = -1;
為（i = VN我VerNum，我+ +）
中for（j = 0; J < VerNum; + +）
（電弧[I，J] = &&弧[I，J]閔&&分== 0 &&訪問[J] == 1）
{ BR />最小值=弧[I，J]; N = I，M = J;
}
敏=旻= M
返回n;
} BR />詮釋MinAdjNode（N）
{
我，敏，米;
最小值=否，M = -1;
（i = 0; I < VerNum，我+ +）
（電弧[N，I] =沒有訪問&& == 0 &&最小弧[N，I] &&訪問[N] == 1）{BR /> BR />最小值=弧[N，I]，M = I;}

返回米;
}
INT訪問（）
{
INT I，S = 0;
為（i = 0; <VerNum，我+ +）
（訪問== 0）+ +;
返回s;
>}

[編輯本段] Dijkstra演算法的Pascal實現：
程序Dijkstra的;
VAR
答：ARRAY [1 .. 100,1 .. 100的整數;
標志：數組[1] .. 100]布爾值;
W，X，N，I，J，分，明尼蘇達州：整數;
開始
readln（N）;
我：= 1到n
開始
對於j = 1到n
讀（A）;
readln;
結束;
fillchar（標志中，sizeof（標志），假）;
標志[1]：= TRUE;
明尼蘇達州：= 1;
為：= 2到n
開始
分： 32767;
W：=明尼蘇達州
我：= 1到n做
（W >）和（[W，I] <MIN），然後
開始
分：= [];
明尼蘇達州：= I;
結束;
標志[明尼蘇達州]：= TRUE;
J： 1到n做
（J >明尼蘇達州）和（A [1，明尼蘇達州] + A [明尼蘇達州，J]，A [1，J）和（標志[J] = FALSE），那麼 BR /> A [1，J] = [1，明尼蘇達州] + A [明尼蘇達州，J];
結束;
我：= 1到n做
寫（ [1]）;
年底。

❼ 詳細介紹廣度優先搜索的實現，原理，c++程序

寬度優先搜索演算法（又稱廣度優先搜索）是最簡便的圖的搜索演算法之一，這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS，屬於一種盲目搜尋法，目的是系統地展開並檢查圖中的所有節點，以找尋結果。換句話說，它並不考慮結果的可能位址，徹底地搜索整張圖，直到找到結果為止。

已知圖G=(V,E)和一個源頂點s，寬度優先搜索以一種系統的方式探尋G的邊，從而「發現」s所能到達的所有頂點，並計算s到所有這些頂點的距離(最少邊數)，該演算法同時能生成一棵根為s且包括所有可達頂點的寬度優先樹。對從s可達的任意頂點v，寬度優先樹中從s到v的路徑對應於圖G中從s到v的最短路徑，即包含最小邊數的路徑。該演算法對有向圖和無向圖同樣適用。
之所以稱之為寬度優先演算法，是因為演算法自始至終一直通過已找到和未找到頂點之間的邊界向外擴展，就是說，演算法首先搜索和s距離為k的所有頂點，然後再去搜索和S距離為k+l的其他頂點。
為了保持搜索的軌跡，寬度優先搜索為每個頂點著色：白色、灰色或黑色。演算法開始前所有頂點都是白色，隨著搜索的進行，各頂點會逐漸變成灰色，然後成為黑色。在搜索中第一次碰到一頂點時，我們說該頂點被發現，此時該頂點變為非白色頂點。因此，灰色和黑色頂點都已被發現，但是，寬度優先搜索演算法對它們加以區分以保證搜索以寬度優先的方式執行。若(u,v)∈E且頂點u為黑色，那麼頂點v要麼是灰色，要麼是黑色，就是說，所有和黑色頂點鄰接的頂點都已被發現。灰色頂點可以與一些白色頂點相鄰接，它們代表著已找到和未找到頂點之間的邊界。
在寬度優先搜索過程中建立了一棵寬度優先樹，起始時只包含根節點，即源頂點s.在掃描已發現頂點u的鄰接表的過程中每發現一個白色頂點v，該頂點v及邊(u,v)就被添加到樹中。在寬度優先樹中，我們稱結點u 是結點v的先輩或父母結點。因為一個結點至多隻能被發現一次，因此它最多隻能有--個父母結點。相對根結點來說祖先和後裔關系的定義和通常一樣：如果u處於樹中從根s到結點v的路徑中，那麼u稱為v的祖先，v是u的後裔。