Хочу разобраться с реализацией алгоритма Эйлерова цикла

← →
Виталий (2010-06-05 11:47) [0]

Здравствуйте. Я хочу самостоятельно написать алгоритм обхода Эйлерова пути. Но не могу понять, как реализовать алгоритм: в википедии (http://ru.wikipedia.org/wiki/Эйлеров_цикл) написано:

"procedure find_all_cycles (v)
var массив cycles
1. пока есть цикл, проходящий через v, находим его
добавляем все вершины найденного цикла в массив cycles (сохраняя порядок обхода)
удаляем цикл из графа
2. идем по элементам массива cycles
каждый элемент cycles[i] добавляем к ответу
из каждого элемента рекурсивно вызываем себя: find_all_cycles (cycles[i])"

Как понять, что есть цикл, и найти его? С чего следует начать, что прочесть?
И да, я не прошу готового кода. Я хочу понять, КАК что-то нужно реализовать.
Если кому-то в это субботнее утро будет несложно потратить свое время и пояснить мне принцип, я буду очень благодарен.

← →
oldman © (2010-06-05 12:14) [1]

> Как понять, что есть цикл, и найти его? С чего следует начать,
> что прочесть?

На той же странице википедии, что ты привел кликни по слову "цикл" в тексте

← →
Виталий (2010-06-05 12:14) [2]

Да, я прочел его понятие, но я имею ввиду, что мне неясно, как алгоритмически найти, есть ли цикл, проходящий через v.

← →
MBo © (2010-06-05 12:35) [3]

>как алгоритмически найти, есть ли цикл, проходящий через v
например, поиском в глубину

про эйлеров путь лучше тут почитать:
http://e-maxx.ru/algo/euler_path

← →
Виталий © (2010-06-05 12:44) [4]

Можете пояснить несколько моментов:

while (!deg[first]) ++first;
что делает этот цикл? Простите, с C++ понимаю не вполне ясно.

if (i == n) { res.push_back (v); st.pop(); }

как это соотносится с

> если степень(V) = 0, то
> добавляем V к ответу;
> снимаем V с вершины St;

Заранее спасибо.

← →
Виталий © (2010-06-05 12:57) [5]

Про первое, кажется, понял - ищет элемент, с которого стартовать, то есть находит первый элемент "степени", где степень не null?

← →
Виталий © (2010-06-05 16:04) [6]

Что же, наверное, никто не может мне помочь. Извините.

← →
Sha © (2010-06-05 21:03) [7]

Нет смысла теорию пересказывать своими словами.
Лучше сначала почитать и понять теорию,
а потом программировать абсолютно понятные вещи.

← →
Виталий © (2010-06-06 00:06) [8]

Я понял прочитаную теорию, но не понял моменты в реализации алгоритма. Может все-таки кто-то объяснить? Или это запретные знания?

← →
Sha © (2010-06-06 00:48) [9]

> Виталий © (06.06.10 00:06) [8]

Того что написано в ссылке [3] достаточно для самостоятельной реализации.
Начинай писать, на вопросы ответим.

> Я понял прочитаную теорию

Я не совсем уверен, что это так

> но не понял моменты в реализации алгоритма.

Зачем разбираться в чужой реализации алгоритма на незнакомом тебе языке?
Это не даст ничего нового. Ты же ты прочитал теорию и понял сам алгоритм.

> Может все-таки кто-то объяснить? Или это запретные знания?

Нет, конечно, не запретные.
Но до тех пор, пока имеются сомнения в том, что ты можешь словами
описать, что именно должно быть сделано, совершенно бессмыслено
разбираться в том, как это делают другие.

← →
Виталий © (2010-06-06 09:58) [10]

> Это не даст ничего нового. Ты же ты прочитал теорию и понял
> сам алгоритм.

Я просто подумал, что условие
> if (i == n) { res.push_back (v); st.pop(); }

я могу вполне себе понять, как оно выглядит в Delphi, и попросил это объяснить. Но, хорошо, начну писать сам.
Первый вопрос: как я понимаю, граф нужно задать матрицей смежности, состоящей из единиц и нулей, затем для каждой вершины подсчитать ее степень?

← →
Виталий © (2010-06-06 10:01) [11]

Или, возможно, мне надо прочесть совсем не те краткие выжимки, которые написаны в википедии или на сборнике алгоритмов?

← →
Sha © (2010-06-06 10:13) [12]

> Виталий © (06.06.10 09:58) [10]
> как я понимаю, граф нужно задать матрицей смежности,
> состоящей из единиц и нулей,
> затем для каждой вершины подсчитать ее степен

Да.

> Или, возможно, мне надо прочесть совсем не те краткие выжимки,

Достаточно разобраться в тексте по ссылке [3]

← →
Виталий © (2010-06-06 11:02) [13]

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

← →
Sha © (2010-06-06 11:27) [14]

Сначала надо решить, что он должен видеть: процесс или результат.
Если процесс, то мне, например, удобнее следить за стеком пройденных
вершин и списком смежных вершин или состоянием матрицы смежности.

Ну и потом, если сейчас будешь думать, как вставить рисование
в процедуру обхода, есть шанс ее вообще не написать.

← →
Виталий © (2010-06-06 11:31) [15]

Понял. И все-таки объясните мне, нет ли в том алгоритме какой-то неточности. Я вижу несоответствие: почему в словесном описании написано "если степень вершины равно 0", а в алгоритме вообще непонятно что?

← →
Sha © (2010-06-06 11:49) [16]

А говорил, понял прочитаную теорию [8] :)

