Алгоритм Хирхольцера: как построить сам эйлеров цикл, а не только проверить?
Проверять существование эйлерова цикла я научился. Но теперь надо вывести сам цикл — последовательность вершин. Наивный DFS с удалением рёбер даёт неправильный порядок. Слышал про алгоритм Хирхольцера — как он строит маршрут и почему наивная рекурсия ломается?
2 ответа
Почему наивно нельзя. Если просто рекурсивно идти и дописывать вершины в pre-order, можно «застрять»: уйти в тупик, не обойдя боковую петлю. Хирхольцер чинит это, добавляя вершину в ответ в момент, когда из неё больше некуда идти (post-order), и потом разворачивая.
Идея. Идём по неиспользованным рёбрам, пока можем (на стеке). Когда из текущей вершины рёбер не осталось — выгружаем её в ответ. Так «застрявшие» петли встраиваются в маршрут.
// ориентированный вариант; g[v] — список соседей, ptr[v] — указатель на след. неиспользованное
vector<int> hierholzer(int n, vector<int> g[], int start) {
vector<int> ptr(n, 0), st = {start}, path;
while (!st.empty()) {
int v = st.back();
if (ptr[v] < (int)g[v].size()) {
int u = g[v][ptr[v]++]; // используем ребро v->u
st.push_back(u);
} else {
path.push_back(v); // тупик: выгружаем
st.pop_back();
}
}
reverse(path.begin(), path.end());
return path; // длина = E+1
}
Сложность O(V+E) — каждое ребро используется ровно один раз (ключ: ptr[v] не сбрасывается, мы никогда не пересматриваем уже пройденные рёбра). Память O(V+E).
Для неориентированного графа: ребро надо помечать использованным с обеих сторон. Храним рёбра с id и флагом used[id]; при проходе по (u,id) проверяем !used[id], ставим used[id]=true. Иначе пройдёте каждое ребро дважды.
Критичная деталь именно про производительность: ptr[v] (текущий индекс по списку смежности) должен жить между заходами в v. Если на каждом заходе сканировать список заново в поисках неиспользованного ребра, получите O(E·deg) = TLE. Поэтому продвигаем ptr[v]++ и больше не возвращаемся к пройденным позициям — это и даёт линейность.
И итеративная версия (на явном стеке, как выше) предпочтительнее рекурсивной: эйлеров цикл может иметь длину E ~ 10^6, рекурсия словит stack overflow. Перед запуском не забудьте проверить условия существования (степени + связность) — Хирхольцер на «неэйлеровом» графе выдаст путь длины меньше E+1.