Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Нахождение ВСЕХ эйлеровых циклов в графе (pascal)

Автор: Panourgue 27.12.2006, 10:33

Здраствуйте!
Алгоритм для нахождения ВСЕХ эйлеровых циклов и цепей (т.е. незамкнутых; это если есть нечетные вершины) в ор- и неорграфах (Delphi / Pascal)
Умоляю, помогите!

Автор: SoWa 27.12.2006, 15:43

Во первых поиск, во вторых перебор.

Автор: Panourgue 27.12.2006, 16:28

2SoWa:, А нельзя ли поподробнее? smile

Что значит перебор?

----------------
Просто я к программированию и алгоритмам имею не совсем непосредственное отношение...

Автор: SoWa 27.12.2006, 17:14

ООоо!
Перебор- это перебор. Когда берешь комбинацию, проверяешь её на условие, и так для каждой возможной комбинации...
А во первых- используй поиск по форуму smile

Автор: IvanoffAndrey 31.12.2006, 13:21

Я бы искал эйлеровы циклы согласно теореме:
Граф содержит Эйлеров цикл тогда и тоглько тогда когда все его вершины имеют четную степень. Это значит,
1. что нужно удостовериться в четности всех степеней вершин.
2. Найти один цикл согласно алгоритма Флери
3. сгенерировать всевозможные переставки данного цикла.
Вроде так.
Если тебя все еще интерисует этот вопрос отвечу подробнее.

Цитата

во вторых перебор.

Не стоит делать перебор, существуют абсолютно полные алгоритмы например алгоритм Флери, если надо опишу его.

Автор: VaiMR 16.1.2007, 01:39

Вот например так (правда си++):

Код


//================ проверка связности =====================

//-----Проверка наличия вершин помеченных 2 маркером-------
char kolv2(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]==2)
    return 't';
  return 'f';
 }
//---------------------------------------------------------

char svaz(int kolv,int *gr[])
{
 int mbuf[maxkolv];

 for (int i=0;i<kolv;i++)
  mbuf[i]=1;

 mbuf[1]=2;
 while (kolv2(kolv,mbuf)=='t')
  for (i=0;i<kolv;i++)
   if (mbuf[i]==2)
    {
     mbuf[i]=3;
      for (int j=0;j<kolv;j++)
       if ((gr[i][j]==1)&&(mbuf[j]==1))
    mbuf[j]=2;
    };
 for (i=0;i<kolv;i++)
  if (mbuf[i]==1)
   return 'f';
 return 't';
}
//=========================================================

//================ поиск эйлерова пути ====================

//-----Проверка наличия ненулевых вершин ------------------
char kolvn0(int kolv,int mbuf[])
 {
  for (int i=0;i<kolv;i++)
   if (mbuf[i]>0)
    return 't';
  return 'f';
 }
//---------------------------------------------------------

void euler(int kolv,int *gr[])
{
 int v,u,i,x,i1=0,i2=0;
 int st1[maxkolv];
 int st2[maxkolv];

 for(i=0;i<kolv;i++) st1[i]=0, st2[i]=0;
 do
  cout<<"введите номер стартовой вершины: ",cin>>v; // ЗДЕСЬ В ЦИКЛЕ ПЕРЕБИРАЕМ ВСЕ ВЕРШИНЫ!!!
 while (v>kolv);

 st1[i1]=v;
 while (kolvn0(kolv,st1)=='t')
  {
   v=st1[i1];
   i=0;
   while ((i<kolv)&&(gr[v-1][i]==0))
    i++;
   if (i<kolv)
    {
     u=i;
     i1++;
     st1[i1]=u+1;
     gr[v-1][u  ]=0;
     gr[u  ][v-1]=0;
    }
   else
    {
     st2[i2]=st1[i1];
     st1[i1]=0      ;
     i1--;
     i2++;
    }
  };
 cout<<"эйлеров цикл: ";
 for(i=0;i<kolv-1;i++) cout<<st2[i]<<" -> ";
 cout<<st2[kolv-1];
 cout<<" -> "<<v;
}

А вот проверка связности на Паскале:

Код



const kolvmax=10;

type mass=array[1..kolvmax,1..kolvmax] of byte;
     mversh=array[1..kolvmax] of byte;

{Проверка графа на связность}

function svaz(var mbuf:mversh;const m:mass;kolv,n:byte):boolean;
var i,j:byte;

