Prim 알고리즘

 프림 알고리즘은 크루스칼 알고리즘과 비슷하게 MST를 만들어가는 방식 중 하나이다.

 

하지만 크루스칼 알고리즘과는 약간의 차이가 있다.

 

프림 알고리즘은 하나의 정점에서 연결된 간선들 중에 하나씩 선택하며 MST를 만들어 가는 방식인데,

 

우선 제일 먼저 임의의 정점을 하나 선택해서 시작하게 된다.

 

그 후 선택한 정점과 인접하는 정점들 중에서 최소의 비용을 가지는 간선이 존재하는 정점을 선택한다.

 

그 이후 위 두 줄의 방법을 모든 정점이 선택할 때 까지 반복한다.

 

크루스칼 알고리즘과 프림 알고리즘의 차이점은 

 

간선을 선택하느냐 정점을 선택하느냐의 차이이다.

 

크루스칼은 간선의 가중치를 오름차순으로 정렬하여 간선의 가중치에 따라 선택하고,

 

프림은 정점을 선택해서 그 정점과 다른 정점 사이에 최소 비용을 가지는 간선이 존재하는 정점을 선택하는 것이다.

 

약간의 차이가 있다. 

 

 

 

프림 알고리즘의 경우, MST를 만들기 위해 선택된 정점들과 선택되지 않은 정점들을 2개의 집합으로 유지해서 

 

서로소 집합 형태로 구성한다. 이를 통해 정점들의 선택 정보를 유지하게 된다. 

 

 

프림 알고리즘을 가시화 하면 다음과 같다.

 

Prim's algorithm - Wikipedia

 

간선을 정렬하여 간선을 선택하던 크루스칼과는 달리

 

먼저 A 정점을 선택한 뒤 간선을 비교한 후 최소 비용 간선을 가지는 정점을 선택하게 된다.

 

 

코드로 구현하면 다음과 같다.

 

int V= Integer.parseInt(br.readLine());
int E= Integer.parseInt(br.readLine());

int [][]arr = new int [V][V];

우선 정점과 간선을 입력받고,

 

정점의 수만큼의 2차원 배열을 만든다.

 

for(int i=0;i<E;i++){
	StringTokenizer st = new StringTokenizer(br.readLine());
    int a= Integer.parseInt(st.nextToken());
    int b= Integer.parseInt(st.nextToken());
    int w= Integer.parseInt(st.nextToken());
    arr[a][b]=w;
    arr[b][a]=w;
    }

그 후 시작 정점과 목표 정점, 가중치를 입력받아 각각을 입력한다.

 

static final int INF= Integer.MAX_VALUE;

boolean [] visited = new boolean [V];

int [] p = new int [V];
int [] dist= new int [V];
Arrays.fill(dist,INF);

해당 정점을 선택했는지를 확인할 boolean 배열을 만들고,

어디서 출발했는지 저장하는 배열과

가중치를 저장하는 배열을 만든다.

 

이때 가중치를 저장하는 배열을 큰 값으로 초기화한다.

 

이후 임의의 한 점을 선택하게 되는데

 

여기서는 0번째 정점을 선택한다고 가정하자. 

 

dist[0]=0;
p[0]=-1;

0번째 정점에서 0번째 정점까지의 거리는 0이니 dist[0]에는 0을,

 

0번째 정점은 출발점이니까 어디서 출발했는지 확인하는 배열 p[0]=-1을 저장한다.

 

int result=0;

for(int i=0;i<V-1;i++){
	int min=INF;
    int idx=-1;
    
    
    //선택하지 않은 것들 중 가장 작은 값 선택
    for(int j=0;j<V;j++){
    	if(!visited[j]&&dist[j]<min){
        	min=dist[j];
            idx=j;
            }
        }
    //idx 에 가장 작은 값을 가지느 정점 선택
    visited[idx]=true;
    
    for(int j=0;j<V;j++){
    	if(!visited[j]&& arr[idx][j]!=0&&dist[j]>arr[idx][j]){
        //해당 정점과 인접한 정점 사이의 간선의 가중치가 dist에 저장되어 있는 값보다 작다면 
        //갱신 및 출발점도 갱신
        	dist[j]=arr[idx][j];
            p[j]=idx;
            }
    }
}
for(int i=0;i<V;i++){//거리 계산
	result+=dist[i];
}

 

위와 같이 하나의 정점을 선택하고, 해당 정점과 관련된 배열 값들을 초기화 한 후,

 

해당 정점부터 인접한 정점들 사이의 간선에 대한 가중치를 비교해 가중치가 적은 값을 dist배열에 저장,

 

출발 정점은 p배열에 저장한다.

 

 

이후 dist의 모든 값들을 더하면 해당 그래프를 잇는 최소 신장 트리의 최소 비용이 도출된다.

 

라고 이해했다.