스패닝 트리를 만들되 리프노드의 개수가 최대가 되도록 만들어야 하는것 같은데

그냥 크루스칼이나 프림 알고리즘을 사용하면 리프노드가 최대가 된다는 보장이 없어서 어떻게 해야할지 잘 모르겠습니다...

리프노드가 될 수 있는 노드들을 따로 뽑아내서 해보려고 해도 어떤기준으로 뽑아야 할지를 잘 모르겠어서...

고수님들 조언부탁드립니다ㅠ