常用算法及其實(shí)現(xiàn)

1、常用算法經(jīng)典代碼（C+版） 一、快速排序void qsort(int x,int y) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中  int h=x,r=y;   int m=a(x+y)>>1; /取中間的那個(gè)位置的值   while(h<r)while (ah<m) h+; /比中間那個(gè)位置的值小，循環(huán)直到找一個(gè)比中間那個(gè)值大的      while (ar>m) r-; /比中間那個(gè)位置的值大，循環(huán)直到找一個(gè)比中間那個(gè)值小的  

2、0;   if(h<=r)int temp=ah;/如果此時(shí)h<=r，交換ah和ar         ah=ar;         ar=temp;         h+;r-; /這兩句必不可少哦     if(r>x) qsort(x,r);/注意此處，尾指針跑到前半部分了&#

3、160;    if(h<y) qsort(h,y); /注意此處，頭指針跑到后半部分了調(diào)用：qsort(1,n)即可實(shí)現(xiàn)數(shù)組a中元素有序。適用于n比較大的排序 二、冒泡排序void paopao(void) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;i<n;i+)  /控制循環(huán)（冒泡）的次數(shù)，n個(gè)數(shù)，需要n-1次冒泡  for(int j=1;j<=n-i;j+) /相鄰的兩兩比較    if(aj<aj+1) int temp=aj;aj=aj+1;aj+1=

4、temp;或者void paopao(void) /待排序的數(shù)據(jù)存放在a1.an數(shù)組中for(int i=1;i<n;i+)  /控制循環(huán)（冒泡）的次數(shù)，n個(gè)數(shù)，需要n-1次冒泡  for(int j=n-i;j>=1;j-) /相鄰的兩兩比較    if(aj<aj+1) int temp=aj;aj=aj+1;aj+1=temp; 調(diào)用：paopao()，適用于n比較小的排序 三、桶排序void bucketsort(void)/a的取值范圍已知。如a<=cmax。 memset(ton

5、g,0,sizeof(tong);/桶初始化for(int i=1;i<=n;i+)/讀入n個(gè)數(shù)    int acin>>a;tonga+;/相應(yīng)的桶號(hào)計(jì)數(shù)器加1  for(int i=1;i<=cmax;i+)  if(tongi>0) /當(dāng)桶中裝的樹(shù)大于0，說(shuō)明i出現(xiàn)過(guò)tongi次，否則沒(méi)出現(xiàn)過(guò)i     while (tongi!=0)       tongi-;cout<<i<< ;

6、 桶排序適用于那些待排序的關(guān)鍵字的值在已知范圍的排序。 四、合（歸）并排序void merge(int l,int m,int r)/合并l,m和m+1,r兩個(gè)已經(jīng)有序的區(qū)間 int b101;/借助一個(gè)新的數(shù)組B，使兩個(gè)有序的子區(qū)間合并成一個(gè)有序的區(qū)間，b數(shù)組的大小要注意  int h,t,k;  k=0;/用于新數(shù)組B的指針  h=l;t=m+1;/讓h指向第一個(gè)區(qū)間的第一個(gè)元素，t指向第二個(gè)區(qū)間的第一個(gè)元素。  while(h<=m)&&(t<=r)/在指針h和t沒(méi)有到區(qū)間尾時(shí)，把兩個(gè)區(qū)間的元素抄在新

7、數(shù)組中    k+;       /新數(shù)組指針加1     if (ah<at)bk=ah;h+;       /抄第一個(gè)區(qū)間元素到新數(shù)組     elsebk=at;t+;   /抄第二個(gè)區(qū)間元素到新數(shù)組      while(h<=m)k+;bk=ah;h+;  /如果第一個(gè)區(qū)間沒(méi)有

8、抄結(jié)束，把剩下的抄在新數(shù)組中  while(t<=r)k+;bk=at;t+;   /如果第二個(gè)區(qū)間沒(méi)有抄結(jié)束，把剩下的抄在新數(shù)組中  for(int o=1;o<=k;o+)/把新數(shù)組中的元素，再抄回原來(lái)的區(qū)間，這兩個(gè)連續(xù)的區(qū)間變?yōu)橛行虻膮^(qū)間。al+o-1=bo;void mergesort(int x,int y)/對(duì)區(qū)間x,y進(jìn)行二路歸并排序  int mid;  if(x>=y) return;  mid=(x+y)/2;/求x,y區(qū)間，中間的那個(gè)點(diǎn)mid,mid把x,y區(qū)間一分為二  m

