Сложность этого жадного алгоритма для нахождения максимального независимого набора графа

Question

Какова сложность этого метода, который находит максимальный независимый набор графа?

Я думаю, что это O (| E |), верно?

Greedy(G): 
S = {} 
While G is not empty: Let v be a node with minimum degree in G 
    S = union(S, {v}) 
    remove v and its neighbors from G 
return S 

Answer 1

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

Что касается временной сложности - это зависит от того, как вы представляете график и как вы реализуете каждый шаг. Вот один из способов реализовать этот алгоритм за время O (m + n).

Предположим, что у вас есть график, представленный как список смежности. Создайте массив логических значений, по одному на узел, который отслеживает, может ли узел быть добавлен в независимый набор. Первоначально все эти логические значения верны. Затем создайте массив из n ведер, изначально пустых. Затем перебираем список смежности. Для каждого узла подсчитайте, сколько ребер его смежно (его степень), затем поместите этот узел в ведро по этому индексу. Эта настройка занимает время O (m + n), потому что каждое ребро сканируется ровно один раз, и нам нужно только время O (n) для инициализации вспомогательных структур.

Теперь, работая слева направо, просматривайте ведра. Для каждого узла в ковше выполните следующие действия. Если вспомогательный Boolean этого узла отмечен как false, пропустите узел. В противном случае добавьте узел в набор, пометьте его логическое значение false, а затем переместите его в запись списка смежности для узла и отметьте все логические значения смежных узлов false. Это имитирует удаление узла и его соседних узлов из графика.

В целом, этот второй этап занимает время O (m + n). Чтобы убедиться в этом, обратите внимание, что время O (n) занимает итерацию по массиву ведер, и через все итерации мы каждый раз каждый узел и каждый ребро посещаем один раз. Следовательно, это может быть реализовано в общем времени O (m + n).

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

Надеюсь, это поможет!