‘단순 경로’ 동일한 간선을 중복하여 포함하지 않는 경로를 뜻한다.
사이클 - 단순 경로이면서 시작과 끝이 같은 경로를 가리켜 ‘사이클’이라 한다.
위와 같이 사이클을 이루지 않는 그래프를 신장 트리(spanning tree) 라고 한다.
앞서 설명한 사이클을 형성하지 않는 그래프, 다시 말해서 신장트리의 특징은 두가지는 다음과 같다.
신장트리의 모든 간선의 가중치 합이 최소인 그래프를 가리켜 ‘최소 비용 신장 트리’ 또는 ‘최소 신장 트리’라 한다.
모든 노드를 있는 제일 짧은 간선들이라 보면 될것 같다.
최소 비용 시장 트리의 구성에 사용되는 대표적인 알고리즘 두가지는 다음과 같다.
간선들을 가중치에 따라 정렬할 후 한개씩 선택하면서 들어갈수 있는지, 즉 사이클을 형성하지 않는지를 판단후 추가하는 알고리즘이다. 사이클 판단에는 union find 를 이용한다고 한다.
지금까지 설명한 크루스칼 알고리즘의 흐름에 있어서 핵심이 되는 사항은 다음과 같다.