Грубо, суть алгоритма:
- начинаем из особой вершины или из любой, если таких нет
- пока есть куда идти, идем куда глаза глядят,
сжигая за собой мосты и запоминая пройденные вершины
- если дальше дороги нет, выводим в результат все что запомнили
в обратном порядке до тех пор, пока не вспомним вершину,
из которой еще есть пути-дороги, или вспомнили все
- начиная с нее, повторяем все описанное выше

← →
Виталий © (2010-06-06 11:57) [17]

Значит, не в силах понять я прочитаную теорию, потому что то, что написали вы, никак не кореллирует с прочитаным мною текстом. То, как написали вы, теперь объясняет мне написаные тут строки:
int v = st.top(); int i; for (i=0; i<n; ++i) if (g[v][i]) break; if (i == n) { res.push_back (v); st.pop(); } else { --g[v][i]; --g[i][v]; st.push (i); }
Но я не смог понять, как это соотносится со степенью V. И сейчас не могу. Или вы не хотите мне объяснить этот момент, или он где-то написан черным по белому и я безнадежно туп.

← →
Sha © (2010-06-06 12:00) [18]

Не надо тут ничего понимать.
Это реализация алгоритма на другом языке.
Нафиг ее разбирать.

Словесное описание и есть алгоритм.
Требуется реализовать его на Делфи.
И все.

← →
Виталий © (2010-06-06 12:03) [19]

Господи, да хоть на BrainFucke он будет написан, суть остается ясна: алгоритм реализован ОТЛИЧНО от его словесного описания. Да, я вижу, что он оптимизирован: на текущем шаге не подсчитывается опять число ребер, исходящих из v: если ребро вершины еще не последнее, то его конец добавляется в список, а если последнее, то уже наконец его можно добавить в результат. Но все мои просьбы объяснить, почему сделано именно так, натыкаются почему-то на отказ.

← →
Sha © (2010-06-06 12:06) [20]

> как это соотносится со степенью V

Степень вершины в процессе работы алгоритма уменьшается,
если мы через нее проходим, т.к. мы вычеркиваем пройденные ребра.
Степень становиться нулевой, когда идти дальше некуда.
Тут мы и начинаем вспоминать, где были, что делали.

← →
Виталий © (2010-06-06 12:07) [21]

Да. То есть по-хорошему на каждом шаге цикла ее надо пересчитывать?

← →
Sha © (2010-06-06 12:09) [22]

Как хочешь.
Можешь пересчитывать, можешь хранить.

← →
MBo © (2010-06-06 12:10) [23]

Считаем, что граф проверен на эйлеричность.
В данном случае я задал граф, по виду напоминающий открытый конверт (степени вершин 2 и 4)

