Помогите с алгоритмом
Возможно кто-нибудь сможет помочь с алгоритмом дискретной математики. Просьба тех, кто не знает что такое графы дальше не читать. )
Итак, нужен алгоритм(!) построения эйлерова цикла. НО! Чтобы алгоритм не портил граф. Есть самый известный способ (Липский, Иванов), но в нем присутствует удаление ребра при построении. Нужен соответственно алгоритм без удалений ) Представление графа - списком ребер. Хотя можно и матрицей смежности впринципе. ) Граф - связный, неориентированный. |
Ты программу чтоле создаёшь или для себя алгорит выбираешь?
|
Цитата:
|
Как я вас понимаю :)
Я подумаю, если что придумаю, то отпишу... |
тож посижу..
с графами знаком, выступал на конкурсе по ним. с++ в вижуале ноу проблэм сэр. |
2 стэка - a,b
ЦИКЛ: { берём вершину x0, идём от неё по непройденному ранее ребру, записываем вершины в a. ЕСЛИ x последняя = a, ТО ЦИКЛ { перекладываем вершины из a в b ПОКА не наткнемся на x последнюю } ИНАЧЕ ЕСЛИ стэк а - пустой, ТО в стэке b лежит путь эйлерова цикла } Сань, проверь только выход из 2ого цикла.. а то тут на бесконечный смахивает.. либо не делай ПОКА(while, for), а чисто проверку и число операций.. |
Цитата:
ЦИКЛ: { берём вершину x0, идём от неё по непройденному ранее ребру Ну как раз условие ЦИКЛа получается ПОКА ребёр > 0 "ЕСЛИ x последняя = a, ТО" что здесь есть "x последняя"? и имеется ввиду видимо top стека a?) |
Могу написать алгоритм на бэйсике:fu:
|
выбираем вершину x0
заносим эту вершину в стэк a пока a ≠ Ø { x = top(a) если есть непройденное ребро (x,y) то "проходим его" то есть просто помечаем y заносим в а иначе перемещаем x из а в b } когда а будет пустое, что в b будет лежать последовательность вершин эйлерова цикла |
ну вы уманы
|
Часовой пояс GMT +5, время: 06:52. |
vBulletin® 3.7.1, Copyright ©2000-2024, Jelsoft Enterprises Ltd.
Перевод: RSN-TeaM (zCarot)