1 #include <stdio.h> 2 int book[101],sum,n,e[101][101]; 3  4 void dfs(int cur) 5 { 6   int i; 7   printf("%d ",cur); 8   sum++; 9   if(sum==n) return;10   for(i=1;i<=n;i++)11   {12     if(e[cur][i]==1 && book[i]==0)13     {14       book[i]=1;15       dfs(i);16     }17   }18   return;19 }20 21 int main()22 {23   int i,j,m,a,b;24   scanf("%d %d", &n, &m);25                      26   for(i = 1; i <= n; i++)27     for(j = 1; j <= n; j++)28       if(i==j) e[i][j]=0;29         else e[i][j]=99999999;30           31   for(i=1;i<=m;i++)32   {33      scanf("%d %d", &a, &b);34      e[a][b]=1;35      e[b][a]=1;36   }37  38   book[1]=1;39   dfs(1);40   getchar(); getchar();41   return 0;42 }43 44 /*45 46 5 547 1 248 1 349 1 550 2 451 3 552 53 */

 1 #include <stdio.h> 2 int book[101],n,e[101][101]; 3  4 void dfs(int cur) 5 { 6   int i; 7   printf("%d ",cur); 8   for(i=1;i<=n;i++) 9   {10     if(e[cur][i]==1 && book[i]==0)11     {12       book[i]=1;13       dfs(i);14     }15   }16   return;17 }18 19 int main()20 {21   int i,j,m,a,b;22   scanf("%d %d", &n, &m);23                      24   for(i = 1; i <= n; i++)25     for(j = 1; j <= n; j++)26       if(i==j) e[i][j]=0;27         else e[i][j]=99999999;28           29   for(i=1;i<=m;i++)30   {31      scanf("%d %d", &a, &b);32      e[a][b]=1;33      e[b][a]=1;34   }35  36   book[1]=1;37   dfs(1);38   getchar(); getchar();39   return 0;40 }41 42 /*43 这组数据，使顶点四不连通44 45 5 546 1 247 1 348 1 549 2 350 3 551 52 5 553 1 254 1 355 1 556 2 457 3 558 59 */

 1 #include <stdio.h> 2 int main() 3 { 4   int i,j,n,m,a,b,cur,book[101]={0},e[101][101]; 5   int que[10001],head,tail; 6   scanf("%d %d", &n, &m); 7    8   for(i = 1; i <= n; i++) 9     for(j = 1; j <= n; j++)10       if(i==j) e[i][j]=0;11         else e[i][j]=99999999;12           13   for(i=1;i<=m;i++)14   {15      scanf("%d %d", &a, &b);16      e[a][b]=1;17      e[b][a]=1;18   }  19   20   head=1;21   tail=1;22   23   que[tail]=1;24   tail++;25   book[1]=1;26   27   while(head<tail)28   {29     cur=que[head];30     for(i=1;i<=n;i++)31     {32       if(e[cur][i]==1 && book[i]==0)33       {34         que[tail]=i;35         tail++;36         book[i]=1;37       }38       if(tail>n) break;39     }40     head++;41   }42   43   for(i=1;i<tail;i++)44     printf("%d ",que[i]);45 46   getchar(); getchar();47   return 0;48 }49 50 /*51 52 5 553 1 254 1 355 1 556 2 457 3 558 59 */

 1 #include <stdio.h> 2 int min=99999999, book[101], n, e[101][101]; 3  4 void dfs(int cur, int dis) 5 { 6   int i; 7   if(dis>min) return; 8   if(cur==n) 9   {10     if(dis<min) min=dis;11     return;12   }13 14   for(i=1;i<=n;i++)15   {16     if(e[cur][i] !=99999999 && book[i]==0)17     {18       book[i]=1;19       dfs(i,dis+e[cur][i]);20       book[i]=0;21     }22   }23   return;24 }25 26 int main()27 {28   int i,j,m,a,b,c;29   scanf("%d %d", &n, &m);30                      31   for(i = 1; i <= n; i++)32     for(j = 1; j <= n; j++)33       if(i==j) e[i][j]=0;34         else e[i][j]=99999999;35           36   for(i=1;i<=m;i++)37   {38      scanf("%d %d %d", &a, &b, &c);39      e[a][b]=c;40   }41  42   book[1]=1;43   dfs(1,0);44   printf("%d",min);45   46   getchar(); getchar();47   return 0;48 }49 50 /*51 52 5 853 1 2 254 1 5 1055 2 3 356 2 5 757 3 1 458 3 4 459 4 5 560 5 3 361 62 */

 1 #include <stdio.h> 2 int min=99999999, book[101], n, e[101][101]; 3 int start,end; // 4  5 void dfs(int cur, int dis) 6 { 7   int i; 8   if(dis>min) return; 9   if(cur==end) //10   {11     if(dis<min) min=dis;12     return;13   }14 15   for(i=1;i<=n;i++)16   {17     if(e[cur][i] !=99999999 && book[i]==0)18     {19       book[i]=1;20       dfs(i,dis+e[cur][i]);21       book[i]=0;22     }23   }24   return;25 }26 27 int main()28 {29   int i,j,m,a,b,c;30   scanf("%d %d", &n, &m);31                      32   for(i = 1; i <= n; i++)33     for(j = 1; j <= n; j++)34       if(i==j) e[i][j]=0;35         else e[i][j]=99999999;36           37   for(i=1;i<=m;i++)38   {39      scanf("%d %d %d", &a, &b, &c);40      e[a][b]=c;41      //e[b][a]=c; //添加这句，使之成为无向图 p14142   }43 44   scanf("%d %d",&start,&end); //最后一行，输入起点与终点45   book[start]=1; //46   dfs(start,0); //47   printf("%d",min);48   49   getchar(); getchar();50   return 0;51 }52 53 /*54 改编程序，使之能计算任意起点与终点间的最短路径55 56 5 857 1 2 258 1 5 1059 2 3 360 2 5 761 3 1 462 3 4 463 4 5 564 5 3 365 5 266 67 */

 1 #include <stdio.h> 2 struct note 3 { 4   int x; //城市编号 5   int s; //转机次数 6 }; 7  8 int main() 9 {10   struct note que[2501];11   int e[51][51]={0}, book[51]={0};12   int head,tail;13   int i,j,n,m,a,b,cur,start,end,flag=0;14   scanf("%d %d %d %d", &n, &m, &start, &end);15   16   for(i = 1; i <= n; i++)17     for(j = 1; j <= n; j++)18       if(i==j) e[i][j]=0;19         else e[i][j]=99999999;20           21   for(i=1;i<=m;i++)22   {23      scanf("%d %d", &a, &b);24      e[a][b]=1;25      e[b][a]=1;26   }  27   28   head=1;29   tail=1;30   31   que[tail].x=start;32   que[tail].s=0;33   tail++;34   //book[1]=start;35   book[start]=1;36   37   while(head<tail)38   {39     cur=que[head].x;40     for(i=1;i<=n;i++)41     {42       if(e[cur][i]!=99999999 && book[i]==0)43       {44         que[tail].x=i;45         que[tail].s=que[head].s+1;46         tail++;47         book[i]=1;48       }49       if(que[tail-1].x==end)50       {51         flag=1;52         break;53       }54     }55     if(flag==1) break;56     head++;57   }58   59   printf("%d\n",que[tail-1].s);60 61   getchar(); getchar();62   return 0;63 }64 65 /*66 67 5 7 1 568 1 269 1 370 2 371 2 472 3 473 3 574 4 575 76 */