---
title: "Эйлеров путь (алгоритм Хирхольцера)"
url: https://algopath.pro/ru/patterns/eulerian-path
language: ru
summary: "Пройдите граф, использовав каждое ребро ровно один раз. Кладите вершину в стек, когда она застряла, а ответ читайте с конца."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

## JavaScript

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

## Python

```python
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]
```

## PHP

```php
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);
}
```