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


Добавил:DMT
Дата создания:20 мая 2008, 2:50
Дата обновления:20 мая 2008, 8:07
Просмотров:11198 последний сегодня, 1:43
Комментариев: 3

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

Код на Pascal
  1.  
  2. program Gamilton;
  3.  
  4. {$APPTYPE CONSOLE}
  5.  
  6. uses
  7. SysUtils;
  8.  
  9. const n=10;
  10.  
  11.  
  12. var
  13. v0:integer=2;
  14.  
  15. a:array[0..n-1, 0..n-1] of integer=(
  16. (0,0,0,0,0,1,0,0,0,0),
  17. (0,0,1,0,0,0,1,0,0,0),
  18. (0,1,0,1,0,0,0,1,0,0),
  19. (0,0,1,0,1,0,0,0,1,0),
  20. (1,0,0,1,0,0,0,0,0,1),
  21. (0,0,0,0,0,0,1,0,0,1),
  22. (0,0,0,1,0,0,0,1,0,0),
  23. (0,0,0,0,1,0,0,0,0,0),
  24. (0,0,0,0,0,0,0,0,0,1),
  25. (0,0,0,0,0,0,0,0,0,0));
  26. c:array[0..n-1] of integer;
  27. path:array[0..n-1] of integer;
  28.  
  29. procedure print_gamilton_c();
  30. var
  31. p:integer;
  32. begin
  33. for p:=0 to n-1 do write(inttostr(path[p])+' ');
  34. writeLn(inttostr(path[0]));
  35. end;
  36.  
  37. function gamilton(k:integer):integer;
  38. var
  39. v,gl:integer;
  40. begin
  41. gl:=0;
  42. v:=-1;
  43. while ((v<n) and (gl=0)) do begin
  44. inc(v);
  45. if (a[v,path[k-1]]>0) or (a[path[k-1],v]>0) then begin
  46. if (k=n) and (v=v0) then gl:=1
  47. else if (c[v]=-1) then begin
  48. c[v]:=k;
  49. path[k]:=v;
  50. gl:=gamilton(k+1);
  51. if (gl=0) then c[v]:=-1;
  52. end else continue;
  53. end;
  54. end;
  55. result:=gl;
  56.  
  57. end;
  58.  
  59. var
  60. j:integer;
  61.  
  62. begin
  63. writeln('Гамильтонов цикл:');
  64. for j:=0 to n-1 do c[j]:=-1;
  65. path[0]:=v0;
  66. c[v0]:=v0;
  67. if (gamilton(1)>0) then print_gamilton_c else writeln('цикл не найден - нет решений');
  68. end.
  69.  
При использовании обязательна ссылка на http://DMTSoft.ru
Резальтат: 2 1 6 3 8 9 5 0 4 7 2
up

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


Пользователь: monna_liza
Сообщений: 1
Статус: Незримый
Зарегистрирован:
2 декабря 2008, 5:51
Был:2 декабря 2008, 5:53
monna_liza
smsup
Дата: 2 декабря 2008, 5:52 Сообщение № 1
sm
Пользователь: нет
Сообщений: 1
Статус: Незримый
Зарегистрирован:
28 марта 2009, 5:15
Был:28 марта 2009, 6:13
нет
smsup
Дата: 28 марта 2009, 5:48 Сообщение № 2
sm
Пользователь: troy
Сообщений: 1
Статус: Незримый
Зарегистрирован:
2 апреля 2009, 0:38
Был:2 апреля 2009, 1:41
troy
smsup
Дата: 2 апреля 2009, 1:21 Сообщение № 3
Люди, хелп! Где взять исходник? Позарез надо! Выручайте!