c로쓴자료구조론 이석호책 기준으로

 

 

마지막에

 

e를선택함으로서 이모든간선이 U에 속하게된다는게 이해가안됩니다...

 

증명과정은 대충

T=크루스컬이만든신장트리

 

이게 MST가 아니고

 

U=임의의MST가 있다고 가정하고요...

 

T에서 최소간선하나빼서 e라하고

U에 추가하고

 

U에서 e추가하면서 사이클만든것중 하나f라고 하고 f를 뺴서 만든 V 

 

V = U +f -e 를 전제하고

 

f <e라면 크루스컬이 f대신 e를 택한것은

 

f를 선택하면 사이클을 이루기떄문이다..

 

여기까지

 

그다음에 e를 선택함으로서 사이클을 이루는 간선들이 U에도 속한다는데 잘 이해가안됩니다...