Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.05.2016, 19:13   #1
Voltr
Новичок
Джуниор
 
Регистрация: 10.05.2016
Сообщений: 1
По умолчанию Гамильтоновы пути

Язык Delphi7. Задача такова, что надо найти и вывести все гамильтоновы пути в заданном неориентированном графе(задается матрицей смежности). Написал функцию(код которой расположен ниже), но она выводит только 1 путь. Я понимаю как это должно делаться на словах/бумаге, но как это реализовать в коде не могу понять. Собственно вопрос. Можно ли как-то модернизировать эту функцию либо может как-то по другому реализовать кнопку(ниже функции) чтобы оно выводило все гамильтоновы пути?
Код:
//A - матрица смежности
//Mark - буленовский массив (false - точка посещена, true - не посещена)
//v - 1 точка
//w - последняя точка
//d - длинна графа (кол-во точек)
function TForm1.HamiltonPath (v, w, d:integer): boolean;
var i:integer;
begin
Result:=False;
  if (v = w) and (d = 1) then
  begin
  Result:=true;
  Label3.Caption:=Label3.Caption+inttostr(w);
  exit;
  end
  else
    begin
    Mark[v]:=false;
    for i:=1 to N do
    if (A[v,i]=1)  and (Mark[i]=true) then
      if HamiltonPath(i,w,d-1) then
        begin
        Result:=true;
        q[i]:=v;
        Label3.Caption:=inttostr(q[i])+'-'+Label3.Caption;
        exit;
        end
      else
        begin
        Result:=false;
        end;
    Mark[v]:=true;
    end;

end;
Код:
procedure TForm1.Button3Click(Sender: TObject);
  var i:Byte;
begin
  stop:=false;
  SetLength(q,n-1);
  for i:=0 to n-1 do q[i]:=0;
  Label3.Caption:='';
  for i:=1 to N do Mark[i]:=true;
  stop:=HamiltonPath(StrToInt(Edit1.Text),StrToInt(Edit2.Text),N);
  if stop=false then Label3.Caption:='Puti net'
end;

Последний раз редактировалось Voltr; 10.05.2016 в 19:28. Причина: Забыл указать среду
Voltr вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
написать программу для нахождения самого короткого пути от кординаты X1 Y1 до X2 Y2 если на пути встречается яма радиусом R AlbinaM Паскаль, Turbo Pascal, PascalABC.NET 5 27.11.2013 20:02
Динамические пути Neksion Помощь студентам 13 05.06.2013 19:52
C# Волновой алгоритм поиска пути в лабиринте. Построение пути Wanz Помощь студентам 1 17.03.2013 14:04
поиск пути NiCola999 Общие вопросы C/C++ 19 16.11.2009 09:25
Пути к данным Лубышев Общие вопросы Delphi 3 21.01.2008 18:56