procedure TForm2.Button9Click(Sender: TObject); type TMatr = array[0..5, 0..5] of Byte; var Matr: TMatr; EPath: string; procedure InitMatrix; begin FillChar(Matr, SizeOf(Matr), 0); Matr[0, 1] := 1; Matr[1, 0] := 1; Matr[0, 3] := 1; Matr[3, 0] := 1; Matr[1, 2] := 1; Matr[2, 1] := 1; Matr[1, 4] := 1; Matr[4, 1] := 1; Matr[1, 5] := 1; Matr[5, 1] := 1; Matr[2, 4] := 1; Matr[4, 2] := 1; Matr[2, 5] := 1; Matr[5, 2] := 1; Matr[2, 3] := 1; Matr[3, 2] := 1; end; procedure EulerRec(Vertex: Integer); var i: integer; begin for i := 0 to 5 do if Matr[Vertex, i] <> 0 then begin Matr[Vertex, i] := 0; Matr[i, Vertex] := 0; EulerRec(i); end; EPath := EPath + IntToStr(Vertex) + "; "; end; begin EPath := ""; InitMatrix; EulerRec(0); Memo1.Lines.Add(EPath); end;

← →
Виталий © (2010-06-06 12:12) [24]

Ох и ответы)
Она уже сохранена в массиве, человек, реализовавший алгоритм на сайте, использовал этот массив для нескольких проверок. А тот участок, где собственно происходит вся работа, сделал совершенно иначе, чем написано. В этом и причина непонимания.

← →
Виталий © (2010-06-06 12:14) [25]

23, это как я понял, первая версия алгоритма, рекурсивная. Черт побери, а их еще назвали равными по длине кода.

← →
MBo © (2010-06-06 12:19) [26]

Теперь можно посмотреть на рекурсивную процедуру, и заметить, что строка EPath (содержащая последовательность вершин в Эйлеровом пути) по сути аналогична стеку, в который складываются посещенные вершины в порядке, а последовательность Vertex в рекурсивных вызовах - другому стеку (это можно отследить, добавив строку SPath := SPath + IntToStr(Vertex) + "; "; в начале рекурсивной процедуры). Так что если нужно преобразовать алгоритм в нерекурсивную форму, то фундамент для этого уже есть.

Путь:
0; 3; 2; 5; 1; 4; 2; 1; 0;

Последовательность посещения вершин алгоритмом (не путь!):
0; 1; 2; 3; 0; 4; 1; 5; 2;

← →
Sha © (2010-06-06 12:23) [27]

> их еще назвали равными по длине кода

Примерно так и есть.
Ведь когда ты будешь проверять существование пути,
ты все равно вычислишь степени вершин.

← →
Виталий © (2010-06-06 12:24) [28]

Остался, наверное, еще важный вопрос: я опять не понимаю, почему так реализовано удаление вершин "ненужного" ребра из результата:

for (size_t i=0; i+1<res.size(); ++i) if (res[i] == v1 && res[i+1] == v2 || res[i] == v2 && res[i+1] == v1) { vector<int> res2; for (size_t j=i+1; j<res.size(); ++j) res2.push_back (res[j]); for (size_t j=1; j<=i; ++j) res2.push_back (res[j]); res = res2; break; }

Если в результате есть вершина v1 и v2, то мы вначале начнем с места, где вершина V1 или V2 и дойдем до конца результата, складывая это во временый массив, а потом с начала результата до места, где V1 или V2, также добавляя это во врем. массив, который затем присвоим результирующему. Вопрос: так ведь все равно добавятся обе этих вершины?

27, да, но вот эта реализация внутри цикла все равно поставила меня в тупик, если бы не ваше объяснение алгоритма, а с рекурсией все как-то намного яснее.

> Виталий © (06.06.10 12:26) [29]
> с рекурсией все как-то намного яснее

Если как следует разобраться в алгоритме, то можно обойтись и без рекурсии и без стека.

Правда, об этом не пишут в книжках, чтобы учеба медом не казалась :)

Не подскажете, куда копать?

Простейший вариант - аналог стека с использованием динамического массива
размером = количество ребер + 1. Изменяешь текущую позицию и заносишь туда данные или считываешь.

