최소 스패닝(신장) 트리

역시나 이분 블로그 참조 : http://kks227.blog.me/220796029558

간선과 정점들이 있을때 서로 연결되서 가중치의 합을 최소인 트리가 스패닝 트리.

주의 : 사이클이 생기면 안된다, 한 정점에서 다른 정점으로 도달하여야 한다.

시간 복잡도는 ElongE라고 한다.

아래는 예시.

1. 아래와 같은 정점들과 간선들에 대한 가중치가 있다고 하자. 아직 하나도 연결 안됬다.

간선들을 가중치순서대로 오름차순으로 정렬한다.

2. 가중치가 가장 낮은 AE부터 시작해서 서로 연결이 되어있지 않으므로 연결해준다.

A와 E는 이제 하나의 집합으로 보자.

3. 순서대로 잇다 보면 3까지 아래처럼 잇게 된다.

4. 그다음 차례인 4를 이어야되는데 이걸 잇게 되면 사이클이 생기게 된다.

그러므로 잇지 않고 그냥 지나간다.

5. 그다음 순서인 5를 잇는다. 이제 모든 정점들이 어디던지 갈수 있다.