9、ergesort(x,mid);/對(duì)前一段進(jìn)行二路歸并  mergesort(mid+1,y);/對(duì)后一段進(jìn)行二路歸并  merge(x,mid,y);/把已經(jīng)有序的前后兩段進(jìn)行合并 歸并排序應(yīng)用了分治思想，把一個(gè)大問(wèn)題，變成兩個(gè)小問(wèn)題。二分是分治的思想。 五、二分查找int find(int x,int y,int m) /在x,y區(qū)間查找關(guān)鍵字等于m的元素下標(biāo) int head,tail,mid;  head=x;tail=y;mid=(x+y)/2);/取中間元素下標(biāo)  if(amid=m) return mid;/如果中間元素

10、值為m返回中間元素下標(biāo)mid  if(head>tail) return 0;/如果x>y，查找失敗，返回0  if(m>amid)  /如果m比中間元素大，在后半?yún)^(qū)間查找，返回后半?yún)^(qū)間查找結(jié)果    return find(mid+1,tail);  else /如果m比中間元素小，在前半?yún)^(qū)間查找，返回后前區(qū)間查找結(jié)果    return find(head,mid-1);六、高精度加法#include<iostream>#include<cstring&g

11、t;using namespace std;int main()  string str1,str2;  int a250,b250,len;   /數(shù)組的大小決定了計(jì)算的高精度最大位數(shù)  int i;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;   /輸入兩個(gè)字符串  a0=str1.length();  /取得第一個(gè)字符串的長(zhǎng)度  for(i=1;i<

12、;=a0;i+)  /把第一個(gè)字符串轉(zhuǎn)換為整數(shù)，存放在數(shù)組a中    ai=str1a0-i-'0'  b0=str2.length();   /取得第二個(gè)字符串長(zhǎng)度  for(i=1;i<=b0;i+)   /把第二個(gè)字符串中的每一位轉(zhuǎn)換為整數(shù)，存放在數(shù)組B中    bi=str2b0-i-'0'  len=(a0>b0?a0:b0);   /取兩個(gè)字符串最大的長(zhǎng)度  for(i=

13、1;i<=len;i+)   /做按位加法，同時(shí)處理進(jìn)位      ai+=bi;    ai+1+=ai/10;    ai%=10;       len+;    /下面是去掉最高位的0，然后輸出。  while(alen=0)&&(len>1) len-;  for(i=len;i>=1;i-)    cou

14、t<<ai;  return 0;  注意：兩個(gè)數(shù)相加，結(jié)果的位數(shù)，應(yīng)該比兩個(gè)數(shù)中大的那個(gè)數(shù)多一位。 七、高精度減法#include<iostream>using namespace std;int compare(string s1,string s2);int main()  string str1,str2;  int a250,b250,len;  int i;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin&

15、gt;>str1>>str2;  a0=str1.length();  for(i=1;i<=a0;i+)    ai=str1a0-i-'0'  b0=str2.length();  for(i=1;i<=b0;i+)    bi=str2b0-i-'0'  if(compare(str1,str2)=0)  /大于等于，做按位減，并處理借位。      for(i=1;i

16、<=a0;i+)      ai-=bi;       if (ai<0) ai+1-;ai+=10;          a0+;    while(aa0=0)&&(a0>1) a0-;    for(i=a0;i>=1;i-)      cout<&

17、lt;ai;    cout<<endl;                               else      cout<<'-'  /小于就輸出負(fù)號(hào)   

18、for(i=1;i<=b0;i+)  /做按位減，大的減小的      bi-=ai;       if (bi<0) bi+1-;bi+=10;          b0+;    while(bb0=0)&&(b0>1) b0-;    for(i=b0;i>=1;i-)  &

19、#160;   cout<<bi;    cout<<endl;            return 0; int compare(string s1,string s2)  /比較字符串（兩個(gè)數(shù)）數(shù)字的大小，大于等于返回0，小于返回1。  if(s1.length()>s2.length() return 0;  /先比較長(zhǎng)度，哪個(gè)字符串長(zhǎng)，對(duì)應(yīng)的那個(gè)數(shù)就大  if

