Вывод взвешенного графа из групп существующих узлов - есть ли более разумный способ?

Question

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

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

Этот алгоритм работает нормально, но он медленный - есть ли способ избежать трехуровневых итераций?

Ведение единого списка ребер - вариант, но когда строится новый граф, новый список ребер необходимо сканировать на каждом шаге, чтобы увидеть, существует ли этот ребро (и увеличить его вес). 1007 *

Answer 1

Если O(E + Ngroups^2) - это опция, где E - это число ребер в данном графике, а Ngroups - это количество групп, вы можете сделать это следующим образом.

Вы можете создать матрицу смежности для результирующего графа. Затем переберите все ребра в данном графе, как

for each edge u in Graph
    for v such that edge u->v exists
        let w be the weight of u->v
        A[group(u)][group(v)] := A[group(u)][group(v)] + w;

Вы можете перестроить новый граф из матрицы смежности, если хотите.

Одной из возможных оптимизаций является использование сбалансированного дерева для удержания ребер, начинающихся в конкретной группе узлов, вместо всей матрицы смежности, это приведет к O(E*log(Ngroups)) сложности времени.