도대체 뭘 필기해놓은건지 모르겠다

크루스칼 알고리즘 minimun spanning tree 찾을때 엣지들을 오름정렬하면서

no cycle 이면서 connection 되면 추가하는 식으로 짧은경로 찾아내는 식..


step 0 은 edge 오른정렬하는거고 얘가 nlogn 이라 얜 알겠는데 

step 1 은 엣지만큼 for문 돌려서 no cyclt 이면 최소 edge 그룹에 추가하는거에용 


결국 total Elog E 라는건 이해가 가는데 중간과정 step 1 을 모르겠음


각 비교마다 자기의 root 를 만들어놓음? cycle 만들어지면 root 리턴하고 서로 루트가 다르면 no cycle?

아... 뜻은 알겠다 엣지마다  log|E| 씩 반복하는거네

 근데 왜 한사이클 도는게 이게 왜때문에 log|E| 임...? 왜때문에...? 


결론 : 

각 비교마다 자기의 root 를 만들어놓음? cycle 만들어지면 root 리턴하고 서로 루트가 다르면 no cycle? : 왜때문에  log|E|?