최소 신장 트리를 찾는 크루스칼 알고리즘 파헤치기

1. 신장트리(spanning tree) n개의 정점으로 이루어진 "무방향 그래프"에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이다. 그래서 이러한 그래프를 신장 트리라고 부른다. 위와 같은 그래프에서 신장 트리는 여러개 찾을 수 있다. 예를 들어 아래와 같은 그래프는 하나의 신장 트리이다. 하지만 다음 그림과 같은 그래프들은 신장 트리가 아니다. 구체적으로 다음은 노드 1을 포함하고 있지 않다 다음은 노드 4-6-7에서 사이클이 발생하므로 신장트리가 아니다. 2. 최소 신장 트리(Minimum spanning tree)..