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

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

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

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 17.12.2011, 18:14   #1
too lame
 
Аватар для too lame
 
Регистрация: 10.12.2011
Сообщений: 7
По умолчанию Нахождение Эйлерового цикла (Графы)

Нахождение Эйлерового цикла выполняется по алгоритму Флёри.
Допустим граф задаётся следующей матрицей смежности

Начало цикла пускай будет в вершине 1. Для наглядности граф :


Так вот при проходе мы выбираем любую вершину.Вот код нахождения
Код:
Function GetRandom (var WorkMatrix:SWorkMatrix;var row:integer):integer;
var j,i:integer; Vershini_s_1:array[0..9] of integer;
begin
 j:=0;
 randomize;
 for i:=1 to 10 do
  if WorkMatrix[i,row]=1 then
    begin
     Vershini_s_1[j]:=i;
     inc(j);
    end;
 if j=0 then result:=0 else
 result:=Vershini_s_1[random(j-1)];
end;
И собственно сам алгоритм :
Код:
tek_vershina:=start;
  buffer:=getrandom(WorkMatrix,tek_vershina);//получаем случайное ребро
  WorkMatrix[buffer,tek_vershina]:=0;
  WorkMatrix[tek_vershina,buffer]:=0; //удаляем пройденное ребро
  tek_vershina:=buffer;// изменяем текущую вершину
  cycle:=inttostr(start)+'->'+inttostr(tek_vershina); //формируем цикл
    while (getrandom(WorkMatrix,tek_vershina) <> 0)and(tek_vershina <> start) do
    begin
        buffer:=getrandom(WorkMatrix,tek_vershina);
        WorkMatrix[buffer,tek_vershina]:=0;
        WorkMatrix[tek_vershina,buffer]:=0;
        cycle:=cycle+'->'+inttostr(buffer);
        tek_vershina:=buffer;
    end;
Но при выполнении могут пройтись не все рёбра,т.к. выбирается случайная вершина .


ЗЫ Пока писал,вспомнил,что вершина выбирается случайно,но "мост" выбирается,если нет других вариантов.Подскажите,как модифицировать,что бы учитывалось это?

ЗЫЫ Могу скинуть всю программу того,что есть на данный момент.
Спасибо,я всё (не) понял.
too lame вне форума Ответить с цитированием
Старый 17.12.2011, 20:19   #2
too lame
 
Аватар для too lame
 
Регистрация: 10.12.2011
Сообщений: 7
По умолчанию

помогите пожалуйста
Спасибо,я всё (не) понял.
too lame вне форума Ответить с цитированием
Ответ


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



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Нахождение Эйлерового цикла(delphi) too lame Помощь студентам 1 16.12.2011 22:22
алгоритмы нахождения эйлерова цикла и гамильтонова цикла в графе. Necare Помощь студентам 0 15.11.2011 18:26
нахождение пути цикла dima92 Общие вопросы Delphi 2 22.05.2010 06:03
Переход от цикла к циклу не выходя из цикла (без multithreading) Qousio Общие вопросы C/C++ 2 16.05.2009 09:27
Нахождение эйлерова цикла, косяк vendigo Общие вопросы C/C++ 1 22.11.2007 14:14