Posted By

ldominov on 01/09/13


Tagged

c++


Versions (?)

alo


 / Published in: C++
 

hamilton cycles

  1. #include<iostream>
  2. #include<cstdlib>
  3. #define N 6
  4.  
  5. using namespace std;
  6.  
  7. void ispis_rj(int put[]);
  8.  
  9. bool valja (int v, bool graf[N][N], int put[], int pos)
  10. {
  11. if (graf[ put[pos-1] ][ v ] == 0) return false;
  12. for (int i = 0; i < pos; i++) if (put[i] == v) return false;
  13.  
  14. return true;
  15. }
  16.  
  17. void hamo(bool graf[N][N], int put[N], int pos){
  18. if (pos == N){
  19. if ( graf[ put[pos-1] ][ put[0] ] == 1 ) ispis_rj(put);
  20. return;
  21. }
  22. for (int v = 1; v < N; v++) {
  23. if (valja(v, graf, put, pos)) {
  24. put[pos] = v;
  25. hamo (graf, put, pos+1);
  26. put[pos] = -1;
  27. }
  28. }
  29. }
  30.  
  31. void ispis_rj(int put[]) {
  32. for (int i = 0; i < N; i++)
  33. cout << put[i]+1 << "\t" ;
  34. cout << put[0]+1 << endl;
  35. }
  36.  
  37. int main() {
  38. bool graf[N][N] = {{1, 0, 1, 1, 1, 1},
  39. {0, 1, 0, 1, 1, 0},
  40. {1, 0, 1, 0, 0, 1},
  41. {1, 1, 0, 1, 1, 1},
  42. {1, 1, 0, 1, 1, 0},
  43. {1, 0, 1, 1, 0, 1},
  44. };
  45. int *put = new int[N];
  46. for (int i = 0; i < N; i++) put[i] = -1;
  47. put[0] = 0;
  48. cout << "\nRjesenje (ako ga ima):" << endl;
  49. hamo (graf, put, 1);
  50.  
  51. system("pause");
  52. return 0;
  53. }

Report this snippet  

Comments

RSS Icon Subscribe to comments
Posted By: ldominov on January 9, 2013

abu

You need to login to post a comment.