Minimum Spanning Tree (MST) - 최소 신장 트리

• 신장 트리 (Spanning Tree)
  • 그래프에서, 모든 노드가 연결
  • 트리의 속성을 만족하는 그래프

    • 사이클이 없는

    Link to original

• 최소 신장 트리
  • 가능한 신장 트리 중에서, 간선의 가중치 합이 최소인 트리
  • 최소 비용으로 연결된 경로
  • 통신사에서 네트워크를 전국에 깔 때
    • 여러 도시를 통신망(케이블, 광섬유 등)으로 연결할 때, 비용을 최소화하면서 모든 도시를 연결

• Kruskal's Algorithm

  • Minimum Spanning Tree (MST) - 최소 신장 트리
  • 간선 기준
    • 전체 관점시점으로 접근
      • 모든 간선에서 최소를 아니까
    • 로직
      • 간선 거리별로 정렬
        • sort
      • 작은 거리부터 포함 - Greedy
        • 단 사이클이 발생하지 않을때 포함(집합) - Union-Find
        • 누적하려는 최소 거리의 노드가 이미 같은 부모(집합)라면 사이클 이므로 pass
      • 노드 - 1 개의 간선이 포함되면 종료 or 간선 다 순회
        • 정렬된 간선을 다 돌면 종료
    • 초기 값
      • 정렬된 간선
      • 모든 노드에 대해서 rank[x] = 0, parent[x] = x 인 union-find용 자료
      • 정렬된 간선 완전 탐색 for
    • $E\log E$
      • 정렬에서 가장 최악

  Link to original

• Prim's Algorithm

  • Minimum Spanning Tree (MST) - 최소 신장 트리
  • 정점 기준
    • 정점의 인접 간선을 통해 확장해 가는 방식 - Greedy
    • 현재 관점 시점
      • 현재 정점에 의한 간선들만 아니까
  • 로직
    • 시작 정점 선택, 인접 간선 리스트에서 해당 정점 간선을 후보 간선 리스트에 추가
    • 후보 간선중 최소 간선 선택, 해당 정점 연결
      • 이미 해당 정점이 포함되어 있으면 무시 (해당 간선 pass)
    • 연결된 정점의 인접 간선도 후보 간선 리스트에 추가
    • 노드 - 1 개의 간선이 포함되면 종료 or 간선 다 순회
      • 후보 간선 리스트가 비어 있으면 종료
  • 초기 값
    • 인접 간선 리스트
      • 선택된 정점의 간선을 가져와 후보 간선 리스트에 넣는 용
    • 후보 인접 간선 리스트
      • priority_queue, heap으로 구성
    • 연결 확인용 자료
      • set으로 현재 MST 노드들 확인
    • 아무 노드를 시작 정점, 해당 정점의 인접 간선들 후보리스트에 추가
    • 후보리스트가 빌때까지 수행 while
  • $E\log E$
    • 큐에서 가장 최악
  • 개선된 프림 알고리즘
    • 정점이 간선보다 수가 적으므로 정점을 기준으로 우선순위 큐
    • 간선의 최소값이 아닌 노드의 최소값을 중심으로 우선순위 큐를 적용하는 방식
    • 로직
      • 최초 노드의 간선 값을 해당 간선 노드들의 값으로 부여, 큐에 넣기
      • 큐에서 최소값 노드를 가져와 간선 값과, 노드값 비교 업데이트
        • (무한대에서) 업데이트된 새로운 노드 큐에 넣기
        • 이미 큐에 있는 노드는?
          • 큐에 있는 값을 업데이트 해야하는 상황이 존재
            • 다익스트라처럼 현재 값 리스트가 있고, 다르면 무시하는 방향으로
      • 큐가 빌때까지
    • $E\log V$
      • 큐에서 가장 최악
      • 정점($V$)이 간선($E$)보다 최소 1개라도 적으므로 개선
      • $E>V$, 최악의 경우 $V^2=E$

  Link to original