У меня есть неориентированное дерево, вершины которого я хочу пометить. Узлы листа должны быть помечены как один. Затем предположим, что листья были удалены. На дереве, которое остается, листья должны быть помечены двумя. Этот процесс продолжается очевидным образом, пока все вершины не имеют метки. Причина, по которой я это делаю, заключается в том, что я хочу хранить вершины в очереди и проходить через них "сначала". Есть ли простой способ сделать это раз?
Я могу решить проблему, делая BFS на каждом шагу. Но в худшем случае на каждом шаге я прохожу каждую вершину, удаляю ровно два листа и ставлю их в очередь. Я считаю, что это занимает квадратичное время.
Другая идея состояла в том, чтобы сначала найти все листья, а затем сделать BFS из каждого листа. Это не дает мне желаемого решения. Например, рассмотрим своего рода «коронный граф», как показано на рисунке ниже. Желаемое решение показано, но запуск BFS с каждого листа приведет к использованию только двух меток.
В идеале, алгоритм линейного времени также легко объяснить и реализовать.
источник
Простой ответ заключается в следующем:
Топологически сортируйте график.
источник