Главная | УРОКИ | Календарь | Правила | Новые сообщения | Поиск |
|
|
Опции темы | Опции просмотра |
|
21.05.2008, 23:21 | #1 |
Super Moderator
|
Помогите с алгоритмом
Возможно кто-нибудь сможет помочь с алгоритмом дискретной математики. Просьба тех, кто не знает что такое графы дальше не читать. )
Итак, нужен алгоритм(!) построения эйлерова цикла. НО! Чтобы алгоритм не портил граф. Есть самый известный способ (Липский, Иванов), но в нем присутствует удаление ребра при построении. Нужен соответственно алгоритм без удалений ) Представление графа - списком ребер. Хотя можно и матрицей смежности впринципе. ) Граф - связный, неориентированный. Последний раз редактировалось Sanyok, 21.05.2008 в 23:41. |
22.05.2008, 00:56 | #6 |
Guest
|
2 стэка - a,b
ЦИКЛ: { берём вершину x0, идём от неё по непройденному ранее ребру, записываем вершины в a. ЕСЛИ x последняя = a, ТО ЦИКЛ { перекладываем вершины из a в b ПОКА не наткнемся на x последнюю } ИНАЧЕ ЕСЛИ стэк а - пустой, ТО в стэке b лежит путь эйлерова цикла } Сань, проверь только выход из 2ого цикла.. а то тут на бесконечный смахивает.. либо не делай ПОКА(while, for), а чисто проверку и число операций.. |
22.05.2008, 01:47 | #7 | |||||||||||||||||||||||
Super Moderator
|
не очень понял, как это работает, если честно ) ЦИКЛ: { берём вершину x0, идём от неё по непройденному ранее ребру Ну как раз условие ЦИКЛа получается ПОКА ребёр > 0 "ЕСЛИ x последняя = a, ТО" что здесь есть "x последняя"? и имеется ввиду видимо top стека a?) |
|||||||||||||||||||||||
22.05.2008, 21:55 | #9 |
Guest
|
выбираем вершину x0
заносим эту вершину в стэк a пока a ≠ Ø { x = top(a) если есть непройденное ребро (x,y) то "проходим его" то есть просто помечаем y заносим в а иначе перемещаем x из а в b } когда а будет пустое, что в b будет лежать последовательность вершин эйлерова цикла |