Перебрать все пути в графе между двумя заданными вершинами, не содержащие одинаковых вершин на Си(C++)


Добавил:DMT
Дата создания:28 апреля 2008, 14:46
Дата обновления:28 апреля 2008, 14:46
Просмотров:8499 последний сегодня, 10:55
Комментариев: 0
Перебрать все пути в графе между двумя заданными вершинами, не содержащие одинаковых вершин на Си(C++)
Код на C++
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <alloc.h>
  4.  
  5. #define n 5
  6. char a[n][n]=
  7. { 1,1,1,0,1,
  8. 0,1,1,0,0,
  9. 0,0,1,1,0,
  10. 0,0,0,1,1,
  11. 0,0,0,0,1
  12. };
  13. char sp=0,ep=2;
  14. char *was,*pom,*path,cpath;
  15.  
  16. FILE *fp;
  17.  
  18. int graf(char p, char q,char nom)
  19. {
  20. int res = 0;
  21. was[p]=1;
  22. if (q == p)return 1;
  23. for (int i = 0; i < n; i++)
  24. if (i!=p && (a[p][i] || a[i][p]) && !was[i] && !pom[i])
  25. { res=graf(i, q, nom+1);
  26. if (res){
  27. if (i!=sp && i!=q) pom[i]=1;
  28. path[nom]=p;
  29. cpath++;
  30. break;
  31. }
  32. }
  33. return res;
  34. };
  35.  
  36. void main(void){
  37. int i,j,fl;
  38. was=new char[n];
  39. pom=new char[n];
  40. cpath=0;
  41. for(i=0;i<n;i++){ was[i]=0;pom[i]=0;}
  42. fp=fopen("saodl2.txt","w");
  43.  
  44. if (a[sp][ep] || a[ep][sp]){
  45. fl=1;
  46. a[ep][sp]=0;
  47. a[sp][ep]=0;
  48. fprintf(fp," %d %d = len: 1\n",sp,ep);
  49. }
  50. while (graf(sp,ep,0)){
  51. for(i=0;i<n;i++) was[i]=0;
  52. for(j=0;j<cpath;j++){
  53. fprintf(fp," %d",path[j]);
  54. }
  55. fprintf(fp," %d = len: %d\n",ep,cpath);
  56. cpath=0;
  57. }
  58. if (fl==1){fl=0;a[ep][sp]=1;a[sp][ep]=1;}
  59.  
  60. fclose(fp);
  61. printf("\n File: caodl2.txt");
  62. getch();
При использовании обязательна ссылка на http://DMTSoft.ru
Полученный файл:
0 2 = len: 1
0 1 2 = len: 2
0 4 3 2 = len: 3
up