Нахождение гамильтонова цикла в графе, заданном с помощью матрицы смежности на Си, C++


Добавил:DMT
Дата создания:25 апреля 2008, 11:55
Дата обновления:20 мая 2008, 2:47
Просмотров:15915 последний сегодня, 16:09
Комментариев: 1

Возьмем схему перебора с возвратом. Мы модифицируем её так, чтобы программа заканчивала работу при обнаружении гамильтонова цикла. Подпрограмма будет возвращать значение 1 в случае нахождения гамильтонова цикла, и 0 - если таких циклов в графе нет.

Код на C++
  1. #include <stdio.h>
  2. #include <conio.h>
  3. #include <alloc.h>
  4. #define n 10
  5.  
  6. int c[n] ; // номер хода, на котором посещается вершина
  7. int path[n]; // номера посещаемых вершин
  8. int v0=2; // начальная вершина
  9.  
  10. //Матрица смежности
  11. int a[n][n]=
  12. {
  13. 0,0,0,0,0,1,0,0,0,0,
  14. 0,0,1,0,0,0,1,0,0,0,
  15. 0,1,0,1,0,0,0,1,0,0,
  16. 0,0,1,0,1,0,0,0,1,0,
  17. 1,0,0,1,0,0,0,0,0,1,
  18. 0,0,0,0,0,0,1,0,0,1,
  19. 0,0,0,1,0,0,0,1,0,0,
  20. 0,0,0,0,1,0,0,0,0,0,
  21. 0,0,0,0,0,0,0,0,0,1,
  22. 0,0,0,0,0,0,0,0,0,0
  23. };
  24.  
  25. void prnt(void)
  26. {
  27. int p;
  28. for ( p = 0 ; p<n ; p++)
  29. printf("%d ", path[p] ) ;
  30. printf("%d ", path[0] ) ;
  31. printf("\n") ;
  32. }
  33.  
  34. //подпрограмма нахождения гамильтонова цикла
  35. int gamilton ( int k)
  36. {
  37. int v,q1=0;
  38. for(v=0; v<n && !q1; v++)
  39. {
  40. if(a[v][path[k-1]]||a[path[k-1]][v])
  41. {
  42. if (k==n && v==v0 ) q1=1;
  43. else if (c[v]==-1)
  44. {
  45. c[v] = k ; path[k]=v;
  46. q1=gamilton (k+1) ;
  47. if (!q1) c[v]=-1;
  48. } else continue;
  49. }
  50. } return q1;
  51. }
  52.  
  53. main()
  54. {
  55. int j;
  56. clrscr() ;
  57. printf("Гамильтонов цикл:\n");
  58. for(j=0;j<n;j++) c[j]=-1;
  59. path[0]=v0 ;
  60. c[v0]=v0;
  61. if(gamilton (1)) prnt(); else printf("Нет решений\n");
  62. }
  63.  
При использовании обязательна ссылка на http://DMTSoft.ru
Резальтат: 2 1 6 3 8 9 5 0 4 7 2
up

Комментарии для "Нахождение гамильтонова цикла в графе, заданном с помощью матрицы смежности на Си, C++"


Пользователь: vetal-gal89
Сообщений: 1
Статус: Незримый
Зарегистрирован:
17 декабря 2008, 19:01
Был:17 декабря 2008, 19:02
vetal-gal89
smsup
Дата: 17 декабря 2008, 19:02 Сообщение № 1
sm