목록개념 (1)

개발 쥬스

[핵심정리] 크루스칼 알고리즘

크루스칼 알고리즘에 대해서 핵심만 담아보았습니다.시간복잡도: O(ElogE) (E: 그래프의 간선의 개수) 크루스칼 알고리즘을 알기 전에 먼저 다음 개념을 알아야 합니다. 🔍 신장 트리란?하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다. 위 개념을 바탕으로 크루스칼 알고리즘에 대한 설명을 하면 다음과 같습니다. 🔍 크루스칼 알고리즘이란?그리디 알고리즘으로 분류되고 가장 적은 비용으로 만든 신장 트리를 의미합니다. 그렇다면 크루스칼 알고리즘은 어떻게 구현하는지 그림을 통해서 원리를 파악하겠습니다. 🔍 크루스칼 알고리즘의 구현 과정핵심은 그래프에서 서로 연결되어 있는 간선의 비용이 가장 작은 선들을 우선적으로 선택하고, 간선을 구성하고 있는 노드들을 서로..
알고리즘 2024. 10. 2. 19:37
이전 Prev 1 Next 다음