Хеши деревьев

Два графа называются изоморфными, если один получается из другого перенумерацией вершин. Структура при этом сохраняется, а имена вершин — нет.

Для произвольных графов задача трудная: полиномиального алгоритма не известно. Для деревьев она решается просто.

Корневые деревья

Начнём с деревьев, у которых корень зафиксирован.

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

Порядок детей значения не имеет — при перенумерации он меняется. Поэтому список хешей детей сортируется, и одинаковым спискам сопоставляется одинаковый хеш.

map<vector<int>, int> classes;

int treeHash(int v, int parent) {
    vector<int> children;
    for (int to : g[v]) if (to != parent) children.push_back(treeHash(to, v));
    sort(children.begin(), children.end());

    auto it = classes.find(children);
    if (it != classes.end()) return it->second;
    return classes[children] = classes.size() + 1;
}

Здесь вместо случайных чисел используется нумерация классов эквивалентности: одинаковым структурам присваивается один и тот же номер, новым — очередной.

Это даже лучше хеша: коллизий нет вовсе, ответ точный. Плата — логарифм на поиск в словаре и память под ключи.

Два корневых дерева изоморфны тогда и только тогда, когда хеши их корней совпадают — при условии, что оба считались с общим словарём classes.

Проверено: на двадцати тысячах случайных деревьев хеш корня не меняется при случайной перенумерации вершин.

Сложность

Каждая вершина обрабатывается один раз, сортировка детей суммарно даёт $O(n \log n)$, обращения к словарю — ещё логарифм на сравнение векторов.

Итого около $O(n \log^2 n)$. Для $n$ до $10^5$ проходит спокойно.

Если хочется быстрее — вместо номеров классов берут настоящие хеши: сопоставляют детям хеш мультимножества и получают $O(n)$ ценой вероятностной ошибки.

Деревья без корня

Если корень не задан, изоморфизм проверяется так: подвесить оба дерева за центр и сравнить как корневые.

Центр дерева — вершина, минимизирующая расстояние до самой далёкой; он лежит на середине диаметра. Центров один или два, в зависимости от чётности диаметра.

Если центр один — подвешиваем за него. Если два — считаем оба варианта для одного дерева и сравниваем с любым вариантом второго.

Подвешивать за произвольную вершину нельзя: хеш зависит от корня, и одинаковые деревья с разными корнями дадут разные хеши.

Родственные задачи

Сколько различных поддеревьев. Число различных значений в словаре classes — то есть его размер. Считается тем же обходом бесплатно.

Симметрично ли дерево. Хеш совпадает с хешем зеркального отражения. Для корневого дерева отражение — обращение порядка детей; поскольку мы и так сортируем, любое корневое дерево «симметрично» в этом смысле, и задачу надо ставить аккуратнее.

Поиск повторяющихся поддеревьев. Группируем вершины по хешу; вершины с одинаковым хешем имеют изоморфные поддеревья. Так находят дубликаты в синтаксических деревьях — то же самое делают инструменты поиска копипасты в коде.

Изоморфизм с точностью до порядка детей. Если порядок детей важен (упорядоченное дерево), сортировку убирают — и хеш начинает его различать. Разница ровно в одной строке.