20、(s1.length()<s2.length() return 1;  for(int i=0;i<=s1.length();i+)  /長(zhǎng)度相同時(shí)，就一位一位比較。      if(s1i>s2i) return 0;    if(s1i<s2i) return 1;                  

21、            return 0;   /如果長(zhǎng)度相同，每一位也一樣，就返回0，說(shuō)明相等 做減法時(shí)，首先要判斷兩個(gè)字符串的大小，決定是否輸出負(fù)號(hào)，然后就是按位減法，注意處理借位。 八、高精度乘法#include<iostream>#include<cstring>using namespace std;int main()  string str1,str2;  int a250,b250,c500,le

22、n;    /250位以?xún)?nèi)的兩個(gè)數(shù)相乘  int i,j;  memset(a,0,sizeof(a);  memset(b,0,sizeof(b);  cin>>str1>>str2;  a0=str1.length();  for(i=1;i<=a0;i+)    ai=str1a0-i-'0'  b0=str2.length();  for(i=1;i<=b0;i+)  

23、0; bi=str2b0-i-'0'  memset(c,0,sizeof(c);  for(i=1;i<=a0;i+)   /做按位乘法同時(shí)處理進(jìn)位，注意循環(huán)內(nèi)語(yǔ)句的寫(xiě)法。    for(j=1;j<=b0;j+)        ci+j-1+=ai*bj;    ci+j+=ci+j-1/10;    ci+j-1%=10;    &#

24、160;    len=a0+b0+1;  /去掉最高位的0，然后輸出  while(clen=0)&&(len>1) len-;   /為什么此處要len>1?  for(i=len;i>=1;i-)    cout<<ci;  return 0;  注意：兩個(gè)數(shù)相乘，結(jié)果的位數(shù)應(yīng)該是這兩個(gè)數(shù)的位數(shù)和減1。優(yōu)化：萬(wàn)進(jìn)制#include<iostream>#include<cstring>usin

25、g namespace std;void num1(int s,string st1);int a2501,b2501,c5002;/此處可以進(jìn)行2500位萬(wàn)進(jìn)制乘法，即10000位十進(jìn)制乘法。Int main()      string str1,str2;    int len;    cin>>str1>>str2;    memset(a,0,sizeof(a);    memset(b,0,s

26、izeof(b);    memset(c,0,sizeof(c);    num1(a,str1); /把str1從最低位開(kāi)始，每4位存放在數(shù)組a中    num1(b,str2); /把str2從最低位開(kāi)始，每4位存放在數(shù)組b中    for(int i=1;i<=a0;i+) /作按位乘法并處理進(jìn)位，此處是萬(wàn)進(jìn)制進(jìn)位      for(int j=1;j<=b0;j+)   &#

27、160;              ci+j-1+=ai*bj;          ci+j+=ci+j-1/10000;          ci+j-1%=10000;            len

28、=a0+b0;/a0和b0存放的是每個(gè)數(shù)按4位處理的位數(shù)    while (clen=0)&&(len>1) len-;/去掉高位的0，并輸出最高位      cout<<clen;    for(int i=len-1;i>=1;i-)/把剩下來(lái)的每一位還原成4位輸出              if (ci<1000)

29、 cout<<0;        if (ci<100) cout<<0;        if (ci<10) cout<<0;                cout<<ci;       

30、0;  cout<<endl;    return 0;void num1(int s,string st1)/此函數(shù)的作用就是把字符串st1，按4位一組存放在數(shù)組s中   int k=1,count=1;    s0=st1.length();/存放st1的長(zhǎng)度，省去一長(zhǎng)度變量    for(int i=s0-1;i>=0;i-) /從最低位開(kāi)始，處理每一位    if (count%4=0) sk+=(st1i-0)*100

31、0; if(i!=0) k+;      if (count%4=1) sk=(st1i-0);      if (count%4=2) sk+=(st1i-0)*10;      if (count%4=3) sk+=(st1i-0)*100;      count+;        s0=k; /存放數(shù)組的位數(shù)，就是按4位處理后的萬(wàn)進(jìn)

32、制數(shù)的位數(shù)。      Return; 九、高精度除法（沒(méi)講） 十、篩選法建立素?cái)?shù)表void maketable(int x)/建立X以?xún)?nèi)的素?cái)?shù)表prim，primi為0，表示i為素?cái)?shù)，為1表示不是質(zhì)數(shù) memset(prim,0,sizeof(prim);/初始化質(zhì)數(shù)表 prim0=1;prim1=1;prim2=0;/用篩選法求X以?xún)?nèi)的質(zhì)數(shù)表 for(int i=2;i<=x;i+)    if (primi=0)   

