kruskal의 알고리즘에서 가장자리를 정렬하는 가장 좋은 방법은 무엇입니까?

Question

나는 Kruskal의 알고리즘을 구현 중이며 가장자리를 주문하는 것이 더 좋은 방법인지 잘 모르겠습니다. 큰 입력 (300 000+ 에지)에 가장 적합한 시간 복잡성이 필요합니다. 시간 복잡성은 비슷하지만 큰 입력에 대해 더 빨리 알고 싶습니다.

Answer 1

라이브러리 제공 정렬 기능을 사용하여 시작하십시오. 솔루션 작동. 그것은 충분히 빠를 수 있습니다. 그렇지 않다면 프로필을 작성하고 그것이 천천히 내려가는 원인인지 판단합니다. 그러나 코드 최적화에 정말 능숙하지 않으면 사용자 정의 정렬이 기본 제공 버전보다 느려질 수 있습니다.