В настоящее время я использую представление списка ребер графа в своем решателе Vertex Cover, который содержит Python список кортежей (u, v), представляющих вершины (натуральные числа). Я часто просматриваю список и удаляю все ребра, смежные с u и v, то есть всех соседей u и v. Это O (n), очевидно, неэффективно. Кроме того, вершины степени 0 должны быть удалены как можно скорее, что, к счастью, в этом представлении происходит «автоматически».
Какая структура данных (для представления графа или только для этого поиска) будет лучше?
Я пробовал словарь множеств (отображение вершин -> множество его соседей), но у этого есть главный недостаток в управлении состоянием других вершин - когда я удаляю вершину, мне также нужно go и удалить ее от всех его соседей, а также проверьте, создает ли это вершину степени 0 (и удалите ее).
Что бы вы предложили? Или мне просто придерживаться словаря и выполнять всю работу по поддержанию состояния?