[알고리즘]최소신장트리 (MST)구현하기 - C로구현하기

*신장 부 그래프:
그래프 G의 모든 정점들을 포함하는 부그래프.

* 신장트리:
(자유)트리인 신장 부그래프.

최소신장트리 Minimum spanning tree: G의 신장트리 가운데 간선 무게의 합이 최소인 것.
-통신망, 교통망 등의 설계에 자주 응용된다.

* 최소신장트리의 속성
    * 사이클 속성 (없음)
    * 분할 속성
* 최소신장트리 구하는 알고리즘
        *탐욕법
        초기구성으로부터 시작하여 부분적인 향상을 계속함으로써 전체 최적해를 찾을 수 있는 문제들
        탐욕적 선택 속성을 가진 경우에만 탐욕해가 최적해가 된다.




*prim 알고리즘
해석 :
단순연결 무방향 가중 그래프 G에 대한 최소신장트리를 계산한다.
그래프의 임의의 정점 s를 택하여 s로부터 시작하여 정점들을 배낭에 넣어가며 배낭안에서 MST, 즉 최소신장트리 T를 키워나간다.
s는 T의 루트가 된다.

우선 순위큐가 베낭안의 정점들을 잠깐 빼어서 내놓는 베낭 밖역할을 하고, MST가 베낭 안의 역할을 한다.

? 탐욕법으로 작성해도 되는가? 그 정당성
탐욕적 선택 속성을 갖고 있는지 확인해야 한다.
Prim 알고리즘은 반복의 각 라운드에서 항상 베낭 C안의 정점들을 배낭 C밖의 정점과 이어주는 최소 무게의 간선을 선택하므로
MST에 항상 타당한 간선을 추가하게 된다.
따라서 최소신장트리에 관환 분할 속성의 요건을 만족하므로 MST를 정확하게 구한다.

구현법:
처음 시작 정점에 대해 우선순위 큐에 모든 인접정점을 넣고,
그 중 가장 비용이 작은 간선을 채택해서(==우선순위 큐에서 pop) 그 끝의 정점(fresh일 것이다)을 위의 과정을 반복한다.
    (popqueue했는데 visited node였다면 free를 해주어야 할 것이다.)(enque할 때가 아니라 pop하고 나서 그게 경로상의 지점이 되므로, 이때 visited를 갱신해주면 된다. )
비용을 따로 구하려면 각 과정에서 간선의 비용을 더해나가면 되고,
과정을 기록하고 싶으면 배열이나 리스트에 하나씩 담아가면 된다.

Prim 알고리즘 seudo code
Alg prim-JarnikMAST(G)

input n개의 정점과 m개의 간선을 가진 가중치가 있는 그래프 G
output G의 최소신장트리 경로.(또는 그 총 비용)
1. for each v in G.vetices()
  d(v) <- INF
  p(v) <- none
2. s <- a vertex of G
3. d(s) <- 0
4. Q <- 우선순위 큐: d를 라벨로 해서 우선순위로 구현되어있다.
5. while(!Q.isEmpty())
    u <- Q.removeMin()
    for each e in G.incidentEdges(u)
        z <-G.opposite(u,e)//z는 e의 반대편: u이거나 아무튼 Q에 있는 애들일 때 말이 된다.
        if ((z in Q) & w(u,z) < d(z))
            d(z) <- w(u,z)
            p(z) <- e//경로에 포함시킨다!
            Q.replaceKey(z, w(u,z))

실제로 구현한 코드 seudo code
0. total_cost = 0, L <- empty list  //총 비용 저장, 비어있는 리스트에 최소신장트리 방문 노드들 순서대로 저장.(optional)
1. for e in incindentEdges(1): //임의의 정점이어도 되지만 1 정점부터 방문, 1에 인접한 노드들 우선순위큐에 삽입
    enqueue(e)
2. vertex(1).visited = 1 //1은 방문 처리
3. L.addLast(1) //경로에 저장.
4. while (!Q.isEmpty())
    edge = Queue.pop()
    if(edge.visited = TRUE)
        removeEdge(edge)
        continue
    w = Opposite(edge)
    w.visited = 1
    total_cost += edge.weight
    L.addLast(w)
    for v in incidentEdges(w):
        if(v.visited = FALSE)
            enqueue(v)

5. return total_cost

구현한 C코드

#include <stdio.h>
#include <stdlib.h>

//정점, 간선 개수를 입력 받고
//이어지는 간선 개수 만큼의 입력 줄에서 노드 양쪽과 무게를 입력 받는다.
//이때 노드 1에서 출발하는 경우의 최소신장트리에 속하는 노드와 그 때의 최소 무게를 출력한다.

//prim 알고리즘을 사용한다.

typedef struct edge_
{
    int s;
    int e;
    int weight;
    struct edge_ *next;
}edge;


int N,M;
edge *graph;
int visited[1001];

int path[101] = {0,};
int idx = 0;
edge *pq;

//method
edge *popqueue();
void enqueue(edge *e);
int prim(int s);


/*
 * 프림 알고리즘: 임의의 한 정점을 먼저 T에 넣는다. (T가 곧 우선순위 큐가 됨.)
 * T에 있는 노드와 T에 없는 노드 사이의 가중치가 가장 작은 간선을 찾는다.
 * 해당 간선에 속한 T에 없던 노드를 T에 포함시킨다.
 * 위 과정을 반복한다.
 */

