0 / 0 / 0
Регистрация: 21.11.2009
Сообщений: 41
1

Поиск гамильтонова цикла в графе

07.02.2010, 21:20. Показов 9167. Ответов 3
Метки нет (Все метки)

ПОмогите плиииз!!!
Написать программу поиска гамильтонова цикла в графе
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.02.2010, 21:20
Ответы с готовыми решениями:

Поиск гамильтонова цикла в графе
Написать программу поиска гамильтонова цикла в графе.

Поиск эйлерова цикла в графе заданном списком инцидентности
Уважаемые форумчане необходимо найти эйлеров цикл в графе, не содержащем вершин нечетной степени и...

Поиск гамильтонова цикла в графе
Написать программу гамильтонова цикла в графе для PascalABC Помогите пожалуйста Добавлено...

Поиск гамильтонова цикла в ориентированном графе
Честно пытался искать по форуму и не только, но так толком ничего и не нашел :\ Необходимо узнать,...

3
88 / 88 / 56
Регистрация: 05.12.2009
Сообщений: 134
07.02.2010, 21:48 2
Лучший ответ Сообщение было отмечено как решение

Решение

Нахождение гамильтонова цикла в графе, заданном с помощью матрицы смежности.
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
uses SysUtils;
const n=10;
var v0:integer=2;
     a:array[0..n-1, 0..n-1] of integer=(
(0,0,0,0,0,1,0,0,0,0),
(0,0,1,0,0,0,1,0,0,0),
(0,1,0,1,0,0,0,1,0,0),
(0,0,1,0,1,0,0,0,1,0),
(1,0,0,1,0,0,0,0,0,1),
(0,0,0,0,0,0,1,0,0,1),
(0,0,0,1,0,0,0,1,0,0),
(0,0,0,0,1,0,0,0,0,0),
(0,0,0,0,0,0,0,0,0,1),
(0,0,0,0,0,0,0,0,0,0));
c:array[0..n-1] of integer;
path:array[0..n-1] of integer;
 
procedure print_gamilton_c();
var p:integer;
begin
 for p:=0 to n-1 do write(inttostr(path[p])+' ');
 writeLn(inttostr(path[0]));
end;
 
function gamilton(k:integer):integer;
var v,gl:integer;
begin
 gl:=0;
 v:=-1;
 while ((v<n) and (gl=0)) do
  begin
   inc(v);
   if (a[v,path[k-1]]>0) or (a[path[k-1],v]>0) then begin
   if (k=n) and (v=v0) then gl:=1
   else if (c[v]=-1) then
    begin
     c[v]:=k;
     path[k]:=v;
     gl:=gamilton(k+1);
     if (gl=0) then c[v]:=-1;
    end 
   else continue;
   end;
  end;
 result:=gl;
end;
 
var j:integer;
begin
 writeln('Гамильтонов цикл:');
 for j:=0 to n-1 do c[j]:=-1;
 path[0]:=v0;
 c[v0]:=v0;
 if (gamilton(1)>0) then print_gamilton_c 
 else writeln('цикл не найден - нет решений');
end.
Добавлено через 54 секунды
Возьмем схему перебора с возвратом. Мы модифицируем её так, чтобы программа заканчивала работу при обнаружении гамильтонова цикла. Подпрограмма будет возвращать значение 1 в случае нахождения гамильтонова цикла, и 0 - если таких циклов в графе нет.
4
0 / 0 / 0
Регистрация: 21.11.2009
Сообщений: 41
07.02.2010, 23:49  [ТС] 3
спасибо огромное!!!!
0
Jezrok
22.05.2013, 00:22 4
Tom_Sawyer молодець (+1).
Якщо зразу не запускаєтся то у 30-му рядку (v<n) поміняти на (v<n-1)
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
22.05.2013, 00:22
Помогаю со студенческими работами здесь

Нахождение гамильтонова цикла в графе
Как заставить код работать? По условию задачи нужно найти гамильтонов цикл в графе. Если такового...

Алгебраический алгоритм поиска гамильтонова цикла в графе.
ребята, может кто-нибудь помочь?очень надо сдаю курсовую работу по теме ПОИСК ГАМИЛЬТОНОВА ЦИКЛА В...

Поиск минимального гамильтонова цикла в матрице
#include &lt;iostream&gt; using namespace std; #define n 10 int c ; // номер хода, на котором...

Поиск минимального Гамильтонова цикла по заданным координатам
Здравствуйте ,есть код #include &lt;iostream&gt; #include &lt;vector&gt; #include &quot;math.h&quot; #include...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru