deo2kim
맞왜틀
deo2kim
전체 방문자
오늘
어제
  • 분류 전체보기
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • 개발
    • Infra

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

최근 댓글

최근 글

티스토리

반응형
hELLO · Designed By 정상우.
deo2kim

맞왜틀

최소 신장 트리(Minimum Spanning Tree)
CS/Algorithm

최소 신장 트리(Minimum Spanning Tree)

2020. 8. 12. 22:01
반응형

그래프에서 최소 비용을 구하는 문제

1. 모든 정점을 연결하는 간선들의 가중치합이 최소가 되는 트리 - 프림과 크루스칼 두가지 형태가 있다.

(프림은 정점을 기준으로, 크루스칼은 간선을 기준으로 MST를 만들어간다.)

2. 두 정점 사이의 최소 비용 경로 찾기  - BFS에서 가중치가 추가된 형태

 

신장 트리

1. n 개의 정점으로 이루어진 무방향 그래프에서 n 개의 정점과 n-1 개의 간선으로 이루어진 트리

 

최소 신장 트리

1. 무방향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

 

그래프의 표현

1. 인접 행렬

인접 행렬

2. 인접 리스트

인접 리스트

🟨 프림 알고리즘:

프림 알고리즘은 하나의 정점에 연결된 간선중 가중치가 최소인 정점을 선택한다.

 

하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 알고리즘

1. 임의로 노드를 하나 선택하고 시작한다.

2. 선택한 노드와 인접하는 노드들 중 최소 가중치의 간선과 연결된 노드를 선택

3. 모든 노드가 선택될 때까지 위의 과정을 반복한다.

 

MST 리스트

MST에 포함되는 노드들과 그렇지 않은 노드들로 나누어 관리한다.

(보통 알고리즘을 풀 때 visited리스트와 비슷한 개념이라고 생각하면 된다)

 

🟦 이 알고리즘으로 해결한 문제:

https://deok2kim.tistory.com/67

 

[python] SWEA - 1251. [S/W 문제해결 응용] 4일차 - 하나로

🤔문제 해결 1. D4 | MST - prim 2. 간선의 가중치를 값으로 하는 인접 행렬을 만든다 3. 최소 값을 갱신해줄 가중치 리스트, MST에 포함되지 체크하는 리스트, 부모노드 선택리스트를 만든다. (여기서�

deok2kim.tistory.com

 

반응형
저작자표시 비영리 변경금지 (새창열림)

'CS > Algorithm' 카테고리의 다른 글

퀵 정렬(quick sort)  (1) 2020.09.24
삽입 정렬(insertion sort)  (0) 2020.09.23
선택 정렬(selection sort)  (0) 2020.09.22
버블 정렬(bubble sort)  (0) 2020.09.21
빅 오(Big O) - 시간복잡도  (0) 2020.09.09
    'CS/Algorithm' 카테고리의 다른 글
    • 삽입 정렬(insertion sort)
    • 선택 정렬(selection sort)
    • 버블 정렬(bubble sort)
    • 빅 오(Big O) - 시간복잡도
    deo2kim
    deo2kim
    코딩 기록하기

    티스토리툴바