프림 알고리즘 구현 C - peulim algolijeum guhyeon C

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

#define infinity 9999 //시작정점을 제외하고 나머지 정점들의
//연결비용을 무한대로 초기화 시키기 위해 infinity라는 변수를 9999로 많이줌
#define MAX 20 //매트릭스의 최대 행, 열

int G[MAX][MAX],spanning[MAX][MAX],n; // G는 모든 각 정점사이의 비용을 입력하기 위한 매트릭스,
//spanning은 최소신장트리의 집합으로 들어갈 정점사이의 비용을 입력시키기 위한 매트릭스

int prims(); //프림 알고리즘 기능의 프로토타입

int main() //메인함수
{
    int i,j,total_cost;
    printf("정점의 개수를 입력하시오.:"); //정점의 개수를 입력
    scanf("%d",&n);

    printf("\n간선 매트릭스에 비용을 입력하시오.:\n");// 간선간의 모든 매트릭스 값을 입력
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&G[i][j]);

    total_cost=prims(); //프림 function을 통해 나온 최소비용합을 변수에 저장
    printf("\n스패닝트리는 다음과 같습니다.:\n");

    for(i=0;i<n;i++)
    {
        printf("\n");
        for(j=0;j<n;j++)
            printf("%d\t",spanning[i][j]);
    }

    printf("\n\n최소비용 값=%d",total_cost);
    return 0;
}

int prims()
{
    int cost[MAX][MAX]; //간선간의 비용이 있는 매트릭스
    int u,v,min_distance,distance[MAX],from[MAX]; //정점의 시작점 정점의 끝점, 최소거리, 거리의 최대,
    int visited[MAX],no_of_edges,i,min_cost,j;

    //정점사이의 비용을 넣을 매트리스와 집합이 되었을때 최소비용을 저장하는 매트릭스를 만듬
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            if(G[i][j]==0)
                cost[i][j]=infinity;
            else
                cost[i][j]=G[i][j];
                spanning[i][j]=0;
        }

    //출발했던 정점과 방문했던 정점과 거리를 초기화
    distance[0]=0;
    visited[0]=1;

    for(i=1;i<n;i++)
    {
        distance[i]=cost[0][i];
        from[i]=0;
        visited[i]=0;
    }

    min_cost=0;        //최소비용이란 변수는 일단 0으로 지정
    no_of_edges=n-1;        //더해진 노드의 개수는 총 n-1개

    while(no_of_edges>0)
    {
        //트리로부터 최소비용거리를 가진 정점들을 찾음
        min_distance=infinity;
        for(i=1;i<n;i++)
            if(visited[i]==0&&distance[i]<min_distance)
            {
                v=i;
                min_distance=distance[i];
            }

        u=from[v];

        //스패닝 트리에 간선을 삽입
        spanning[u][v]=distance[v];
        spanning[v][u]=distance[v];
        no_of_edges--;
        visited[v]=1;

        //최소비용거리로된 정점들을 다시 배열로 정리
        for(i=1;i<n;i++)
            if(visited[i]==0&&cost[i][v]<distance[i])
            {
                distance[i]=cost[i][v];
                from[i]=v;
            }

        min_cost=min_cost+cost[u][v];
    }

    return(min_cost);
}