Boruvka MST 알고리즘을 사용하여 포리스트에서 가장자리를 검색하는 가장 좋은 방법은 무엇입니까?

Question

현재 Baruvka의 알고리즘을 아래와 같이 코딩하고 있습니다. 그러나 이미 탐욕적인 선택을 사용하여 이미 찍힌 가장자리 목록에 이미 존재하는 경우 가장자리 e = uv를 확인하는 질문이 제공됩니다. O (logn) 시간에 edge e를 검색하려면 어떻게해야합니까? 이걸 도와 주시겠습니까 ... 검색 작업은 BFS 또는 DFS를 사용하여 수행 할 수 있으며 가장자리가 있는지 여부를 확인하지만 모든 단계에서 수행하면 비용이 많이 드는 작업이됩니다.

Boruvka 
{ 
while (T < n-1 edges) 
{ 
Find the components of T 
for each tree Ti of the forest T 
{ 
Find the smallest weight edge e = uv such that u is in Ti and v is not in Ti 

//Before adding e to T I have to check if it already exists in the list of greedy edges or not. If it exists then I would like to skip adding e to T and go to the next phase. 
Add e to T 
} 
} 
return T 
} 

그러나 하나의 가장자리를 두 번 이상 추가하는 문제가 있습니다. 그래서 그것을 없애기 위해서 edge를 추가하기 전에 edge가 이미 T에 추가되었는지 확인해야합니다. 이 검사를위한 O (n) 구현이 있습니까?

Answer 1

각 구성 요소에 대해 분리 된 데이터 구조 또는 다른 데이터 구조를 사용해야합니다. 엣지가 서로 다른 두 개의 연결된 구성 요소를 연결하는 경우 트리 엣지 목록에 엣지가 이전에 어떻게 존재합니까? Boruvka's algorithm을 읽어보십시오.

가장자리를 선택할 때마다 그 가장자리로 연결된 두 구성 요소를 병합해야합니다. 병합 할 때이 큰 구성 요소를 새로운 정점으로 간주하십시오.이 정점의 가장자리는 바깥으로 이동하는 구성 요소의 가장자리 여야합니다.