프림.md

[알고리즘 개념] 최소신장트리(MST)-Prim

개념

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나간다
• 시작 단계에서는 시작 정점만이 신장 트리 집합에 포함된다
• 앞 단계에서 만들어진 신장 트리 집합에 인접한 정점들 중에서 최저 간선으로 연결된 정점을 선택하여 트리를 확장해나간다

인접행렬 그래프의 MST를 구하기 위한 Prim 알고리즘 구현

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class algorithm_prim {

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = null;
		int[][] adjMat = new int[N][N];
		int[] minEdge = new int[N];
		boolean[] visited = new boolean[N];
		
		for</