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

Eulerian path (Hierholzer's algorithm)

O(E)

Пройдите граф, использовав каждое ребро ровно один раз. Кладите вершину в стек, когда она застряла, а ответ читайте с конца.

Elman HuseynovОбновлено 17 окт. 2026 г.

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

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

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

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

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

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

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

Источники: Википедия: Эйлеров цикл

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

Все билеты по одному разу: алгоритм Хирхольцера

eulerianPath([["JFK", "ATL"], ["ATL", "BER"], ["ATL", "SFO"], ["SFO", "DEN"], ["DEN", "JFK"], ["JFK", "LAX"], ["LAX", "ATL"]], "JFK")

число над аэропортом = сколько билетов оттуда ещё не использовано

stack (стек)

JFK← вершина

route (заполняется с конца)

пусто

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

1 / 17

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

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();
}

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

def eulerian_path(tickets, start):
    adj = {}
    for frm, to in tickets:
        adj.setdefault(frm, []).append(to)
    for frm in adj:
        adj[frm].sort(reverse=True)  # pop smallest first
    route = []
    stack = [start]
    while stack:
        node = stack[-1]
        if adj.get(node):
            stack.append(adj[node].pop())
        else:
            route.append(stack.pop())  # dead end: record and back up
    return route[::-1]

function eulerianPath(array $tickets, string $start): array {
    $adj = [];
    foreach ($tickets as [$from, $to]) {
        $adj[$from][] = $to;
    }
    foreach ($adj as $from => &$list) {
        rsort($list); // pop smallest first
    }
    unset($list);
    $route = [];
    $stack = [$start];
    while ($stack) {
        $node = end($stack);
        if (!empty($adj[$node])) {
            $stack[] = array_pop($adj[$node]);
        } else {
            $route[] = array_pop($stack); // dead end: record and back up
        }
    }
    return array_reverse($route);
}

    public static List<String> eulerianPath(String[][] tickets, String start) {
        Map<String, List<String>> adj = new HashMap<>();
        for (String[] ticket : tickets) {
            adj.computeIfAbsent(ticket[0], k -> new ArrayList<>()).add(ticket[1]);
        }
        for (List<String> dests : adj.values()) {
            dests.sort(Comparator.reverseOrder()); // pop smallest first
        }
        List<String> route = new ArrayList<>();
        Deque<String> stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            List<String> dests = adj.get(stack.peek());
            if (dests != null && !dests.isEmpty()) {
                stack.push(dests.remove(dests.size() - 1));
            } else {
                route.add(stack.pop()); // dead end: record and back up
            }
        }
        Collections.reverse(route);
        return route;
    }

    public static List<string> EulerianPath(string[][] tickets, string start) {
        var adj = new Dictionary<string, List<string>>();
        foreach (var ticket in tickets) {
            if (!adj.ContainsKey(ticket[0])) adj[ticket[0]] = new List<string>();
            adj[ticket[0]].Add(ticket[1]);
        }
        foreach (var dests in adj.Values) {
            dests.Sort();
            dests.Reverse(); // pop smallest first
        }
        var route = new List<string>();
        var stack = new Stack<string>();
        stack.Push(start);
        while (stack.Count > 0) {
            if (adj.TryGetValue(stack.Peek(), out var dests) && dests.Count > 0) {
                string next = dests[dests.Count - 1];
                dests.RemoveAt(dests.Count - 1);
                stack.Push(next);
            } else {
                route.Add(stack.Pop()); // dead end: record and back up
            }
        }
        route.Reverse();
        return route;
    }

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

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

Дан список авиабилетов, каждый надо использовать ровно один раз, начиная с 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();
}

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

Паттерн «Эйлеров путь (алгоритм Хирхольцера)» нужен, когда в условии есть слова «использовать каждое ребро ровно один раз», «восстановить маршрут по билетам» или «рисунок одним росчерком / не отрывая ручку». Решение на нём обычно укладывается в O(E).

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

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

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

Паттерн «Эйлеров путь (алгоритм Хирхольцера)» чаще всего путают с этими паттернами: Обход графа BFS / DFS, Бэктрекинг, Компоненты связности и Стек (LIFO).

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

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

Возвращают путь в порядке обхода
Выходной стек обязан быть развёрнут. Порядок обхода ставит тупики не туда.
Не удаляют использованное ребро
Тогда по одному ребру ходят бесконечно. Убирайте его в момент использования.
Пропускают проверку степеней
У множества графов такого обхода вообще нет. Проверьте степени до начала.
Берут бэктрекинг
Перебор маршрутов с откатом взрывается на большом графе. Правилу со стеком откаты не нужны.

Паттерн «Эйлеров путь (алгоритм Хирхольцера)» решает такие задачи с собеседований: Восстановление маршрута, Верная расстановка пар, Взлом сейфа, Проверка эйлерова цикла, Цепочка домино, Сборка генома из фрагментов и Кёнигсбергские мосты.

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