【文章內(nèi)容簡(jiǎn)介】 b]=qq[b]p。 qq[a]poo=b。 qq[b]poo=a。 qq[a]num=qq[b]num=c。 } s=clock()。 for(i=0。in。i++) { qq[i]p=NULL。 dis[i]=1。 } yes[0]=1。 wor[0]=0。 dis[0]=0。 while(beg!=end) { x=q[wor[beg]].p。 while(x!=NULL) { if(dis[xpoo]==1||(dis[xpoo]xnum+dis[wor[beg]]amp。amp。dis[xpoo]!=1)) { dis[xpoo]=dis[wor[beg]]+xnum。 wor[end]=xpoo。 if(yes[xpoo]==0) { yes[xpoo]=1。 end++。 } } x=xp。 } yes[wor[beg]]=0。 beg++。 } printf(%d,dis[n1])。 t=clock()。 隨機(jī)數(shù)生成模塊： fprintf(fp,%d %d\n,n,10*n)。 for(i=0。i10*n。i++) { j=rand()%n+1。 k=rand()%n+1。 while(j==k){ j=rand()%n+1。 k=rand()%n+1。} fprintf(fp,%d %d %d\n,j,k,rand())。 } 運(yùn)行時(shí)間（不含文件操作）：當(dāng) n=100000時(shí)，運(yùn)行時(shí)間 1937ms；當(dāng) n=10000時(shí)，運(yùn)行時(shí)間 141ms；當(dāng) n=1000時(shí)，運(yùn)行時(shí)間小于 10ms。特別需要注意的是，當(dāng) n=50000時(shí)，用時(shí)828ms，再加上文件操作用時(shí)，可稱為是 SPFA算法數(shù)據(jù)規(guī)模的上限。這組數(shù)據(jù)是 n 個(gè)點(diǎn)，10*n條隨機(jī)邊的情況下作出的。若使用 O(n^2)的 Dijkstra算法，時(shí)間將大幅增加。 對(duì)于單源最短路徑，要考慮題意要求，稀疏圖使用 SPFA，密集圖使用 Dijkstra，以提高運(yùn)行效率。 —— Floyed算法 void floyed() { int i,j,k,min=0。 for(k=0。kn。k++) for(i=0。in。i++) for(j=0。jn。j++) if(d[i][k]+d[k][j]d[i][j]) d[i][j]=d[i][k]+d[k][j]。 } 當(dāng) MAX=500 時(shí)，運(yùn)行時(shí)間： 。這提示我們，點(diǎn)對(duì)點(diǎn)最短路徑的規(guī)模最大為500，否則會(huì)超時(shí)。 若使用 MAX1次 dijkstra算法 void dijkstra() { int i,j,k,min=0。 for(k=0。kn1。k++) { int use[MAX]={0}。 for(i=0。in。i++) dis[i]=d[k][i]。 for(i=1。in。i++) { min=n。 for(j=0。jn。j++) if(!use[j]amp。amp。d[i][j]d[i][min]) min=j。 use[min]=1。 for(j=0。jn。j++) if(dis[min]+d[min][j]dis[j]) dis[j]=dis[min]+d[min][j]。 } } } 當(dāng) MAX=500時(shí)，運(yùn)行時(shí)間： 1625ms，與 floyed的 980ms相比，顯然慢了很多。因此，floyed算法是點(diǎn)對(duì)點(diǎn)最短路徑的“正統(tǒng)”算法。 三、字符串匹配算法的比較 for(i=0。i1000。i++) S[i]=1。 for(j=0。j100000。j++) T[j]=1。 s=clock()。 tot=0。 ls=strlen(S)。 lt=strlen(T)。 for(i=0。iltls。i++) { for(j=0。jls。j++) if(T[i+j]!=S[j]) break。 if(j==ls) tot++。 } printf(%d ,tot)。 t=clock()。 運(yùn)行時(shí)間： 。這組測(cè)試數(shù)據(jù)是：原串 100000個(gè) 1，匹配串 1000個(gè) 1. 若使用更極端的數(shù)據(jù)，如匹配串 10000個(gè) 1，則需要數(shù)秒出解，顯然過慢。對(duì)于隨機(jī)數(shù)據(jù)，由于匹配的可能性極小，用時(shí)很快是必然的。我們只考慮極端數(shù)據(jù)。 算法（優(yōu)化） int KMP() { int i,q=0。 for(i=1。i=ls。i++) { while(q0amp。amp。T[q+1]!=S[i]) q=next[q]。 if(T[q+1]==S[i]) q++。 if(q==lt) a[tot++]=ilt+1。 } } void ff() { int q,k。 for(q=1。q=lt。q++) { k=next[q]。 while(k0amp。amp。T[k+1]==T[q+1]) k=next[k]。 next[q]=k。 } } void f() { int q,k。 next[1]=0。k=0。 for(q=2。q=lt。q++) {while(k0amp。amp。T[k+1]!=T[q]) k=next[k]。 if(T[k+1]==T[q]) k=k+1。 next[q]=k。 } } 調(diào)用過程： f()。 ff()。 KMP()。 算法說明：函數(shù) f計(jì)算初始“回復(fù)位置”，函數(shù) ff計(jì)算優(yōu)化后的“回復(fù)位置”，函數(shù) KMP是依賴上述“回復(fù)位置”進(jìn)行快速匹配的算法。 S[i]為待匹配串， T[i]為目標(biāo)串， next[i]計(jì)算“回復(fù)位置”。 運(yùn)行時(shí)間：當(dāng)目標(biāo)串長(zhǎng) 1000，匹配串長(zhǎng) 100000 時(shí) 。目標(biāo)串長(zhǎng) 100 時(shí) 。目標(biāo)串長(zhǎng) 10 或 10000時(shí)，運(yùn)行時(shí)間 。可見， KMP 算法極快，確實(shí)是 O(n)的時(shí)間復(fù)雜度。故正確的優(yōu)化 KMP 算法是不會(huì)超時(shí)的。同樣，優(yōu)化 KMP與普通 KMP的差距也很明顯，尤其是在極端數(shù)據(jù)時(shí)。 四、最小生成樹算法的比較 void prim() { int lowcost[2020],closet[2020],i,j,k,min,tot=0。 for(i=1。i=n。i++) { lowcost[i]=cost[1][i]。 closet[i]=1。 } for(i=1。in。i++) { min=MAXINT。 for(j=1。j=n。j++) if(lowcost[j]minamp。amp。lowcost[j]!=0) { min=lowcost[j]。 k=j。 } tot+=lowcost[k]。 lowcost[k]=0。 for(j=1。j=n。j++) if(cost[k][j]lowcost[j]) { lowcost[j]=cost[k][j]。 closet[j]=k。 } } printf(%d ,tot)。 } 隨機(jī)數(shù)生成： for(i=1。i=MAX。i++) for(j=1。j=MAX。j++) if(i!=j) cost[i][j]=rand()。 當(dāng)數(shù)據(jù)范圍 MAX=2020時(shí)，平均 運(yùn)行時(shí)間： 。 由于 Prim算法是 O(n^2)的，速度快不是偶然。由此可見，最小生成樹不是程序運(yùn)行時(shí)間的瓶頸。從算法上看，我們注意到 Prim 算法十分類似求單源最短路徑的 Dijkstra 算法。兩種算法都是先找出不在集合中的最近元素，將其加入集合，并對(duì)該元素連接的點(diǎn)進(jìn)行松弛操作，更新各點(diǎn)到集合的距離。在具體實(shí)現(xiàn)中，都是利用一個(gè)數(shù) 組記錄每個(gè)點(diǎn)到集合的距離， 點(diǎn)在集合中用距離為零表示。 （較差） int father(int x) { if(set[x]!=x) set[x]=father(set[x])。 return set[x]。 } void kruskal() { int i,j,start,end,value,cost=0。 for(i=0。in。i++) set[i]=i。 for(k=1。kn。k++) { value=MAXINT。 for(i=0。in。i++) for(j=0。jn。j++) if(i!=jamp。amp。father(i)!=father(j)) if(data[i][j]value) { start=i。 end=j。 value=data[i][j]。 } cost+=value。 set[father(start)]=father(end)。 } printf(%d ,cost)。 } 當(dāng)規(guī)模 MAX=500時(shí)，運(yùn)行時(shí)間： 3563ms。顯然，當(dāng)圖為密集矩陣時(shí)， Kruskal算法并不迅速。但當(dāng)圖為稀疏圖時(shí)，算法的優(yōu)勢(shì)便很明顯了。 （優(yōu)化） int find(int x) { if(f[x]!=x) f[x]=find(f[x])。 return f[x]。 } void kruskal() { int i,j,a,b,tot=0,num=0。 for(i=0。in。i++) f[i]=i。 for(i=0。in。i++) { a=find(s[i])。 b=find(e[i])。 if(a!=b) { num++。 tot+=w[i]。 f[a]=b。 if(num==max) break。 } } printf(%d ,tot)。 } 主程序： for(i=1。in。i++) { f[i]=rand()%max。 e[i]=rand()%max。 w[i]=rand()。 } s=clock()。 sort(0,n1)。 kruskal()。 t=clock()。 此處 sort函數(shù)是快速排序函數(shù)，采用了本文上述“優(yōu)化的快速排序算法”。 當(dāng) max=100000時(shí)，即共 100000個(gè)點(diǎn)，共 1000000條邊時(shí)，平均運(yùn)行時(shí)間為 。當(dāng) max=10000 時(shí)，平均運(yùn)行時(shí)間為 。完全滿足時(shí)限 1s 的要求。而若使用 O(n^2)的Prim算法，運(yùn)行時(shí)間將不可思議。故 Kruskal算法十分適合稀疏圖的處理。 我們?cè)賮砜?Kruskal算法對(duì)于密集圖的效率。 for(i=0。imax。i++) for(j=0。jmax。j++) { f[i]=i。 e[i]=j。 w[i]=rand()。 } 當(dāng) max=2020時(shí)，平均運(yùn)行時(shí)間 ，比 Prim的 47ms慢了約 30倍。通過單獨(dú)測(cè)試 sort 時(shí)間可