알고리즘
[알고리즘] 크루스칼 알고리즘이란? (최소 신장 트리 찾기)
1️⃣ 신장 트리란?크루스칼 알고리즘은 '최소 신장 트리 알고리즘'이다. 즉, 최소 신장 트리를 찾기 위한 알고리즘이라는 것이다.최소 신장 트리란 신장 트리 중에서 최소 비용으로 만들 수 있는 신장 트리를 의미한다. 크루스칼 알고리즘을 설명하기 전에 신장 트리에 대해 설명을 하고 넘어가겠다. 신장트리란 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다.모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건에 해당한다. 따라서 이런 그래프를 신장 트리라고 부르는 것이다. 신장 트리는 동일한 그래프에서도 여러 개의 신장트리를 찾을 수 있다. 하지만 가능한 한 최소한의 비용으로 신장 트리를 찾아야 하는 상황이 존재한다.따라서 신장 ..