Например так:
unit EulerPathForm; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids; type TForm1 = class(TForm) bRecursive: TButton; bStack: TButton; Memo1: TMemo; StringGrid1: TStringGrid; procedure bFindPathClick(Sender: TObject); private public end; var Form1: TForm1; implementation {$R *.dfm} uses SymmetricMatrix; var Matrix: TSymmetricMatrix; Total: integer; procedure InitMatrix; begin; SymmetricMatrixReallocate(Matrix, 7); SymmetricMatrixSetElement(Matrix, 0, 1, 1); // SymmetricMatrixSetElement(Matrix, 0, 2, 1); //закомментировать, чтобы путь существовал SymmetricMatrixSetElement(Matrix, 0, 3, 1); SymmetricMatrixSetElement(Matrix, 1, 2, 1); SymmetricMatrixSetElement(Matrix, 1, 4, 1); SymmetricMatrixSetElement(Matrix, 1, 5, 1); SymmetricMatrixSetElement(Matrix, 2, 3, 1); SymmetricMatrixSetElement(Matrix, 2, 4, 1); SymmetricMatrixSetElement(Matrix, 2, 5, 1); // SymmetricMatrixSetElement(Matrix, 3, 5, 1); //снять комментарий, чтобы путь был замкнут SymmetricMatrixSetElement(Matrix, 3, 6, 1); SymmetricMatrixSetElement(Matrix, 5, 6, 1); end; function GetStartPos: integer; var i, j, Count, OddCount, ZeroCount: integer; begin; Result:=0; OddCount:=0; ZeroCount:=0; Total:=0; if Length(Matrix.Values)>0 then begin; for i:=0 to Matrix.Size-1 do begin; Count:=0; for j:=0 to Matrix.Size-1 do if SymmetricMatrixGetElement(Matrix,i,j)<>0 then inc(Count); inc(Total,Count); if Count=0 then inc(ZeroCount); if odd(Count) then begin; inc(OddCount); Result:=i; end; end; end; Total:=Total shr 1; if (Total=0) or (ZeroCount>0) or (OddCount<>0) and (OddCount<>2) then Result:=-1; end; procedure EulerPathRecursive(StartPos: integer; var EPath: string); var i: integer; begin; for i:=0 to Matrix.Size-1 do if SymmetricMatrixGetElement(Matrix,StartPos,i)<>0 then begin; SymmetricMatrixSetElement(Matrix,StartPos,i,0); Dec(Total); EulerPathRecursive(i, EPath); end; EPath:=EPath + IntToStr(StartPos) + "; "; end; procedure EulerPathStack(StartPos: integer; var EPath: string); var LastCol: array of integer; Stack: array of integer; Current, i, j: integer; begin; SetLength(LastCol, Matrix.Size); for i:=0 to Matrix.Size-1 do LastCol[i]:=Matrix.Size-1; SetLength(Stack, Total + 1); Current:=-1; inc(Current); Stack[Current]:=StartPos; while true do begin; i:=Stack[Current]; j:=LastCol[i]; while (j>=0) and (SymmetricMatrixGetElement(Matrix,i,j)=0) do dec(j); if j>=0 then begin; LastCol[i]:=j-1; inc(Current); Stack[Current]:=j; SymmetricMatrixSetElement(Matrix,i,j,0); dec(Total); end else begin; dec(Current); EPath:=EPath + IntToStr(i) + "; "; if Current<0 then break; end; end; end; procedure TForm1.bFindPathClick(Sender: TObject); var Comment, EPath: string; i, j: integer; begin; InitMatrix; if Length(Matrix.Values)>0 then begin; StringGrid1.DefaultColWidth:=24; StringGrid1.DefaultRowHeight:=18; StringGrid1.ColCount:=Matrix.Size+1; StringGrid1.RowCount:=Matrix.Size+1; StringGrid1.Cols[0].Clear; for j:=1 to Matrix.Size do StringGrid1.Cells[0,j]:=IntToStr(j-1); for i:=1 to Matrix.Size do begin; StringGrid1.Cols[i].Clear; StringGrid1.Cells[i,0]:=IntToStr(i-1); for j:=1 to Matrix.Size do StringGrid1.Cells[i,j]:=IntToStr(SymmetricMatrixGetElement(Matrix,i-1,j-1)); end; end; i:=GetStartPos; if i<0 then Comment:="Путь не существует" else begin; if Sender=bRecursive then EulerPathRecursive(i, EPath); if Sender=bStack then EulerPathStack(i, EPath); if Total<>0 then Comment:="Граф не связен" else if i=0 then Comment:="Найденный путь замкнут" else Comment:="Найденный путь не замкнут"; end; Memo1.Lines.Add(Comment); Memo1.Lines.Add(EPath); end; end. //Используется в EulerPath unit SymmetricMatrix; interface type //Симметричная матрица размерами[0..Size-1, 0..Size-1] //Кроме экономии памяти почти в 2 раза автоматически поддерживает //равенство элементов, симметричных относительно главной диагонали. TSymmetricMatrix= record Size: integer; Values: array of integer; end; procedure SymmetricMatrixReallocate(var Matrix: TSymmetricMatrix; Size: integer; Value: integer= 0; Dirty: boolean= false); function SymmetricMatrixGetElement(var Matrix: TSymmetricMatrix; i, j: integer): integer; procedure SymmetricMatrixSetElement(var Matrix: TSymmetricMatrix; i, j: integer; Value: integer); implementation procedure SymmetricMatrixReallocate(var Matrix: TSymmetricMatrix; Size: integer; Value: integer= 0; Dirty: boolean= false); var i, len: integer; begin; len:=Size*(Size+1) shr 1; SetLength(Matrix.Values, len); Matrix.Size:=Size; if not Dirty then for i:=0 to len-1 do Matrix.Values[i]:=Value; end; function SymmetricMatrixGetElement(var Matrix: TSymmetricMatrix; i, j: integer): integer; begin; if i>=j then i:=(i*(i+1) shr 1)+j else i:=(j*(j+1) shr 1)+i; Result:=Matrix.Values[i]; end; procedure SymmetricMatrixSetElement(var Matrix: TSymmetricMatrix; i, j: integer; Value: integer); begin; if i>=j then i:=(i*(i+1) shr 1)+j else i:=(j*(j+1) shr 1)+i; Matrix.Values[i]:=Value; end; end.

