Алгоритм линейной метки времени для дерева?

12

У меня есть неориентированное дерево, вершины которого я хочу пометить. Узлы листа должны быть помечены как один. Затем предположим, что листья были удалены. На дереве, которое остается, листья должны быть помечены двумя. Этот процесс продолжается очевидным образом, пока все вершины не имеют метки. Причина, по которой я это делаю, заключается в том, что я хочу хранить вершины в очереди и проходить через них "сначала". Есть ли простой способ сделать это раз?O(n+m)

Я могу решить проблему, делая BFS на каждом шагу. Но в худшем случае на каждом шаге я прохожу каждую вершину, удаляю ровно два листа и ставлю их в очередь. Я считаю, что это занимает квадратичное время.

Другая идея состояла в том, чтобы сначала найти все листья, а затем сделать BFS из каждого листа. Это не дает мне желаемого решения. Например, рассмотрим своего рода «коронный граф», как показано на рисунке ниже. Желаемое решение показано, но запуск BFS с каждого листа приведет к использованию только двух меток.

введите описание изображения здесь

В идеале, алгоритм линейного времени также легко объяснить и реализовать.

Боб Вист
источник

Ответы:

8

Необжитые деревья

Вы можете использовать приоритетную очередь, чтобы решить это в :O(E+VlogV)

  • Поместите все вершины в очередь с приоритетом, причем их приоритетом будет их степень.
  • Пока очередь не пуста:
    • Удалите вершину с минимальным приоритетом, которая должна быть 1 (или 0 в самом конце).v10
    • σ(v)=1+maxσ(u)uv
    • 1u

O(E+V)

  • V
  • V
  • 1
  • Пока очередь не пуста:
    • v
    • σ(v)=1+maxσ(u)uv
    • v
    • vu1u
    • u1u

Корни деревьев

Вместо этого используйте DFS. Вот эскиз алгоритма.

  • vvd(v)=1
  • vd(v)=1+maxd(u)u

Вы запускаете этот алгоритм в корне.

Юваль Фильмус
источник
Это правильно? Рассмотрим дерево 1-> 2-> 3-> 4-> 5, где 1 - корень. 2 должен получить этикетку 1, а вы даете 3? Или под детьми вы подразумеваете соседей? С какого узла мы запускаем dfs?
Knoothe
245432
Я не задавал вопрос :-). Я интерпретировал вопрос так: неориентированное дерево. Маркируйте все листья. Удалить их. Рекурс на получившееся дерево. В этом случае дерево на самом деле 1-2-3-4-5, шаг 1, вы удаляете 1 и 5, затем 2 и 4, а затем 3. См. Параграф о «графе короны». Это один из классических алгоритмов поиска центра дерева.
Knoothe
1 не лист. Это очень далеко от листа, это корень. Я интерпретировал вопрос как нацеливание на корневые деревья. Возможно, нам следует дождаться ответа ОП.
Юваль Фильмус
2
1+max{d(u)}12
2

Простой ответ заключается в следующем:

  • (u,v)uv

  • Топологически сортируйте график.

  • vv

O(n+m)O(n+m)

DW
источник