void ft_handle_error(char *str)
{
    printf("%s", str );
    exit(1);
}

void initGraph()
{
    for(int i=1;i<=N;i++)
    {
        graph[i].next = NULL;
        visited[i] = 0;
    }
    pq = (edge *)malloc(sizeof(edge));
    pq->next = NULL;
}

void makeEdge(int a, int b, int weight)
{
    edge *p = &graph[a];
    while(p->next != NULL && p->next->e < b)
        p = p->next;
    edge *newedge = (edge*)malloc(sizeof(edge));
    newedge->s = a;
    newedge->e = b;
    newedge->weight = weight;
    newedge->next = p->next;
    p->next = newedge;

}

void buildGraph()
{
    int u,v,w;
    for(int i=1;i<=M;i++)
    {
        scanf("%d %d %d", &u, &v, &w);
        makeEdge(u,v,w);
        makeEdge(v,u,w);
    }
}

void print_path()
{
    for(int i =0;i<idx;i++)
        printf("%d ", path[i]);
    printf("\n");
}
//****************queue method******************
edge *popqueue()
{
    if (pq->next == NULL)
        ft_handle_error("no element in queue!\n");
    edge *pop = pq->next;
    pq->next= pop->next;
    return (pop);
}

void enqueue(edge *e)
{
    edge *newedge = (edge*)malloc(sizeof(edge));
    newedge->weight = e->weight;
    newedge->e = e->e;
    newedge->s = e->s;

    edge *p = pq;
    while(p->next != NULL && p->next->weight < e->weight)
        p = p->next;
    newedge->next = p->next;
    p->next = newedge;
}

int isEmpty()
{
    if(pq->next == NULL)
        return 1;
    return 0;
}

//*******************prim algorithm*************************
int prim(int s)
{
    int final_cost = 0;
    edge *p;

    p = graph[s].next;
    while(p != NULL)
    {
        enqueue(p);
        p=p->next;
    }
    visited[s] = 1;
    path[idx++] = s;

    while(!isEmpty())
    {
        edge *pop = popqueue();
        //printf("pop : %d\n", pop->e);
        int cur = pop->e;
        if(visited[cur] == 1)
        {
            //printf("free %d\n", cur);
            free(pop);
            continue;
        }
        path[idx++] = cur;
        visited[cur] = 1;
        final_cost += pop->weight;
        p = graph[cur].next;
        while(p != NULL)
        {
            if (visited[p->e] == 0) {
                enqueue(p);
            }
            p = p->next;
        }

    }
    return final_cost;
}



void printGraph()
{
    for(int i =1; i<=N;i++)
    {
        printf("%d: ", i);
        edge *p = graph[i].next;
        while(p!=NULL)
        {
            printf("%d (%d)", p->e,p->weight);
            p=p->next;
        }
        printf("\n");
    }
}
int main()
{
    scanf("%d %d", &N, &M);
    graph = (edge *)malloc(sizeof(edge)*(N+1));
    initGraph();
    buildGraph();
    //printGraph();
    int n = prim(1);
    print_path();
    printf("%d", n);
}

*Kruskal 알고리즘
이 알고리즘 역시도 탐욕법에 기초한다.
알고리즘 수행을 위한 전초 작업으로 모든 정점을 각각의 독자적인 배낭에 넣는다.
즉, 그래프 G의 정점 수가 n이면 n개의 배낭으로 시작하는 것이다.
그런 다음 배낭 밖의 간선들을 우선순위 큐Q에 저장한다. Q의 원소는 간선들이며 키는 간선의 무게(가중치)다.
비어있는 MST T를 초기화한 후, 반복의 각 라운드에서 두 개의 다른 배낭 안에 양끝점을 가진 최소 무게의 간선을
MST T에 포함하고 두 배낭을 하나로 합친다. 그래프 G의 정점 수 n보다 하나 작은 수의 간선을 배낭에 포함할 때까지 반복한다.
반복이 완료되면 MST T를 포함하는 한 개의 배낭만 남는다.

Alg KruskalMST(G)
input n개의 정점과 m개의 간선을 가진 가중치 그래프 G
output G의 MST인 T

1. for each v in G.vertices()
    define a Sack(v) {V}
2. Q <- G의 모든 간선을 담은 우선순위 큐
3. T <- none
4. while (T has fewer than n- 1 edges)
    (u,v) <- Q.removeMin()
    if (Sack(u) != Sack(v))
        Add edge(u,v) to T
        Merge Sack(u) and Sack(v)
5. return T

실제로 구현한 kruskal
1. 우선 순위 큐에 모든 간선들을 입력과 동시에 삽입한다.
2. kruskal 알고리즘 수행 시작: 우선 순위큐에서 (가장 비용이 작은 )간선을 꺼낸 후에, 간선의 시작과 끝점의
        union이 같은지 다른지 확인한다.
        같다면 free 후에 pass(continue)
        다르다면 비용을 저장하거나 더한 후 그 간선을 이루는 두 정점의 집합을 통일시킨다.
         * 집합의 통일: e를 s에 맞춘다.  단, 조상까지 변경해야 하므로 자식까지 모두 내려간 후에 부모로 타고 올라가면서 업데이트.

 

구현 C코드는 다음기회에...