Перебрать все пути в графе между двумя заданными вершинами, не содержащие одинаковых вершин на Си(C++)
Код на C++ #include <stdio.h> #include <conio.h> #include <alloc.h> #define n 5 char a[n][n]= { 1,1,1,0,1, 0,1,1,0,0, 0,0,1,1,0, 0,0,0,1,1, 0,0,0,0,1 }; char sp=0,ep=2; char *was,*pom,*path,cpath; FILE *fp; int graf(char p, char q,char nom) { int res = 0; was[p]=1; if (q == p)return 1; for (int i = 0; i < n; i++) if (i!=p && (a[p][i] || a[i][p]) && !was[i] && !pom[i]) { res=graf(i, q, nom+1); if (res){ if (i!=sp && i!=q) pom[i]=1; path[nom]=p; cpath++; break; } } return res; }; void main(void){ int i,j,fl; was=new char[n]; pom=new char[n]; cpath=0; for(i=0;i<n;i++){ was[i]=0;pom[i]=0;} fp=fopen("saodl2.txt","w"); if (a[sp][ep] || a[ep][sp]){ fl=1; a[ep][sp]=0; a[sp][ep]=0; fprintf(fp," %d %d = len: 1\n",sp,ep); } while (graf(sp,ep,0)){ for(i=0;i<n;i++) was[i]=0; for(j=0;j<cpath;j++){ fprintf(fp," %d",path[j]); } fprintf(fp," %d = len: %d\n",ep,cpath); cpath=0; } if (fl==1){fl=0;a[ep][sp]=1;a[sp][ep]=1;} fclose(fp); printf("\n File: caodl2.txt"); getch();
Полученный файл:
0 2 = len: 1
0 1 2 = len: 2
0 4 3 2 = len: 3
|