Spanning Tree 풀이 - 1. Kruskal 크루스칼 알고리즘 (JAVA)
2019.09.23 1. Kruskal 그래프의 모든 간선을 기준으로 가중치를 작은 순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가. 이때 스패닝 트리가 사이클을 이룰 경우 해당 간선은 고려대상에서 제외해야 함. - 풀이방법 1) 간선을 가중치 오름차순으로 정렬 2) 간선 목록을 순회하며 스패닝 트리에 추가 이때, 추가할 간선이 사이클을 이룰 경우 해당 간선은 제외 그렇다면 간선이 사이클을 이루는지는 어떻게 판단하는가? => 간선 추가하기 전, 간선의 시작점과 끝점 부모가 동일할 경우 사이클을 이룬다고 판단할 수 있음 즉 Union-find 알고리즘을 통해 추가할 간선의 부모가 동일한지 판단할 수 있음 - 즉석 문제! 위 그림 좌측 상단과 같은 그래프가 주어진다고 해보자. 처음 노드의 수 N과 간선의 수 ..
Algorithm
2019. 9. 23. 21:13
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 크루스칼 알고리즘
- MST
- 데이터분석 준전문가
- Kruskal Algorithm
- 크루스칼 알고리즘 자바
- Algorithm
- Kruskal Algorithm Java
- R
- ADsP 후기
- 자격증
- kruskal
- 크루스칼
- ADsP
- 최소신장트리
- java
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 8 | 9 | 10 | 11 | 12 | 13 | 14 |
| 15 | 16 | 17 | 18 | 19 | 20 | 21 |
| 22 | 23 | 24 | 25 | 26 | 27 | 28 |
| 29 | 30 |
글 보관함