크루스칼 알고리즘

1. 개요[편집]

2. 구현방법[편집]

• 그래프의 모든 간선의 집합 [math(E)]을 만든다.
• [math(E)]가 비어있지 않을 때까지
  • [math(E)]의 간선들 중 가중치가 최소인 간선을 지운다.[1]
    정렬해도 된다.
  • 삭제된 간선이 가리키는 정점 [math(x, y)]를 연결하여도 사이클이 발생하지 않는다면[2]
    이 과정을 Union Find으로 수행할 수 있다.
    연결한다.

이 문서의 내용 중 전체 또는 일부는 2023-12-21 12:14:11에 나무위키 크루스칼 알고리즘 문서에서 가져왔습니다.