공부 기록장

PRIM 알고리즘 또한 크루스칼과 비슷하게 최소신장트리 알고리즘 중 하나이다. 프림 알고리즘은 하나의 정점을 시작점으로 하여 cycle을 생성하지 않는 범위 내에서, 최소 가중치를 가지는 정점을 하나씩 포함하여 N-1개의 간선까지 확대하는 알고리즘이다. 1) 임의의 정점을 시작 정점으로 택해서 최소 신장트리의 루트 노드로 삽입하기. 2) 최소 신장트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사하여 이 가중치가 가장 작은 간선을 골라 최소 신장트리에 삽입 3) 모든 점이 다 연결될 때 까지 반복. public class MST_PRIM { public static void main(String[] args) throws IOException{ BufferedRe..

Union-Find 알고리즘은 최소신장트리 알고리즘에 많이 쓰이지만 사실은 서로소 집합을 찾는 알고리즘이다. 서로소 집합은 서로 중복 포함된 원소가 없는 집합들, 즉 교집합이 없는 집합이다. 따라서 집합에 속한 하나의 특정 멤버인 대표자를 이용해 각 집합들을 구분한다. 서로소 집합을 표현하는 방법에는 대표적으로 연결 리스트와 트리가 있다. 연결 리스트 - 같은 집합의 원소들은 하나의 연결리스트로 관리하고, 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다. - 즉, 연결리스트의 헤드가 대표자가 되는 것이다. - 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다. 트리 - 트리도 연결리스트와 비슷하다. 자식 노드가 부모 노드를 가리키며, 루트 노드가 대표자가 된다. 이런 서로소 집합들을 서로 연결 ..