Изменения

Перейти к: навигация, поиск

Алгоритм построения Эйлерова цикла

356 байт добавлено, 20:31, 10 января 2015
м
Нет описания правки
== Время работы ==
Если реализовать поиск ребер инцидентных вершине и удаление ребер за <tex>O(1)</tex> (для этого для каждого ребра достаточно добавить свойство deleted типа boolean), то алгоритм будет работать за <tex>O(E)</tex>.<br>Чтобы реализовать поиск за <tex>O(1)</tex>, для хранения графа следует использовать списки смежных вершин. Тогда удаление ребер будет выглядеть следующим образом:<font size=2> '''function''' remove(v : Vertex, index : '''int'''): graph[v][index] = graph[v].back() graph[v].pop()</font>
== См. также ==
17
правок

Навигация