최소 신장나무 - 크루스칼 , 프림 알고리즘

최소 신장 나무

- 그래프 G의 모든 정점들을 사이클이 생기지 않게 연결하면서 간선에 부여된 가중치의 합이 가장 적게 구성된 나무.

- 만드는 방법에는 크루스칼 , 프림 알고리즘이 있다.

신장 나무

가중 무방향 그래프에 대하여 신장 나무는 주어진 그래프의 모든 노드들을 포함하는 연결된 부분 그래프로 나무를 형성.

신장 나무 중에서 가중치의 합이 가장 작은 신장 나무로 최소 신장 나무도 있음.

크루스칼 알고리즘

- 욕심쟁이 방법 적용. 사이클을 만들지 않는 최단 간선을 하나씩  추가해 나감으로 최소 신장 나무를 구하는 방법

- 간선을 가중치가 증가하는 순으로 한 번에 하나씩 사이클이 만들어 지지 않도록 추가함.

Kruskal (Adj(G), T)
{
    /* 입력 : 그래프 g=(v,e)의 인접 리스트, 출력 : 최소 신장 나무의 간선 집합 T */
    T=∅ ;
    for( 그래프 G의 각 정점 v)
        init_S(v);
    /* 가중치가 증가하는 순으로 E의 간선을 정렬 */
    for(가중치가 작은 것부터 모든 간선 (u,v) E)
        if ( find(u)=find(v)){
            union(u,v); /* T=T U {(u,V)} */
    }
}

프림 알고리즘

- 가중치가 주어진 그래프에서 임의의 정점을 선택하고 이 정점에 연결된 간선들 중 가중치가 제일 작은 간선을 선택하여 

최소 비용 신장 나무에 포함시킴.

- 최소 비용 신장 나무에 인접한 정점들에 연결된 간선들에 대해 가중치가 제일 작은 간선을 선택하여 사이클이 형성되지 않으면

최소 비용 신장 나무에 포함시킴.

- 이 과정을 간선의 수가 N-1 개가 될 때까지 반복한다.

Prim (Adj(G), T)
{
    /* 입력 : 그래프 g=(v,e)의 인접 리스트, 출력 : 최소 신장 나무의 간선 집합 T */
    T=∅ ;
    S={1}; /* 정점들의 집합-첫번째 정점으로 초기화 */
    while (S!=V){
    u eS, v e V-S인 것중 최소인 간선 (u,v) 선택;
    T=T U {(u,v)}
    S=S U {v}
    }
}