Эффективное сжатие графика производительности на основе критериев

Question

У меня есть ориентированный взвешенный простой график. Я хочу заключить контракт с каждым узлом, который имеет равное значение узла, с другим узлом, который напрямую связан с ним. После сжатия параллельные ребра будут превращены в один с суммой весов.

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

Answer 1

Если вам разрешено создавать новый график и вы не хотите делать это на месте, возможно, вам поможет структура данных для поиска объединения: https://en.wikipedia.org/wiki/Disjoint-set_data_structure поможет вам в этом.

Это структура, позволяющая вам определить репрезентативную вершину для каждого набора вершин, которые объединяются вместе. Вы создаете свой новый граф на этом наборе вершин и используете структуру union-find для создания ребер на этом новом графе.