| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > построение эйлерова цикла за линейное время |
| Автор: max07 9.5.2007, 16:35 |
| Добрый день, может есть у кого реализация такого алгоритма? Или ссылку можете дать какую полезную? Спасибо. |
| Автор: comp 9.5.2007, 17:49 |
| Ну блин... Идеш в глубину, вершину, в которую только что зашел, кладёш в стэк. Приэтом, удаляеш рёбра, по которым ходиш... Если из какой-то вершины некуда идти, помещаеш её во второй стэк, а из первого удаляеш... Ну и в итоге во втором стэке будут нужные те циклы... Схема примерно такая... массив C - кол-во инцедентных вершин у i-й вершины. e - наш граф. v - вершина, с которой начинать... ну, если в графе более 2х вершин, степень которых нечётная, то естественно, в таком графе циклов нет... если таких вершин - две, то надо начинать с любой из них... иначе - без разницы. stack <int > st1, st2 st1.push(v); for (; !st1.empty();) { v = st1.top() if (!c[v]) { st2.push(v); st1.pop(); continue; } it_v = e[v].begin(); c[v]--; c[*it_v]--; st1.push(*it_v); e[v].erase(it_v); } |
| Автор: esperant0 9.5.2007, 19:32 |
| Цикл можно построить за постоянное время. Берете две вершины соединяете двумя ребрами. Вот и эйлеров цикл готов |
| Автор: max07 9.5.2007, 19:37 |
| А как лучше хранить граф для этой задачи? |