boomini

boomini

천천히 공부하기

크루스칼 & 프림 알고리즘

Updated:

서로소 집합(Disjoint-set)

  • 서로소 또는 상호배타 집합들은 서로 중복 포함된 원소가 없는 집합들이다. 다시 말해 교집합이 없다.
  • 집합에 속한 특정 멤버를 통해 각 집합들을 구분한다. 이를 대표자라고 한다.
  • 서로소 집합을 연결하는 방법
    • 연결리스트
    • 트리
  • 서로소 집합 연산
    • Make-Set(x)
    • Find-Set(x)//대표자 찾기
    • Union(x,y)//합치기
  • 서로소 집합 표현 - 연결리스트
    • 같은 집합의 원소들은 하나의 연결리스트로 관리한다.
    • 연결리스트의 맨 앞의 원소를 집합의 대표 원소로 삼는다.
    • 각 원소는 집합의 대표원소를 가리키는 링크를 갖는다.
  • 서로소 집합 표현 - 트리
    • 하나의 집합을 하나의 트리로 표현한다.
    • 자식 노드가 부모 노드를 가리키며 루트 노드가 대표자가 된다.

  • 맨처음 원소 한개씩 갖는 서로소 집합으로 시작한다.

  • Make-Set(X) : 유일한 멤버 x를 포함하는 새로운 집합을 생성하는 연산
Make-Set(x)
	p[x] <- x
  • Find-Set(x) : x를 포함하는 집합을 찾는 연산
Find-Set(x)
	IF x == p[x] : RETURN x
	ELSE
  • Union(x,y) : x와 y를 포함하는 두 집합을 통합하는 연산
Union(x,y)
	IF Find-Set(y) == Find-Set(x) RETURN;
	p[Find-Set(y)] <- Find-Set(x)
  • 연산의 효율을 높이는 방법
    • Rank를 이용한 Union
    • 각 노드는 자신을 루트로 하는 subtree의 높이를 랭크(Rank)라는 이름으로 저장한다.
    • 두 집합을 합칠 때 rank가 낮은 집합을 rank가 높은 집합에 붙인다.(랭크 변화가 없도록)
    • Path compression
    • Find-Set을 행하는 과정에서 만나는 모든 노드들이 직접 root를 가리키도록 포인터를 바꾸어 준다.
    • 때문에 Find-Set을 행하지 않으면 Path compression은 일어나지 않는다.
  • Path Compression 적용한 Find_Set 연산
  • Find_Set(x) : x를 포함하는 집합을 찾는 오퍼레이션 
    Find-Set(x)
 IF x == p[x] : RETURN x
 ELSE         : RETURN Find_Set(p[x])

Find-Set(x)
	IF x==p[X] : RETURN x
	ELSE	   : RETURN p[x] = Find_Set(p[x])
  • Find_set 연산은 특정 노드에서 루트까지의 경로를 찾아 가면서 노드의 부모 정보를 갱신한다.

예시

import java.util.Arrays;

public class DisjoinSetTest {

	static int N; //원소개수
	static int[] parents; //부모원소를 관리(트리처럼 사용)
	
	private static void make() {
		//모든 원소를 자신을 대표자로 만듦.
		for (int i = 0; i < N; i++) {
			parents[i] = i;
		}
	}
	
	//a가속한 집합의 대표자 찾기
	private static int find(int a) {
		if(a==parents[a]) return a; //자신이 대표자
		return parents[a] = find(parents[a]); //자신이 속한 집합의 대표자를 자신의 부모로 : path compression
	}
	
	// 두 원소를 하나의 집합으로 합치기(대표자를 이용해서 합침)
	private static boolean union(int a , int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot) return false; //이미 같은 집합으로 합치지 않음
		
		parents[bRoot] = aRoot;
		return true;
	}
	
	public static void main(String[] args) {
		N = 5;
		parents = new int[N];
		
		//make set
		make();
		System.out.println(union(0,1));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(2,1));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(3,2));
		System.out.println(Arrays.toString(parents));
		System.out.println(union(4,3));
		System.out.println(Arrays.toString(parents));
		
		System.out.println("==========find=====================");
		System.out.println(find(4));
		System.out.println(Arrays.toString(parents));
		System.out.println(find(3));
		System.out.println(Arrays.toString(parents));
		System.out.println(find(2));
		System.out.println(Arrays.toString(parents));
		System.out.println(find(0));
		System.out.println(Arrays.toString(parents));
		System.out.println(find(1));
		System.out.println(Arrays.toString(parents));
	}
}

최소 신장 트리

  • 그래프에서 최소비용 문제
    • 모든 정점을 연결하는 간선들의 가중치의 합이 최소가 되는 트리(최소신장트리)
    • 두 정점 사이의 최소 비용의 경로 찾기 (최단경로)
  • 신장트리
    • n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리.
    • 어떤 정점도 끊어지지 않은 트리.
  • 최소신장트리
    • 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리.

