34. Prim 알고리즘

Prim 알고리즘이란?

Kruskal 알고리즘과 마찬가지로 그리디 알고리즘을 기반으로 하며, 어떤 정점을 선택할 때 그 정점과 연결된 간선 중 최소 비용 간선을 선택하는 방식으로 동작한다.

---

Prim 알고리즘의 동작 방식

1. 임의의 정점을 선택하고 이 정점을 시작점으로 설정한다.

2. 시작점과 인접한 간선 중 최소 비용 간선을 선택한다.

3. 선택한 간선으로 연결된 정점 중 방문하지 않은 정점들 중 최소 비용의 간선을 선택한다.

4. 모든 정점을 방문할 때까지 2, 3 과정을 반복한다.

 

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

#define infinity 9999
#define MAX 20

int G[MAX][MAX],spanning[MAX][MAX],n;

int prims();

int main()
{
    int i,j,total_cost;
    printf("정점의 개수 : ");
    scanf("%d",&n);

    printf("그래프의 가중치 인접행렬 : \n");
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            scanf("%d",&G[i][j]);

    total_cost=prims();
    
    printf("스패닝트리 인접행렬\n");
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            printf("%d ",spanning[i][j]);
        printf("\n");
    }

    printf("\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;
    no_of_edges=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);
}