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

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

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

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

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

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

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

← →
Виталий © (2010-06-14 10:46) [43]

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

← →
MBo © (2010-06-14 11:20) [44]

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

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

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

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

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

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

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

← →
Виталий © (2010-06-15 10:32) [46]

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

← →
Sha © (2010-06-15 10:45) [47]

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

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

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

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

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

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

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

← →
Sha © (2010-06-15 17:08) [50]

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

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

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

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

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

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

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

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

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

← →
Sha © (2010-06-15 19:48) [51]

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

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

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

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

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

← →
Виталий © (2010-06-16 15:37) [52]

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

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? Значит, для данной вершины уже нет ребер?

← →
Sha © (2010-06-16 17:12) [53]

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; //если стек исчерпан весь путь пройден.

← →
Виталий © (2010-06-16 20:37) [54]

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

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

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

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

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

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

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

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

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

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

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