"크러스컬 알고리즘"의 두 판 사이의 차이

 
(차이 없음)

2017년 2월 7일 (화) 14:30 기준 최신판

1 무엇인가?

최소 비용 신장 트리를 [math]O(ElogV)[/math]만에 구하는 알고리즘이다.

2 어떻게 구현하는가?

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