Эйлеров путь (алгоритм Хирхольцера)

Эйлеров путь (алгоритм Хирхольцера): как это работает?

Сначала проверьте степени вершин. Для ненаправленного пути нечётную степень могут иметь не больше двух вершин.

В ориентированном графе лишнее исходящее ребро может быть только у одной вершины. Она и обязана быть началом.

Идите вперёд жадно и удаляйте каждое использованное ребро. По использованному ребру больше не ходят.

Когда у вершины не осталось рёбер, положите её в выходной стек. Она застряла, значит её место ближе к концу.

Вернитесь в предыдущую вершину и продолжайте. Неиспользованные рёбра там всё ещё доступны.

В самом конце разверните выходной стек. Это ставит путь в правильном порядке.

1. в JFK, рёбра в A и в BБерём A первым, если нужен наименьший маршрут.
2. в A, потом обратно в JFKЕдинственное ребро из A возвращает в JFK.
3. в B: рёбер не осталосьB застряла, поэтому кладётся первой.
4. кладём JFK, A, JFKКаждая вершина кладётся, когда исчерпала рёбра.
5. развернули: JFK, A, JFK, BЧтение стека с конца даёт маршрут.

function eulerianPath(tickets, start) {
    const adj = {};
    for (const [from, to] of tickets) {
        (adj[from] ||= []).push(to);
    }
    for (const from in adj) adj[from].sort().reverse(); // pop smallest first
    const route = [];
    const stack = [start];
    while (stack.length) {
        const node = stack[stack.length - 1];
        if (adj[node] && adj[node].length) {
            stack.push(adj[node].pop());
        } else {
            route.push(stack.pop()); // dead end: record and back up
        }
    }
    return route.reverse();
}

Эйлеров путь (алгоритм Хирхольцера): разбор примера

Восстановить маршрут перелётов

Дан список авиабилетов, каждый надо использовать ровно один раз, начиная с JFK.

Если маршрутов несколько, верните наименьший по алфавиту.

Отсортируйте пункты назначения каждого аэропорта, чтобы первым брался наименьший.

Идите жадно и кладите аэропорт в стек, когда билетов не осталось. В конце разверните стек.

function findItinerary(tickets) {
    const graph = new Map();
    for (const [from, to] of tickets) {
        if (!graph.has(from)) graph.set(from, []);
        graph.get(from).push(to);
    }
    // reversed, so pop() hands back the smallest destination
    for (const list of graph.values()) list.sort().reverse();

    const route = [];
    const stack = ["JFK"];

    while (stack.length) {
        const airport = stack[stack.length - 1];
        const next = graph.get(airport);

        if (next && next.length) {
            stack.push(next.pop()); // the ticket is used up
        } else {
            route.push(stack.pop()); // stuck, so this airport ends the route
        }
    }

    return route.reverse();
}

Эйлеров путь (алгоритм Хирхольцера): когда применять?

Эти формулировки в условии ведут сюда:

• •использовать каждое ребро ровно один раз
• •восстановить маршрут по билетам
• •рисунок одним росчерком / не отрывая ручку
• •пройти каждую дорогу/домино ровно один раз
• •рейсы или домино должны соединиться в одну поездку

Эйлеров путь (алгоритм Хирхольцера): с чем путают?

• Обход графа BFS / DFS (Graph BFS / DFS): Обходу нужно достичь каждой вершины. Здесь нужно использовать каждое ребро.
• Бэктрекинг (Backtracking): Пробовать маршруты и откатывать их это экспонента. Этот обход шагов назад не делает.
• Компоненты связности (Connected components): Все рёбра обязаны лежать в одной компоненте, и это одно из условий. Но считать группы здесь не цель.
• Стек (LIFO) (Stack (LIFO)): Стек это то, на чём обход держится. Эта страница про то, когда в него класть.

Эйлеров путь (алгоритм Хирхольцера): частые ошибки

• Возвращают путь в порядке обхода

  Выходной стек обязан быть развёрнут. Порядок обхода ставит тупики не туда.

• Не удаляют использованное ребро

  Тогда по одному ребру ходят бесконечно. Убирайте его в момент использования.

• Пропускают проверку степеней

  У множества графов такого обхода вообще нет. Проверьте степени до начала.

• Берут бэктрекинг

  Перебор маршрутов с откатом взрывается на большом графе. Правилу со стеком откаты не нужны.

Эйлеров путь (алгоритм Хирхольцера): задачи с собеседований

• Восстановление маршрута: Направленные рёбра, при равенстве берётся алфавитный порядок.
• Верная расстановка пар: Начало определяется по степеням вершин.
• Взлом сейфа: Последовательность де Брёйна это эйлеров цикл.
• Проверка эйлерова цикла: Все степени чётные и одна компонента связности.
• Цепочка домино: Каждая костяшка это ребро между двумя числами.
• Сборка генома из фрагментов: В графе перекрытий лежит эйлеров путь.
• Кёнигсбергские мосты: Исходное доказательство того, что такого обхода нет.

Эйлеров путь (алгоритм Хирхольцера): сложность по времени и памяти

O(E)

V вершин и E рёбер дают O(E log E) вместе с сортировкой рёбер. Без сортировки это O(E).