Secondary MST ....

  • LucidaSH
    LucidaSH

    오래전 부터 -_-;; 고민해볼만 하다고 생각했던 문제인데 ,,,
    가중치의 합이 두번째로 작은 신장트리를 만들기 위한 알고리즘은 어떤 것이 있을까요 ....
    Weights 들이 Distinct 하지 않은 조건에서 말이죠....
    만약 distinct 하다면 ,,, Kruscal 로 MST 를 구성한 다음에 하나의 edge 를 지우고 남아있던 edge 를 추가해보는 방법 ,,,
    이나 반대로 하나를 추가하고 생긴 사이클 내의 다른 edge 를 제거하는 ... 과정을 반복 하는 방식으로
    풀 수 있을 것 같은데 말입니다만,,,

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    13년 전
2개의 댓글이 있습니다.
  • astein
    astein

    MST가 있는 경우, 각 vertex를 연결하는 path중에서 제일 긴 edge의 길이를 O(N^2)만에 구할 수 있습니다.
    그러면 현재 연결되지 않은 모든 edge들에 대해서
    "현재의 edge를 연결하고 MST를 이루고 있는 path중 제일 긴 edge를 자르는 연산"을 한 번 한다면
    Secondary MST를 찾을수가 있습니다. 따라서 O(N^2)으로 풀리게 되지요.


    13년 전 link
  • Being
    Being

    O(V^2 + E) ㅋㅋㅋㅋ


    13년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.