UkJJang
로그인
UkJJang
로그인
최소 신장 트리
UkJJang
·
2021년 9월 26일
팔로우
0
아침 알고리즘 공부
0
신장트리
Spanning Tree or 신장 트리라고 불린다.
원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
신장트리의 조건
1. 본래의 그래프의 모든 노드를 포함해야 한다.
2. 모든 노드가 서로 연결되어야 한다.
3. 트리의 속성을 만족시켜야한다. (사이클이 존재하지 않음)
최소 신장 트리
신장 트리에서 간선의 가중치 합이 최소인 트리를 말한다.
대표적으로 크루수칼 알고리즘, 프림 알고리즘이 있다.
UkJJang
꾸준하게 성실하게
팔로우
이전 포스트
HTTP 상태코드 정리
다음 포스트
쿠키(Cookie) 정리
0개의 댓글
댓글 작성