#algorithm #graph #tree
Вопрос:
Учитывая график G с красными и синими краями и константой K, разработайте детерминированный алгоритм линейного времени, который находит связующее дерево G с ровно K красными краями (или возвращает False , если такое связующее дерево не существует).
Что мы сделали до сих пор:
Пусть каждое красное ребро имеет вес -1, а каждое синее ребро имеет вес 0.
Найдите минимальное связующее дерево (используя стандартный алгоритм линейного времени). Итак, у нас есть связующее дерево T с минимальным весом, то есть мы использовали как можно больше красных ребер, потому что красные ребра только уменьшат вес.
Если в T меньше K красных ребер, мы возвращаемся False .
Если есть ровно K красных краев, мы закончили, T-это ответ.
Если красных краев больше K, нам нужно заменить их синими.
Это наша проблема, как мы делаем это в линейном времени?
Каждое добавленное синее ребро создаст цикл, поэтому удаление одного красного ребра из цикла будет работать, но как мы можем обеспечить линейность таким образом? Это вообще хороший подход?
Комментарии:
1. Неясно, пытаетесь ли вы найти минимальное связующее дерево с K красными краями, или любое связующее дерево с K красными краями, или связующее дерево, которое минимально среди тех связующих деревьев, у которых есть K красных краев.
2. Только что узнал, что это можно решить с помощью сжатия ребер…не знаю, как это использовать..
3. @Тайлер: Для меня это довольно ясно: «находит связующее дерево G с ровно K красными краями», ничего не сказано о минимальности
4. @RachelBernouli — В вашем вопросе «Найдите минимальное связующее дерево (используя стандартный алгоритм линейного времени)». какой алгоритм линейного времени вы имеете в виду ?
Ответ №1:
подсказки
Вы можете сделать это за линейное время, используя два прохода алгоритма Прима. (Обычно алгоритм Prim не является линейным по времени, но когда у вас есть только два типа ребер, вам не нужно тратить время на сортировку ребер).
Проход 1
В первом проходе следуйте синим краям перед красными краями и отметьте любые красные края, которые вы вынуждены взять.
Если вы отметите C ребер в этом процессе, то мы знаем, что в любом решении связующего дерева должно быть по крайней мере C красных ребер, поэтому, если C>K, это невозможно.
Проход 2
Предположим, мы нашли C (
Во втором проходе следуйте красным краям перед синим, пока общее количество дополнительных красных краев не достигнет K-C. Во втором проходе вам также разрешается следовать красным краям, отмеченным в первом проходе (и они не учитываются в вашем общем зачете).
Если ваши дополнительные красные края не достигают K-C, то это невозможно.
Комментарии:
1. Хорошая идея, я собирался предложить очень похожую идею в сочетании с Крускалом: сначала запустите ее с
e = B R(B = синие края, R = красные края). Пусть X-ребра в R, которые использовались в этом запуске. Теперь снова запустите Kruskale = X (R X) Bи теперь прекратите добавлять красные края, как только вы выбралиkодин из них.2. @NiklasB. Это звучит так же хорошо. Я буду голосовать, если вы поставите это в качестве ответа 🙂
3. Не могли бы вы объяснить подробнее? Алгоритм Prims работает на взвешенных графиках, так что вы имеете в виду, говоря «сначала идет синий»?..
4. Я имею в виду использовать тот же подход, что и вы (например, присвоение веса 0 синим краям и веса 1 красным краям). Как только вы это сделаете, алгоритм Prim всегда будет добавлять синие края вместо красных, когда это возможно.
5. @NiklasB. Когда вы запустите Kruskal, не будет ли он использовать union-find и приводить к решению O(V logV)? ОП просит линейного решения.