{Проверка наличия вершин помеченных 2 маркером}

 function kolv2(const mbuf:mversh;kolv:byte):boolean;
  var i:byte;
  begin
   for i:=1 to kolv do
    if mbuf[i]=2
     then
      begin
       kolv2:=true;
       exit;
      end;
  kolv2:=false;
  end;

{////////////////////////////////////////////////}

begin
 for i:=1 to kolv do
  mbuf[i]:=1;
 mbuf[n]:=2;
 while kolv2(mbuf,kolv) do
  begin
   for i:=1 to kolv do
    if mbuf[i]=2
     then
      begin
       mbuf[i]:=3;
        for j:=1 to kolv do
          if (m[i,j]=1)and(mbuf[j]=1)
           then
            mbuf[j]:=2;
      end;
   end;
 for i:=1 to kolv do
  if mbuf[i]=1
   then
    begin
     svaz:=false;
     exit;
    end;
 svaz:=true;
end;

{////////////////////////////////////////////////////}

На Паскале нет Эйлеровых циклов, так как когда писал не нужно было.

Автор: VaiMR 16.1.2007, 08:40

Оказывается есть реализация на Паскале в моей копилке:

Код


Program Euler;
const n=9;
      m: array[1..n, 1..n] of boolean=
      (
      (False, True,  True,  False, False, False, False, False, False),
      (True,  False, True,  False, False, False, True,  True,  False),
      (True,  True,  False, True,  True,  False, False, False, False),
      (False, False, True,  False, True,  False, False, False, False),
      (False, False, True,  True,  False, True,  False, True,  False),
      (False, False, False, False, True,  False, True,  True,  True ),
      (False, True,  False, False, False, True,  False, True,  True ),
      (False, True,  False, False, True,  True,  True,  False, False),
      (False, False, False, False, False, True,  True,  False, False)
      );
Type
    list=^node;
    node=record
             i: integer;
          next: list
         end;
Var stack1, stack2: list;
        v, u, x, i: integer;

 Procedure Push(x: integer; var stack: list);
 Var temp: list;
 Begin
   New(temp);
   temp^.i:=x;
   temp^.next:=stack;
   stack:=temp
 End;

 Procedure Pop(var x: integer; var stack: list);
 Begin
   x:=stack^.i;
   stack:=stack^.next
 End;

 Function Peek(stack: list): integer;
 Begin
   Peek:=stack^.i
 End;

 Procedure PrintList(l: list);
 Begin
   Writeln;
   If l=nil then writeln('NIL');
   While l<>nil do
   Begin
     Write(l^.i:3);
     l:=l^.next
   End
 End;

Begin
  stack1:=nil;
  stack2:=nil;
  Write('Начальная вершина: ');readln(v);
  Push(v, stack1);
  While stack1<>NIL do
  Begin
    v:=peek(stack1);
    i:=1;
    While (i<=n) and not m[v, i] do inc(i);
    If i<=n then
            Begin
              u:=i;
              Push(u, stack1);
              m[v, u]:=False;
              m[u, v]:=False;
            End
            else
            Begin
              pop(x, stack1);
              push(x, stack2)
            End
  End;
  PrintList(stack2)
End.

Этот код писал не сам (взял из учебника) smile

Автор: esperant0 16.1.2007, 09:37

Цитата(IvanoffAndrey @ 31.12.2006, 13:21)

Не стоит делать перебор, существуют абсолютно полные алгоритмы например алгоритм Флери, если надо опишу его.

Почему не стоит, задача класса PSPACE разве нет:?

Автор: xZero 27.11.2008, 22:55

Код


private void FindCircle(Int32 v) {
            for (Int32 i = 0; i < n; i++) {
                     if (newg[v, i] > 0) {
                        newg[v, i]--;
                        newg[i, v]--;
                        FindCircle(i);               
                    } 
            }
            result.Add(v);
       
 } 
// newg - матрица смежности
// n - число вершин

таким рекурсивным алгоритмом можно найти один эйлеров цикл.
А как найти все эйлеровы циклы в графе?

например если v = 1;
находим вершины, смежные v. Пусть это вершины 3,5,6. Если в FindCircle(i) ставить вершины в
той последовательности, то получим один цикл, если в последовательности, например 5,3,6, то получим уже другой цикл.
Таким образом нужно модифицировать как-то этот рекурсивный алгоритм для нахождения всех циклов. Кто-нибудь может подсказать как это реализовать, потому что я пока что не смог придумать...