33、60; int j=2*i;      while(j<=x)       primj=1;j=j+i; 對(duì)于那些算法中，經(jīng)常要判斷素?cái)?shù)的問(wèn)題，建立一個(gè)素?cái)?shù)表，可以達(dá)到一勞永逸的目的。 十一、深度優(yōu)先搜索void dfs(int x)  以圖的深度優(yōu)先遍歷為例。           cout<<x<< ; 訪問(wèn)x頂點(diǎn)  

34、;    visitedx=1; 作已訪問(wèn)的標(biāo)記      for(int k=1;k<=n;k+) 對(duì)與頂點(diǎn)x相鄰而又沒(méi)訪問(wèn)過(guò)的結(jié)點(diǎn)k進(jìn)行深度優(yōu)先搜索。        if(axk=1)&&(visitedk=0)         dfs(k);    十二、廣度優(yōu)先搜索void  bfs(void) /

35、按廣度優(yōu)先非遞歸遍歷圖G，n個(gè)頂點(diǎn)，編號(hào)為1.n。注：圖不一定是連通的/使用輔助隊(duì)列Q和訪問(wèn)標(biāo)記數(shù)組visited。    for(v=1;v<=n;v+)  visitedv=0；/標(biāo)記數(shù)組初始化    for(v=1; v<=n; v+)      if(visitedv=0 )         /v尚未訪問(wèn)       

36、  int h=1,r=1;    /置空的輔助隊(duì)列q         visitedv=1；/頂點(diǎn)v,作訪問(wèn)標(biāo)記         cout<<v<< ; /訪問(wèn)頂點(diǎn)v         qr=v；    /v入隊(duì)列    &#

37、160;    while(h<=r) /當(dāng)隊(duì)列非空時(shí)循環(huán)              int tmp=qh;  /隊(duì)頭元素出隊(duì)，并賦值給tmp             for(int j=1;j<=n;j+)       

38、60;       if(visitedj=0)&&(atmpj=1)/j為tmp的尚未訪問(wèn)的鄰接頂點(diǎn)                    visitedj=1;  對(duì)j作訪問(wèn)標(biāo)記            

39、;        cout<<j<< ; 訪問(wèn)j                    r+; /隊(duì)尾指針加1qr=j; /j入隊(duì)  /end-if             h+;

40、60;          /end -while十三、二叉樹(shù)的前序、中序和后序遍歷void preorder(int x)/二叉樹(shù)的先序遍歷    if(x=0) return;   cout<<x;/先訪問(wèn)根   preorder(ax.ld);/再先序遍歷根的左子樹(shù)   preorder(ax.rd);/最后先序遍歷根的右子樹(shù) void inorder(int x)/二叉樹(shù)的中序遍歷

41、0;   if(x=0) return;   preorder(ax.ld);/先中序遍歷根的左子樹(shù)   cout<<x;/再訪問(wèn)根   preorder(ax.rd);/最后中序遍歷根的右子樹(shù) void reorder(int x)/二叉樹(shù)的后序遍歷    if(x=0) return;   preorder(ax.ld);/先后序遍歷根的左子樹(shù)   preorder(ax.rd);/再后序遍歷根的右子樹(shù) 

42、60; cout<<x;/最后訪問(wèn)根  十四、樹(shù)轉(zhuǎn)換為二叉樹(shù)算法 十五、二叉排序樹(shù) 十六、哈夫曼樹(shù)void haff(void) /構(gòu)建哈夫曼樹(shù)   for(int i=n+1;i<=2*n-1;i+) /依次生成n-1個(gè)結(jié)點(diǎn)     int l=fmin(i-1); /查找權(quán)值最小的結(jié)點(diǎn)的編號(hào)l       ai.lchild=l; /把l作為結(jié)點(diǎn)i的左孩子     

43、  al.father=i; /把l的父結(jié)點(diǎn)修改為i       int r=fmin(i-1); /查找次小權(quán)值的編號(hào)r       ai.rchild=r; /把l作為結(jié)點(diǎn)i的右孩子       ar.father=i; /把r的父結(jié)點(diǎn)修改為i       ai.da=al.da+ar.da; /合并l,j結(jié)點(diǎn)，生成新結(jié)點(diǎn)i 

44、0;   int fmin(int k)/在1到K中尋找最小的權(quán)值的編號(hào)                int mins=0;         for(int s=1;s<=k;s+)           if(amins.da>as.da)&&(as.fath

45、er=0) /as.father=0,說(shuō)明這個(gè)結(jié)點(diǎn)還不是別個(gè)結(jié)點(diǎn)mins=s;                           /的孩子，不等于0說(shuō)明這個(gè)結(jié)點(diǎn)已經(jīng)用過(guò)。         return mins;    

