# Kruskal's Algorithm

6개의 포스트
post-thumbnail

Kruskal's Algorithm

Kruskal's Algorithm은 가장 적은 비용으로 노드들을 연결하기 위한 알고리즘이다.모든 노드를 최소한의 비용으로 연결시키면 되기 때문에 모든 간선 정보를 오름차순으로 정렬하고 비용이 적은 간선부터 차례대로 연결해주면 된다.1\. 정렬된 순서에 맞게 그래프에

2022년 3월 11일
·
0개의 댓글
·
post-thumbnail

무방향 그래프에서의 사이클여부 확인 방법

최근 "최소 스패닝 트리"에 대해 알게되고 해당 문제를 접하게 되었다.당연히 그래프에서 사이클의 존재 여부를 파악하기 위해서는 DFS를 통해 전부 탐색해봐야지만 판단할 수 있다고 생각하고 있었다.그러나 해당 포스트에서는 DFS보다 훨씬 간단하고, 적은 시간이 걸리는 서

2022년 2월 11일
·
0개의 댓글
·
post-thumbnail

[BaekJoon] 1647 도시 분할 계획 (Java)

🔗 문제 링크 https://www.acmicpc.net/problem/1647

2021년 11월 1일
·
0개의 댓글
·
post-thumbnail

[BaekJoon] 1774 우주신과의 교감 (Java)

🔗 문제 링크 https://www.acmicpc.net/problem/1774

2021년 10월 13일
·
0개의 댓글
·
post-thumbnail

[알고리즘] Kruskal's algorithm

Kruskal's algorithm은 대표적인 MST알고리즘으로 Edge를 가중치에 따라 정렬한 후 가중치가 낮은 Edge부터 cycle이 생기지 않는다면 연결하는 방법으로 진행된다.

2021년 9월 23일
·
0개의 댓글
·
post-thumbnail

[백준] 1197 - 최소 스패닝 트리 (java)

문제 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다. 입력 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 ...

2021년 1월 29일
·
0개의 댓글
·