Мне показалось, или тут неоправданое усложнение и таки есть рекурсия? ;) За код спасибо, буду разбираться.
Но можно вернуться к изначальному нерекурсивному варианту? Скажите, вот если при каждом шаге цикла, пока стек не пуст, считать для вершины степень - это как я понимаю неоптимально? Правильнее делать так, как реализовано на C++?

> Виталий © (06.06.10 22:16) [34]
>Мне показалось, или тут неоправданое усложнение и таки есть рекурсия?

Тут 2 процедуры (с рекурсией и без).

> если при каждом шаге цикла, считать для вершины степень - это как я понимаю неоптимально?

Надо сначала понять нужна ли тебе степень в действительности и для чего.
Вот, допустим, ты ее узнал. Скажем она равна 2. Что мы делаем дальше?
Находим очередное ребро для перехода к следующей вершине. Что нам дало наше знание?
Мы и без него можем искать следующее ребро. Если найдем, хорошо, идем дальше.
Если нет, то понятно, что степень равна нулю.
Получается, что степень использована в описании алгоритма только для большей ясности.
Гораздо важнее помнить не степень вершины, а последнее просмотренное нами ребро.

> последнее просмотренное нами ребро.

таки последнее просмотреное ребро а не вершину?

> Виталий © (07.06.10 01:33) [36]
> таки последнее просмотреное ребро а не вершину?

Вершину тоже, разумеется - это ведь переменная цикла.

А для каждой вершины хорошо бы знать,
с какого ребра начинать перебор,
чтобы не проверять каждый раз все ребра.

Посмотри, как это сделано в процедуре EulerPathStack
при помощи массива LastCol.

Если со стеком еще не разобрался, то вот простой код.
Не используется оптимизация, как у Sha

> для каждой вершины хорошо бы знать,
> с какого ребра начинать перебор,
> чтобы не проверять каждый раз все ребра.

function EulerStackPath: string; var i, V: integer; VStack: TStack; Isolated: Boolean; begin Result := ""; VStack := TStack.Create; VStack.Push(Pointer(0)); while VStack.Count > 0 do begin V := Integer(VStack.Peek); Isolated := True; for i := 0 to 5 do if Matr[V, i] <> 0 then begin Matr[V, i] := 0; Matr[i, V] := 0; VStack.Push(Pointer(i)); Isolated := False; Break; end; if Isolated then Result := Result + IntToStr(Integer(VStack.Pop)) + "; "; end; end;

хе, в конце при правке потерял
VStack.Free;

38, если я правильно понимаю, ваш вариант как раз в точности соответствуте словесному описанию, данному в сборнике алгоритмов?

Хочу разобраться с реализацией алгоритма Эйлерова цикла Найти похожие ветки