46、0;  void inorder(int x)/遞歸生成哈夫曼編碼  if(ax.father=0) ax.code=”“;/根結(jié)點(diǎn)  if(aax.father.lchild=x)  ax.code=aax.father.code+'0'  if(aax.father.rchild=x)  ax.code=aax.father.code+'1'  if(ax.lchild!=0) inorder(ax.lchild);/遞歸生成左子樹(shù)  if(ax.lchild=0)&&a

47、mp;(ax.rchild=0)/輸出葉子結(jié)點(diǎn)     cout<<ax.da<<':'<<ax.code<<endl;  if(ax.rchild!=0) inorder(ax.rchild);/遞歸生成右子樹(shù)十七、并查集int getfather(int x)/非遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào)while(x!=fatherx)  x=fatherx; return x; int getfather(int x)/遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)的編號(hào)if(x=fa

48、therx) return x; else return getfather(fatherx);  int getfather(int x)/非遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)編號(hào)同時(shí)進(jìn)行路徑壓縮int p=x;while(p!=fatherp)/循環(huán)結(jié)束后，P即為根結(jié)點(diǎn)   p=fatherp; while(x!=fatherx)/從X結(jié)點(diǎn)沿X的父結(jié)點(diǎn)進(jìn)行路徑壓縮   int temp=fatherx;/暫存X沒(méi)有修改前的父結(jié)點(diǎn)fatherx=p;/把X的父結(jié)點(diǎn)指向Px=temp;    ret

49、urn p; int getfather(int x)/遞歸求X結(jié)點(diǎn)的根結(jié)點(diǎn)編號(hào)同時(shí)進(jìn)行路徑壓縮if(x=fatherx) return x; else        int temp=getfather(fatherx);       fatherx=temp;       return temp; void merge(int x,int y)/合并x,y兩個(gè)結(jié)點(diǎn) int

50、x1,x2;  x1=getfather(x);/取得X的父結(jié)點(diǎn)  x2=getfather(y);/取得Y的父結(jié)點(diǎn)  if(x1!=x2) fatherx1=x2; /兩個(gè)父結(jié)點(diǎn)不同的話(huà)就合并，注意：合并的是X，Y兩個(gè)結(jié)點(diǎn)的根。 十八、Prime算法void prime(void) /prim算法求最小生成樹(shù)，elisti是邊集數(shù)組，aij為<I,j>的權(quán)值。edge為結(jié)構(gòu)體類(lèi)型。for (int i=1;i<=n-1;i+)/初始化結(jié)點(diǎn)1到其它n-1個(gè)結(jié)點(diǎn)形成的邊集   elisti.from=1;elisti.

51、to=i+1;elisti.w=a1i+1;    for (int i=1;i<=n-1;i+)/依次確定n-1條邊  int m=i;   for(int j=i+1;j<=n-1;j+)/確定第i條邊時(shí)，依次在i+1至n-1條邊中找最小的那條邊     if(elistj.w<elistm.w) m=j;   if(m!=i) /如果最小的邊不是第i條邊就交換edge tmp=elisti;elisti=elistm;elistm=tmp; 

52、  for(int j=i+1;j<=n-1;j+)/更新第i+1至n-1條邊的最小距離。     if(elistj.w>aelisti.toelistj.to) elistj.w=aelisti.toelistj.to;                          &

53、#160; for(int i=1;i<=n-1;i+)/求最小生成樹(shù)的值ans=ans+elisti.w;                        如果要求出哪些邊構(gòu)成最小生成樹(shù)，在更新第i+1至n-1條邊到已經(jīng)生成的樹(shù)中最小距離時(shí)(上面代碼中加粗的部分)，還要加上elistj.from=elisti.to;語(yǔ)句，即在更新權(quán)值時(shí)，還應(yīng)該更新起點(diǎn)

