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

← →
Виталий (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, также добавляя это во врем. массив, который затем присвоим результирующему. Вопрос: так ведь все равно добавятся обе этих вершины?

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

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

← →
Sha © (2010-06-06 15:04) [30]

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

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

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

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

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

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

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

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

Например так:
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.

← →
Виталий © (2010-06-06 22:16) [34]

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

← →
Sha © (2010-06-06 22:32) [35]

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

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

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

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

← →
Виталий © (2010-06-07 01:33) [36]

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

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

← →
Sha © (2010-06-07 07:39) [37]

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

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

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

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

← →
MBo © (2010-06-07 08:04) [38]

Если со стеком еще не разобрался, то вот простой код.
Не используется оптимизация, как у 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;

← →
MBo © (2010-06-07 08:06) [39]

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

← →
Виталий © (2010-06-07 19:28) [40]

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

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

Кстати, по поводу добавленного ребра: его вершины должны оставаться в результате?

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

В результат заносятся вершины, ставшие изолированными в процессе кромсания графа. Вершины со степенью более 2 присутствуют в результате несколько раз.

Это-то понятно. Но не совсем ясно с "фиктивным" ребром: оно должно быть удалено из ответа, так? А почему тогда вершины, его образующие, в ответе в сборнике алгоритмов остаются?

Эти вершины (нечетной степени) будут начальной и конечной вершиной в пути.

> Виталий © (14.06.10 10:46) [43]
> Но не совсем ясно с "фиктивным" ребром: оно должно быть удалено из ответа, так?

А зачем оно тебе нужно, это фиктивное ребро?

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

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

Не проще ли сразу начать движение с одной из особых вершин?

Sha, я просто ориентировался на написаное в сборнике алгоритмов - мол, при наличии двух вершин нечетной степени (а мы и делаем их поиск при анализе графа) нужно добавить фиктивное ребро, а зтем удалить его из результата.
А вы предлагаете не искать вторую вершину, а начать обход графа с первой найденой вершины нечетной степени?

> Виталий © (15.06.10 10:32) [46]
> А вы предлагаете не искать вторую вершину, а начать обход графа с первой найденой вершины нечетной степени?

Так можно делать, если ты точно знаешь, что путь существует.

В [33] я предлагаю сначала проверить "эйлеричность" графа при помощи GetStartPos,
затем при помощи рекурсивной (EulerPathRecursive) или стековой (EulerPathStack)
функции найти сам путь и, наконец, при помощи bFindPathClick,
которая собственно и вызывала перечисленные функции,
отобразить результаты и исходный граф.

Можете объяснить, как работают процедуры GetStartPos и EulerPathStack?

Кокретно, в первой неясна сдвиговая операция. Во второй - операции с последней колонкой и Current.

> Можете объяснить, как работают процедуры GetStartPos и EulerPathStack?

GetStartPos считает степени вершин, и возвращает
номер вершины с которой начинается путь (если он существует)
или -1 (если путь не существует).

Проверка существования пути простая (связность графа не проверяется):
число ребер > 0,
число изолированных вершин = 0,
число вершин нечетной степени = 0 или 2.

В качестве начальной вершины возвращается:
0 - при отсутствии вершин нечетной степени,
вершина с большим номером в противном случае.

> в первой неясна сдвиговая операция

При подсчете ребер мы каждое ребро считаем дважды,
т.к. перебираем все вершины, поэтому надо делить на 2 или сдвигать на 1.

> Во второй - операции с последней колонкой и Current.

EulerPathStack эмулирует работу со стеком при помощи динамического массива Stack и целого Current, кот. задает текущее положение в стеке.
Длина массива устанавливается в самом начале, т.к. мы знаем число ребер
после работы GetStartPos.

Каждый раз когда мы при обходе графа попадаем в i-тую вершину, мы ищем
очередное ребро в i-той строке, начиная с последней непросмотренной
колонки до нулевой (массив LastCol хранит номер последней колонки для каждой строки).

> вершина с большим номером в противном случае.

Здесь подразумевается:
вершина нечетной степени с большим номером в противном случае.

Эта маленькая хитрость позволяет определить замкнутость пути,
найденного EulerPathStack, даже не глядя на ее результат.

Еще одна хитрость состоит в том, что мы в GetStartPos
проверили, что граф не содержит изолированных вершин,
и подсчитали общее число ребер.

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

Можно немного пройтись еще раз вот по этому моменту:

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;

вот что делается при уменьшении Current? Значит, для данной вершины уже нет ребер?

i:=Stack[Current]; //переходим в очередную вешину, ее номер берем из стека, сам стек не меняем j:=LastCol[i]; //вершина - первый кандидат на переход из текущей вершины while (j>=0) and (SymmetricMatrixGetElement(Matrix,i,j)=0) do dec(j); //пропускаем кандидатов, в которые переход невозможен if j>=0 then begin; //нашли вешину j, в которую переход возможен LastCol[i]:=j-1; //запомним следующего возможного кандидата на переход из вершины i inc(Current); Stack[Current]:=j; //помещаем j стек, эта вершина будет следующей текущей SymmetricMatrixSetElement(Matrix,i,j,0); //удаляем ребро, использованное при переходе i->j dec(Total); //уменьшаем количество ребер, оставшихся в графе end else begin; //нет вершин, в которые возможен переход из текущей вершины i dec(Current); //удаляем ее из стека, после этого текущей станет предыдущая посещенная EPath:=EPath + IntToStr(i) + "; "; //заносим вершину в формируемый путь if Current<0 then break; //если стек исчерпан весь путь пройден.

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

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

Извините, что встреваю - вот ради таких Учеников, как Вы, Виталий, кому-то еще хочется быть Учителем.
Не останавливайтесь, учитесь..
Здесь есть кому подсказать, хотя бы на примере этой ветки.

Для поверхностного изучения теории графов мне лекций хватило :)
Думаю, задача о мостах Эйлера должна быть в первой главе любой книги.
Книгу для самостоятельного изучения, где последовательно и доходчиво изложена теория, рекомендовать затрудняюсь.
Мне больше интересна прикладная сторона, а это часто не в книгах, а в отдельных статьях.

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

> колледж, увы, не дал сколько-нибудь углубленых материалов
> по этим вопросам.

Ох уж это красивое заграничное слово колледж. Да кто ж туда пойдёт преподавать?

Увы, теперь я и сам в этом убедился.

отпиши если это поможет.

http://delphiforfun.org/programs/Download/ShortestPathSource.zip
http://delphiforfun.org/programs/Math_Topics/ShortestPath.htm

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