최소 신장 트리

UkJJang·2021년 9월 26일
0

신장트리

  • Spanning Tree or 신장 트리라고 불린다.
  • 원래의 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프
  • 신장트리의 조건
    1. 본래의 그래프의 모든 노드를 포함해야 한다.
    2. 모든 노드가 서로 연결되어야 한다.
    3. 트리의 속성을 만족시켜야한다. (사이클이 존재하지 않음)

최소 신장 트리

  • 신장 트리에서 간선의 가중치 합이 최소인 트리를 말한다.
  • 대표적으로 크루수칼 알고리즘, 프림 알고리즘이 있다.
profile
꾸준하게 성실하게

0개의 댓글