54、。Prime算法適用于頂點(diǎn)不是太多的稠密圖，如果對(duì)于頂點(diǎn)數(shù)較多的稀疏圖，就不太適用了。 十九、Dijkstra算法void dijkstra(int x)  /求結(jié)點(diǎn)x到各個(gè)結(jié)點(diǎn)的最短路徑memset(vis,0,sizeof(vis); /初始化，visi0表示源點(diǎn)到結(jié)點(diǎn)i未求，否則已求visx=1;prex=0; /初始化源點(diǎn)。for(int i=1;i<=n;i+)   /對(duì)其它各點(diǎn)初始化。    if(i!=x)disi=gxi;prei=x;for(int i=1;i<=n-1;i+) 

55、60; /對(duì)于n個(gè)結(jié)點(diǎn)的圖，要求x到其它n-1個(gè)結(jié)點(diǎn)的最短距離    int m=big; /虛擬一個(gè)最大的數(shù)big=99999999;int k=x;      for(int j=1;j<=n;j+)   /在未求出的結(jié)點(diǎn)中找一個(gè)源點(diǎn)到其距離最小的點(diǎn)        if(visj=0&&m>disj)m=disj;k=j;      visk=1

56、;   /思考：如果k=X說(shuō)明什么？說(shuō)明后面的點(diǎn)，無(wú)解。      for(int j=1;j<=n;j+)   /用當(dāng)前找的結(jié)點(diǎn)更新未求結(jié)點(diǎn)到X的最短路徑      if(visj=0)&&(disk+gkj<disj)                   &

57、#160;disj=disk+gkj;  /更新         prej=k;  /保存前趨結(jié)點(diǎn)，以便后面求路徑            說(shuō)明：disi表示x到i的最短距離，prei表示i結(jié)點(diǎn)的前趨結(jié)點(diǎn)。二十、Kruscal算法void qsort(int x,int y)/對(duì)邊集數(shù)組進(jìn)行快速排序int h=x,r=y,m=elist(h+r)>>1.w; while(h&l

58、t;r)  while(elisth.w<m) h+;   while(elistr.w>m) r-;   if(h<=r)    edge tmp=elisth;elisth=elistr;elistr=tmp;h+;r-;   if(x<r) qsort(x,r); if(h<y) qsort(h,y); int getfather(int x)/找根結(jié)點(diǎn)，并壓縮路徑，此處用遞歸實(shí)現(xiàn)的。if(x=fatherx) return x; 

59、;else         int f=getfather(fatherx);        fatherx=f;        return f;       void merge(int x,int y)/合并x,y結(jié)點(diǎn)，在此題中的x,y為兩個(gè)根結(jié)點(diǎn)。fatherx=y; void kruscal(void)int

60、 sum=0,ans=0;qsort(1,t);/對(duì)t條邊按權(quán)值大小按從小到大的次序進(jìn)行快速排序   for(int i=1;i<=t;i+)     int x1=getfather(elisti.from);/取第i條邊的起點(diǎn)所在的樹(shù)的根int x2=getfather(elisti.to);/ 取第i條邊的終點(diǎn)所在的樹(shù)的根if(x1!=x2)sum+;merge(x1,x2);ans+=elisti.w;/不在同一個(gè)集合，合并，即第i條邊可以選取。if(sum>n-1)break;/已經(jīng)確定了n-1條邊了，最小生成樹(shù)

61、已經(jīng)生成了，可以提前退出循環(huán)了   if(sum<n-1)cout<<"Impossible"<<endl; /從t條邊中無(wú)法確定n-1條邊，說(shuō)明無(wú)法生成最小生成樹(shù)   else  cout<<ans<<endl;   克魯斯卡爾算法，只用了邊集數(shù)組，沒(méi)有用到圖的鄰接矩陣，因此當(dāng)圖的結(jié)點(diǎn)數(shù)比較多的時(shí)候，輸入數(shù)據(jù)又是邊的信息時(shí)，就要考慮用Kruscal算法。對(duì)于島國(guó)問(wèn)題，我們就要選擇此算法，如果用Prim算法，還要開(kāi)一個(gè)二維的數(shù)組來(lái)表示圖的鄰接矩陣，對(duì)于

62、10000個(gè)點(diǎn)的數(shù)據(jù)，顯然在空間上是無(wú)法容忍的。 二十一、Floyed算法void floyed(void)/ aij表示結(jié)點(diǎn)i到結(jié)點(diǎn)j的最短路徑長(zhǎng)度，初始時(shí)值為<I,J>的權(quán)值。for(int k=1;k<=n;k+) /枚舉中間加入的結(jié)點(diǎn)不超過(guò)K時(shí)fij最短路徑長(zhǎng)度，K相當(dāng)DP中的階段        for(int i=1;i<=n;i+) /i，j是結(jié)點(diǎn)i到結(jié)點(diǎn)J，相當(dāng)于DP中的狀態(tài)for(int j=1;j<=n;j+)      if (aij>aik+akj) aij=aik+akj;/這是決策，加和不加中間點(diǎn)，