오래전 부터 -_-;; 고민해볼만 하다고 생각했던 문제인데 ,,,
가중치의 합이 두번째로 작은 신장트리를 만들기 위한 알고리즘은 어떤 것이 있을까요 ....
Weights 들이 Distinct 하지 않은 조건에서 말이죠....
만약 distinct 하다면 ,,, Kruscal 로 MST 를 구성한 다음에 하나의 edge 를 지우고 남아있던 edge 를 추가해보는 방법 ,,,
이나 반대로 하나를 추가하고 생긴 사이클 내의 다른 edge 를 제거하는 ... 과정을 반복 하는 방식으로
풀 수 있을 것 같은데 말입니다만,,,
MST가 있는 경우, 각 vertex를 연결하는 path중에서 제일 긴 edge의 길이를 O(N^2)만에 구할 수 있습니다.
그러면 현재 연결되지 않은 모든 edge들에 대해서
"현재의 edge를 연결하고 MST를 이루고 있는 path중 제일 긴 edge를 자르는 연산"을 한 번 한다면
Secondary MST를 찾을수가 있습니다. 따라서 O(N^2)으로 풀리게 되지요.
LucidaSH
오래전 부터 -_-;; 고민해볼만 하다고 생각했던 문제인데 ,,,
가중치의 합이 두번째로 작은 신장트리를 만들기 위한 알고리즘은 어떤 것이 있을까요 ....
Weights 들이 Distinct 하지 않은 조건에서 말이죠....
만약 distinct 하다면 ,,, Kruscal 로 MST 를 구성한 다음에 하나의 edge 를 지우고 남아있던 edge 를 추가해보는 방법 ,,,
이나 반대로 하나를 추가하고 생긴 사이클 내의 다른 edge 를 제거하는 ... 과정을 반복 하는 방식으로
풀 수 있을 것 같은데 말입니다만,,,
16년 전