[MST] Prim & Greedy

2023. 9. 1. 18:49· Programming/Data Structure

MST 중 prim알고리즘은 그리디알고리즘을 만족하는 몇 안 되는 알고리즘이다.
여기서 mst = minimum spaning tree로 최소신장트리이다.

신장트리 중 가중치의 총합이 가장 최소임을 의미한다.
특징으로는

1. 간선의 가중치의 합이 최소여야 한다.
2. n개의 정점을 가지는 그래프에 대해 반드시 (n-1) 개의 간선만을 사용해야 한다.

노드 1번에서 가질 수 있는 간선의 수 : 2(N-1)
노드 2번에서 가질 수 있는 간선의 수 : 2(N-2)
노드 3번에서 가질 수 있는 간선의 수 : 2(N-3)

이를 모두 더하면

2(N-1 + N-2 + N-3 + .... + N-N)
2*(N^2 - (N(N+1)/2))
E = N(N-1)
이다.

이때 prim알고리즘은 현재 보이는 것 중 가장 좋은 (최소 or 탐욕적인)해를 택한다.
prim은

selected[MAX_VERTEX]
distance[MAX_VERTEX] 이다.

여기서 그리디로 간선을 고를 때 큰간선을 골랐을 때, 더 시간이 빠를 수도 있지 않을까? 에 관한 의문을 품을 수 있다.

이는 그림을 보고 이해 할 수 있다.

그런 경우는 수학적으로 증명되어 있고 절대로 그럴 일 이 없다.

따라서 제일 작은 경우를 골랐을 때, 최소가 된다.

보면, 최소값을 고를 때, 더 큰 간선보다 그거를 골라야
그 노드를 다시 갈 때 더작게 갈 수 있는 경우의 수가 생기고 더 작게 갈 수 있는 방법이 있다.
왜냐면 distance리스트에 최소로 작아지는 값을 update하면서 계속 기록하고 있기 때문이다.
따라서 이를 통해 고른 vertex들은

최단거리로 이은상태가 된다.

 

이때 시작정점으로부터 트리집합으로 뻗어나가기 때문에 이 그래프는 사이클이 없는 Tree 모양이 된다. 

또한, 이런 간선의 값을 heap == 즉, minimum heap ==  minimum tree로 구성하여 가지고 있으면서 

root node를 항상 뽑아서 mst를 완성시켜야 

원래 알고있는 시간복잡도 O(E*log(E)인 복잡도를 지닌다.

위에서 말한바와 같이 E = N(N-1) 최대 이 정도의 크기를 가진다.

이는 

kruskal알고리즘을 적용시켰을 때 얘기이다.

 

prim알고리즘은 

주 반복문이 정점의 수 n만큼 반복하기에, prim 알고리즘 o(n^2) == o(v^2)의 시간복잡도를 지닌다.

kruskal = O(E*log(E)
prim = o(v^2) = O((V + E)logV)

prim은 인접행렬을 사용하면 o(v^2)
우선순위 큐를 사용하면 O((V + E)logV)

 

따라서 우선순위큐를 사용하느냐에 따라서 시간복잡도가 많이 차이 난다.

이때, kruskal알고리즘은 union-find알고리즘을 사용한다.

 

'Programming > Data Structure' 카테고리의 다른 글

[MST] kruskal(크루스칼), prim(프림) 알고리즘  (0) 2024.02.16
[자료구조] 우선순위 큐(Priority Queue), Heap  (0) 2023.09.02
'Programming/Data Structure' 카테고리의 다른 글
  • [MST] kruskal(크루스칼), prim(프림) 알고리즘
  • [자료구조] 우선순위 큐(Priority Queue), Heap
code_wizard
code_wizard
헛둘헛둘
code_wizard
코드의 신비: 컴퓨터 마법사의 일기
code_wizard
전체
오늘
어제
  • 분류 전체보기 (60)
    • 생각정리 (1)
    • Project (7)
      • Caston Design (5)
      • 상명대 축제 2023 "비상(飛上)" (1)
      • 취뽀Lab (1)
    • Solo Project (4)
      • 소셜로그인+JWT (4)
    • Back-end (4)
      • Spring (4)
      • Test (0)
    • DevOps (1)
      • Docker (1)
    • Tip💡 (2)
    • CS🖥️ (5)
      • Operating System (1)
      • Network (0)
      • OOP (4)
    • Programming (35)
      • Data Structure (3)
      • Algorithm(Python) (26)
      • Java (1)
      • Python (5)
    • DeepLearning (1)
    • sw마에스트로 (0)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • BFS
  • java
  • 티스토리챌린지
  • 리트코드
  • MSE
  • 구현
  • 백준
  • 축제사이트
  • Docker
  • 경사하강법
  • 그리디알고리즘
  • 캡스톤디자인
  • 오버라이딩
  • super
  • SW마에스트로
  • 오버로딩
  • 21966번
  • jpa
  • SWEA
  • 오블완
  • 프로그래머스
  • Baekjoon
  • 평균오차제곱
  • 도커커맨드
  • 20115번
  • 문자열

최근 댓글

최근 글

hELLO
code_wizard
[MST] Prim & Greedy
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.