크루스칼 알고리즘

  • 간선을 하나씩 선택해서 MST를 찾는 알고리즘
    1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
    2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
      • 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택
    3. n-1개의 간선이 선택될 때까지 2를 반복
  • 간선을 하난씩 선택하면서 트리를 완성해가는 느낌.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class MSTKruskalTest {

	static class Edge implements Comparable<Edge> {
		int start, end, weight;

		public Edge(int start, int end, int weight) {
			super();
			this.start = start;
			this.end = end;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			//return this.weight - o.weight; //간선의 부호가 모두 같을때.
			return Integer.compare(this.weight, o.weight);
		}
	}

	static int V, E;
	static Edge[] edgeList;
	
	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());

		// 간선리스트 작성, from, to, 비용
		edgeList = new Edge[E];
		
		for (int i = 0; i < E; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			edgeList[i] = new Edge(start,end,weight);
		}
		
		Arrays.sort(edgeList); //오름차순 정렬
		
		make(); //모든 정점을 각각의 집합으로 만들고 출발
		
		//간선 하나씩 시도하면 트리 만들어 감
		int cnt = 0, result = 0;;
		for (Edge edge : edgeList) {
			if(union(edge.start, edge.end)) {
				result += edge.weight;
				if(++cnt == V-1) break; //신장트리 완성
			}
		}
		System.out.println(result);
	}
	
	static int[] parents; //부모원소를 관리(트리처럼 사용)
	
	private static void make() {
		//모든 원소를 자신을 대표자로 만듦.
		parents = new int[V];
		for (int i = 0; i < V; i++) {
			parents[i] = i;
		}
	}
	
	//a가속한 집합의 대표자 찾기
	private static int find(int a) {
		if(a==parents[a]) return a; //자신이 대표자
		return parents[a] = find(parents[a]); //자신이 속한 집합의 대표자를 자신의 부모로 : path compression
	}
	
	// 두 원소를 하나의 집합으로 합치기(대표자를 이용해서 합침)
	private static boolean union(int a , int b) {
		int aRoot = find(a);
		int bRoot = find(b);
		if(aRoot == bRoot) return false; //이미 같은 집합으로 합치지 않음
		
		parents[bRoot] = aRoot;
		return true;
	}
	
}

PRIM 알고리즘

  • 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어가는 방식
    1. 임의 정점을 하나 선택해서 시작
    2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택.
    3. 모든 정점이 선택될 때까지 1,2 과정반복
  • 서로소인 2개의 집합(2 disjoint-set) 정보를 유지
    • 트리 정점들(tree vertices) - MST를 만들기 위해 선택된 정점들
    • 비트리 정점들(non-tree vertices)- 선택되지 않은 정점들
  • 정점을 방문했는지 확인하는 배열하나.
  • min_edge 배열 하나 : 타정점에서 자신으로의 최서간선비용.
  • 크루스칼 알고리즘은 정렬이 동반된다. 즉, 정렬에 소요되는 시간이 추가된다.
  • 간선이 상대적으로 많을때는 크루스칼이 프림보다 효율적이지 않은게 대부분이다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class MSTPrimTest {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(in.readLine()); 
		int[][] adjMatrix = new int[N][N];
		boolean[] visited = new boolean[N];
		
		int[] minEdge = new int[N];
		StringTokenizer st = null;
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			for(int j=0; j<=N; j++) {
				adjMatrix[i][j] = Integer.parseInt(st.nextToken());
			}
			minEdge[i] = Integer.MAX_VALUE;
		}
		
		int result = 0; //최소신장트리비용
		minEdge[0] = 0; //임의의 시작점 0의 간선비용을 0으로 세팅.
		
		for(int i=0; i<N; i++) {
			//1. 신장트리에 포함되지 않은 정점 중 최소간선비용의 정점 찾기.
			int min = Integer.MAX_VALUE;
			int minVertex = -1; //최소간선비용의 정점 번호
			for(int j=0; j<N; j++) {
				if(!visited[j]&&min>minEdge[j]) {
					min = minEdge[j];
					minVertex = j;
				}
				
			}
			visited[minVertex] = true; //신장트리에 포함시킴
			result += min;
			//2. 선택된 정점 기준으로 신장트리에 연결되지 않은 타 정점과의 간선 비용 최소로 업데이트
			for(int j=0; j<N;j++) {
				if(!visited[j]&&adjMatrix[minVertex][j]!=0&&adjMatrix[minVertex][j]<minEdge[j]) {
					minEdge[j]= adjMatrix[minVertex][j];
				}
				
			}
		}
		System.out.println(result);
	}
}

Leave a comment

You may also enjoy

MVC

Web Application Architecture jsp를 이용하여 구성할 수 있는 Web Application Architecture는 크게 model1과 model2로 나뉜다. jsp가 client의 요청에 대한 Logic 처리와 response page(view)에...

JSP

Session & Cookie http protocol의 특징 client가 server에 요청 server는 요청에 대한 처리를 한 후 client에 응답 응답 후 연결을 해제 » stateless 지속적인 연결로 ...

JSP

JSP 자바 서버 페이지는 HTML내에 자바 코드를 삽입하여 웹 서버에서 동적으로 웹 페이지를 생성하여 웹 브라우저에 돌려주는 언어이다. Servlet : html in java (out.print를 사용하여 html을 작성한다. 불편하다.) JSP : java in ...

문자열 패턴 매칭

문자열 패턴 매칭 패턴 매칭에 사용되는 알고리즘 고지식한 패턴 검색 알고리즘 라빈-카프 알고리즘 보이어-무어 알고리즘 KMP 알고리즘