네모장 | 네모장

최소 신장 트리

최소 신장트리

사용한 간선들의 가중치 합이 최소
간선 가중치를 고려하여 최소 비용의 신장 트리 선택
그래프의 모든 노드 포함
모든 노드는 서로 연결
사이클 X
Kruskal 알고리즘, Prim 알고리즘으로 구현

Kruskal 알고리즘

가장 적은 비용으로 모든 노드 연결
간선 선택 기반
서로소 집합(Disjoint Set) / Union-Find 알고리즘 적용
그래프를 간선 리스트로 표현
순서
1. 모든 가중치를 오름차순으로 정렬
2. 가중치가 가장 작은 간선 선택
3. 해당 간선이 연결하려는 노드가 서로 연결되지 않은 상태라면 2개의 노드 연결
4. 1~3 과정을 반복

Disjoint Set 서로소 집합

공통 원소가 없는 두 집합
union, find 두 가지 연산
union
- 두 개의 원소가 각각 포함되어 있는 집합을 하나로 합침
find
- 특정한 원소가 속한 집합이 어떤 집합인지 찾음
하나의 트리를 하나의 집합으로 볼 때, find는 트리의 루트 노드를 찾고, 그 루트 노드를 통해 특정 집합 표현
union은 두 원소에 대해 find 연산을 수행하여 각각의 루트 노드를 찾고, 한 쪽의 루트 노드를 다른 쪽에 연결함으로써 하나의 트리로 만드는 합집합 연산 수행

static int find_parent(int x) {
	if (parent[x] != x) {
		return find_parent(parent[x]);
	}
	return x;
}

// 경로 압축 기법 적용
static int find_parent_compress(int x){
	if (parent[x] != x) {
		parent[x] = find_parent(parent[x]);
	}
	return parent[x];
}

static void union_parent(int a, int b){
	a = find_parent(a);
	b = find_parent(b);
	
	if (a < b) {
		parent[b] = a;
	} else {
		parent[a] = b;
	}
}

public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	int V = sc.nextInt();
	int E = sc.nextInt();

	for (int i = 1; i <= V; i++) {
		parent[i] = i; // 부모 테이블 자기 자신으로 초기화
	}
	
	for (int i = 1; i <= E; i++) {
		int a = sc.nextInt();
		int b = sc.nextInt();
		
		// 각 간선마다 유니온 연산
		union_parent(parent, a, b);
	}
}

프림 알고리즘

시작 정점을 기준으로 가장 작은 간선과 연결된 정점을 선택하여 신장 트리 확장
Heap 이용
정점 선택 기반
그래프를 인접 리스트로 표현
순서
1. 임의의 간선 선택
2. 선택한 간선의 정점으로부터 가장 낮은 가중치를 갖는 정점 선택
3. 모든 정점이 선택될 때까지 반복

// O(N^2) 알고리즘 (배열 이용)
public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt();
	int[][] input = new int[N][N];
	int[] minEdge = new int[N];
	
	boolean[] V = new boolean[N];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			input[i][j] = sc.nextInt();
		}
		minEdge[i] = Integer.MAX_VALUE;
	}

	int minVertex, min, result = 0;
	
	minEdge[0] = 0;
	
	for (int c = 0; c < N; c++) {
		min = Integer.MAX_VALUE;
		minVertex = 0;
		// priority queue로 대체 가능

		// V와 연결된 간선 중 비용이 최소인 간선, 그 간선과 연결된 노드를 찾는다
		for (int i = 0; i < N; i++){
			if (!V[i] && min > minEdge[i]) {
				min = minEdge[i];
				minVertex = i;
			}
		}
	
		// 해당 노드를 V에 포함시킨다.
		result += min;
		V[minVertex] = true;
		
		for (int i = 0; i < N; i++) {
			// V에서 해당 노드까지 가는 최소 비용 간선 갱신
			if (!V[i] && input[minVertex][i] != 0 && minEdge[i] > input[minVertex][i]) {
				minEdge[i] = iput[minVertex][i];
			}
		}
	}
	System.out.println(result);
}

// O(E log V) 알고리즘 (Priority Queue 이용)
static class Vertex implements Comparable<Vertex> {
	int n, edge;
	public Vertex(int n, int edge) {
		super();
		this.n = n;
		this.edge = edge;
	}
	@Override
	public int compareTo(Vertex o) {
		return this.edge - o.edge;
	}
}
public static void main (String[] args) {
	Scanner sc = new Scanner(System.in);
	
	N = sc.nextInt();
	int[][] input = new int[N][N];
	int[] minEdge = new int[N];
	PrioirtyQueue<Vertex> queue = new PriorityQueue<>();
	
	boolean[] V = new boolean[N];

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			input[i][j] = sc.nextInt();
		}
		minEdge[i] = Integer.MAX_VALUE;
	}

	int result = 0, nodeCount = 0;
	
	// 임의의 노드(0번 노드)를 포함시킨다
	minEdge[0] = 0;
	queue.offer(new Vertex(0, 0));
	
	while (!queue.isEmpty()) {
		Vertex minVertex = queue.poll();
		if (V[minVertex.n]) continue;
		result += minVertex.edge;
		V[minVertex.n] = true;
		if(++nodeCount == N) break;

		for (int to = 0; to < N; to++) {
			if (!V[to] && input[minVertex.n][to] != 0 && minEdge[to] > input[minVertex.n][to] {
				minEdge[to] = input[minVertex.n][to];
				queue.offer(new Vertex(to, inut[minVerted.n][to]));
			}
		}
	}
	
	
	System.out.println(result);
}

Kruskal vs Prim

프림은 사이클 가능성이 없음
크루스칼은 사이클이 이루어지는지 항상 확인 (find(a) == find(b))
간선의 개수가 적은 경우 크루스칼
간선의 개수가 많은 경우 프림