temp   3달 전

크루스칼 알고리즘에서 최저간선을 찾는것은 큰 문제가 아니라고 생각합니다. 그냥 소트시켜서 하나씩 찾으면 되니까요

중요한건 싸이클 찾기인데 우선 저는 이런 방법을 생각했습니다.


1. 가장 적은 간선부터 간선을 선택하고 vector에 담아둔다. 

2. 새로운 간선이 선택될때 미리 담아둔 vector를 통해 싸이클이 생성되는지 탐색해 본다. 

3. 싸이클이되면 버리고 아니라면 새로이 푸시한다.

인데... 매번 vector를 전부 탐색하니 시간이 낭비되는 느낌이라서 더 효율적인 방법이 없을까 싶내요. 


그리고 두번째 질문은 모든 간선이 사용되었음을 한번에 알아채려면 어떤 방법을 사용해야 할까요?

제 생각은 위의 2번과정에서 모든 정점이 체크되는지 확인하면 되지 않을까 싶은데 역시나 만약 정점이 10만정도된다면 굉장히 느린 알고리즘이 될거 같은데..


다른 방법이 없을까요?

sksdong1   3달 전

1) union-find 자료구조를 사용합니다.

2) 모든 간선 사용여부를 알 필요없이 내가 선택한 간선의 갯수가 V-1개임을 알아보면 됩니다. 

정점이 V개일 때 V-1개의 간선은 모든 정점을 연결하는 최소 간선의 갯수입니다.


댓글을 작성하려면 로그인해야 합니다.