1626번 - 두 번째로 작은 스패닝 트리
1. 두 번째 대안 간선을 제대로 찾지 못한 경우
2. 두 번째 MST를 만들지 못하는 경우
3. 첫 번째 MST를 만들지 못하는 경우
가 있습니다. 첫 번째 MST를 만들지 못하는 경우가 존재하니.... MST를 만들 수 있는지 아닌지도 체크가 필요합니다.
프림일 경우 모든 정점을 다 방문했는지 체크해보고
크루스컬일 경우 설치한 간선의 수가 정점 - 1일 경우에 MST를 만들 수 있습니다.
감사합니다
감사합니다 선생님,,,
3번은 예상도 못했네
감사합니다... 가능한 모든 반례가 이 글에 다 있네요
댓글을 작성하려면 로그인해야 합니다.
dbfldkfdbgml 6년 전 19
1. 두 번째 대안 간선을 제대로 찾지 못한 경우
2. 두 번째 MST를 만들지 못하는 경우
3. 첫 번째 MST를 만들지 못하는 경우
가 있습니다. 첫 번째 MST를 만들지 못하는 경우가 존재하니.... MST를 만들 수 있는지 아닌지도 체크가 필요합니다.
프림일 경우 모든 정점을 다 방문했는지 체크해보고
크루스컬일 경우 설치한 간선의 수가 정점 - 1일 경우에 MST를 만들 수 있습니다.