기존 노드 그룹에서 가중 그래프를 유도하는 것이 더 똑똑한 방법일까요?

Question

나는 가중치가 부여되지 않은 그래프가 있고 기존 노드 그룹을 기반으로 새 그래프를 유도합니다. 각 그룹은 원래 그래프 사이의 가장자리 총 중량을 기준으로 다른 그래프에 연결된 노드가됩니다.

현재 데이터 구조에서 각 노드는 이웃 및 가중치 목록을 가지며 알고리즘은 노드의 그룹/각 에지에서 그룹/각 노드를 가져 와서 가중치를 합산하여 에지를 결정합니다. 새로운 그래프.

이 알고리즘은 정상적으로 작동하지만 속도가 느립니다. 3 단계 반복을 피할 수있는 방법이 있습니까?

단일 모서리 목록을 유지하는 것은 옵션이지만 새 그래프가 작성되면 각 모서리가 이미 존재하는지 (그리고 가중치가 증가하는지) 확인하기 위해 각 단계에서 새 모서리 목록을 스캔해야합니다.

Answer 1

은 주어진 그래프의 가장자리 수인 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)) 시간 복잡도로 이어질 것입니다.